
»
Performance
Author
Programming Algorithmic Thinking Improvement for Competitions
Nirmit Dalal
Greenhorn
Joined: Mar 12, 2013
Posts: 22
posted
Oct 06, 2013 23:45:54
0
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
Maxim Karvonen
Ranch Hand
Joined: Jun 14, 2013
Posts: 114
11
posted
Oct 09, 2013 12:14:52
0
Hi, Nirmit.
Did you run your code with large numbers for N? Something like 10000 will be sufficient to see a problem.
Anyway, this task is one of "special kind". Solution algorithm is "just calculate the answer" but to calculate that answer you should use some math. As sample input suggests, an answer is some power of two. First solution calculates exactly that although in a very tricky way. Other solutions may calculate required power in more straight-forward way. You definitely does not need to calculate any f or G function. Probably you should prove that "one particular power of two is the answer", but it is not required to provide "acceptable" solution.
As to the math. You should familiar with number theory to solve this task. Can't suggest any books on that (they may be different in different countries). I learnt required theory on a lectures in training camps during my school years. You may took school math contests (regionals or national levels) and Olympiads as a guideline. There are some books with problems and solution. Some other branches of pure mathematics also may be used to create tasks for programming contests (geometry, algebra, calculus). But you don't need anything special except math used in school math contests (though pretty high-level contests) to solve "special" tasks in programming contests.
Paul Clapham
Bartender
Joined: Oct 14, 2005
Posts: 19098
8
I like...
posted
Oct 09, 2013 18:49:20
0
And if your number theory skills are limited, it's still worthwhile working your way through some small examples and noting the
patterns
which appear. Then you can write code which matches the patterns rather than writing code which implements the question in an unsophisticated way.
It is sorta covered in the
JavaRanch Style Guide
.
subject: Programming Algorithmic Thinking Improvement for Competitions
Similar Threads
help me correct my program
Incorrect Output !
Executable-Java!
Help me out
program correction
All times are in JavaRanch time: GMT-6 in summer, GMT-7 in winter
JForum
|
Paul Wheaton