CODEWITHSUNDEEP
javaalgorithmoptimization
Nirmit Dalal
Nirmit Dalal

Reputation: 325

Programming Algorithmic Thinking Improvement for Competitions

I am new to this community and have already got a lot of -1 votes so I am trying my best to improve the way I can ask a question.

Recently I tried this problem at CodeChef. This is the Problem Definition.

This is probably the easiest task of this problem set. To help you understand the task let us define two key functions: f(n,k), (with k <= n) which gives the number of ways we can draw a sample of k objects from a set of n-distinct objects where order of drawing is not important and we do not allow repetition. G(x1, x2, x3, ... , xn) is the largest integer that perfectly divides all of {x1, x2, x3, ... , xn}. Given an integer N, your task is to compute the value of Y where Y = G( f(2*N,1), f(2*N,3), f(2*N,5), ... , f(2*N,2*N-1)).

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first and the only line of each test case contains a single integer denoting the given N as described in the problem statement.

Output

For each test case, output a single line containing the value of Y. Constraints

1 ≤ T ≤ 10000 2 ≤ N ≤ 1011

Example

Input:

3

6

5

4

Output:

4

2

8

Now I wrote a code in Java which works perfectly fine but the CodeChef online judge give TLE error, so I tried it a couple of different ways but with no success. So I checked some solution which others had posted and I Didnt have a clue what their algorithm did but magically it always came to the right answer So what my concern is that what books should I refer to improve the way these algorithms are written . P.S. Yes I have read Corman

Some other solution did some normal addition and subtraction and Bang!! their answer were correct This was one such solution 

   import java.util.*;
    class Main 
 {
     public static void main(String[] args) {

//public static void main(String[] args) {
    Scanner scan=new Scanner(System.in);
    long T=scan.nextLong();
    long fin;
    while(T>0){
        T--;
        long N=scan.nextLong();
        fin=-(-N^N);
        System.out.println(fin);
}
}
 }

I am also showing what I had attempted :- 

           import java.io.BufferedReader;
         import java.io.IOException;
         import java.io.InputStreamReader;
          import java.util.ArrayList;


       class Code1 
       {
static ArrayList<Long> combValues=new ArrayList<Long>();
static ArrayList<Long> input=new ArrayList<Long>();
static ArrayList<Long> output=new ArrayList<Long>();
public static void main(String args[])throws IOException
{
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    //System.out.println("Enter the values of 'T' ");
    //System.out.println("Input:");
    int T=Integer.parseInt(br.readLine());
    //System.out.println("Enter the value of 'N' ");
    for(int i=1;i<=T;i++)
    {
        input.add(Long.parseLong(br.readLine()));
    }
    for(int i=0;i<T;i++)
    {
        output.add(computeFX(input.get(i)));
    }
    //System.out.println("Output:");
    for(long i:output)
    {
        System.out.println(i);
    }
}
public static long computeFX(long N)
{
    combValues=new ArrayList<Long>();
    for(int i=1;i<=2*N-1;i+=2)
    {
        combValues.add( factorial(2*N)/(factorial(2*N-i)*factorial(i)));
    }
    return computeGX();
}
public static long computeGX()
{
    boolean flag=false;
    long tempY=0;
    long limit=combValues.get(0);
    outer:for(int i=new Long(limit).intValue();i>=1;i--)
    {
        inner:for(int j=0;j<(combValues.size()/2)+1;j++)
        {
            if(combValues.get(j)%i!=0)
            {   
                flag=false;
                break inner;
            }
            else
            {
                flag=true;
            }
        }
        if(flag)
        {
            tempY=i;
            break outer;
        }
    }
    return tempY;
}
public static long factorial(long n)
{
    long fact=1L;
    for(int i=1;i<=n;i++)
    {
        fact*=i;
    }
    return fact;
}

   }

Okay this question may be subjective but I would really like some suggestion as to where to start from.

Upvotes: 3

Views: 552

Answers (1)

Niki
Niki

Reputation: 1123

You will find the magic in the given solution when you try solving a simple solution on a piece of paper.

Try 6 as input. You want to find G(f(12,1), f(12,3), f(12,5), ... , f(12,11)). Calculate fs, you will get: 12, 220, 792,... then convert them to binary.

The result SHOULD divide all these values, so it can't be greater than the smallest one (in this case 12). So in the binary representations, only look at the four right-most bits (since 12 has only 4 bits). In this e.g. all values greater other than twelve have "1000" as their four right-most bits in binary representation.

So basically you need to find GCD of 12 and 8 ("1000" in binary)! ta da! Now you have a much simpler question which the title of the problem referes to (The Easiest Problem). The rest could be done in multiple ways as the solutions on Code Chef shows.

About your question on how to improve your algorithms skills, beside books like Introduction to Algorithms, you need to solve a lot of problems like this one. A good place to start is Project Euler. Another book you can grasp a lot of knowledge about algorithms is a book called: The Algorithm Design Manual by Steven Skiena.

Upvotes: 1

Related Questions