Results 1 to 9 of 9
Thread: Codechef exercise
 01232011, 11:42 PM #1
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
Codechef exercise
This is not me asking for the answer, I have working code which uses an array list but it is too slow to pass the submission, the link isOdd  CodeChef
My code is below:
Java Code:import java.util.*; import java.io.*; public class Main { public static ArrayList<Integer> remove0(ArrayList<Integer> al1) { for(int i = 0; i < al1.size(); i++){ if(al1.get(i) == null){ continue; } else if(al1.get(i) == 0){ al1.remove(i); } } return al1; } public static ArrayList<Integer> tRemove(ArrayList<Integer> al) { if(al.size() == 2){ return al; } else{ for(int i = 0; i < al.size(); i++){ if(al.get(i) == null){ continue; } else if(i % 2 != 0){ al.set(i, new Integer(0)); } } remove0(al); return tRemove(al); } } public static void main(String[] args) throws IOException{ ArrayList<Integer> people = new ArrayList<Integer>(); //Scanner in = new Scanner(System.in); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int cases = Integer.parseInt(br.readLine()); for(int j = 0; j < cases; j++){ people.clear(); System.out.print("Enter a number of crew members"); //int input = in.nextInt(); int input = Integer.parseInt(br.readLine()); for(int i = 0; i <= input; i++){ if(i == 0){ people.add(null); } else{ people.add(new Integer(i)); } } /*for(Integer i : people){ System.out.println(i); }*/ //System.out.println(); tRemove(people); /*for(int i = 1; i < people.size(); i++){ System.out.print("Index " + i + " is "); System.out.println(people.get(i)); }*/ System.out.println(people.get(1)); } } }
 01242011, 12:00 AM #2Member
 Join Date
 Jan 2011
 Posts
 13
 Rep Power
 0
Google the Josephus problem, that's what it looks like.
 01242011, 12:36 AM #3Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,565
 Rep Power
 12
Any help on, I guess, the number theory to solve this problem?
Think about the case where there are 12 people. We can number them as in the question and also write those numbers in binary:
Java Code:1 2 3 4 5 6 7 8 9 10 11 12             1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 1 0
Let's remove them, and also remove the trailing zero from the rest.
Java Code:2 4 6 8 10 12             1 1 1 1 1 1 0 1 0 0 1 0 1 0
Now we notice that the pattern merely repeats itself  the second round losers will be those (2,6,10) that end with a 1.
And so it goes until we have a winner: the person who has the largest number of trailing zeros.
These "winning" numbers have a 1 followed by lots of zeros.
You might want to think about these winning numbers (in binary they are 1,10,100,1000, etc) because there's a pattern to them that you can exploit.Last edited by pbrockway2; 01242011 at 12:41 AM.
 01242011, 09:26 AM #4
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
wow, that's definitely a very helpful way to approach it, my thought is to count the number of trailing zeros with a loop and str.substring, after converting each number to binary string.
I feel like that is fairly inefficient however, for a number like 100, it would have to first loop through 100 items, then loop through each string which can contain a length of 7, I'm a little unfamiliar with bit manipulation and the operators for them and using tobinarystring is the best I can think of right now, I suppose I will have to browse the binary operators api.
 01242011, 10:16 AM #5Senior Member
 Join Date
 Nov 2010
 Posts
 210
 Rep Power
 4
At the risk of giving too much away, it seems that the << operator is key to this problem.
 01242011, 10:31 AM #6Member
 Join Date
 Jan 2011
 Posts
 13
 Rep Power
 0
Another approach maybe, although not fully proven. For:
round 1: 1 2 3 4 5 6 7 8 12
round 2: 2 4 6 8
round 3: 4 8
round 4: 8
For 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
round1: 2 4 6 8 10 12 14 16 18 20
round2: 4 8 12 16 20
round3: 8 16
round4: 16
Looks like for n = 1, keep doubling n ( same as a shift left ) until n > number of people. The previous position at loop end n/2 or the highest power of 2 < number_of_people is the position you want to stand in.
Java Code:long number_of_people = 21; long n = 1; while( n < number_of_people ) { n = n * 2; } int position_to_stand_in = n/2;
 01242011, 07:27 PM #7Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,565
 Rep Power
 12
the highest power of 2 < number_of_people is the position you want to stand in.
Yes, what I calling "winning" numbers are all powers of 2.
Rather than using loops, remember that there are logarithms available. (And BigInteger has a bitLength() method.)
 01242011, 07:40 PM #8
 Join Date
 Jan 2011
 Location
 Richmond, Virginia
 Posts
 3,069
 Blog Entries
 3
 Rep Power
 8
Alright, I think I got it figured out, so it simply comes down to finding the largest power of 2 that is less than the input.
 01242011, 07:47 PM #9Member
 Join Date
 Jan 2011
 Posts
 13
 Rep Power
 0
Similar Threads

Have I done this exercise right?
By ccie007 in forum New To JavaReplies: 7Last Post: 09282010, 05:54 PM 
Exercise for java 3d
By armiri in forum Java 2DReplies: 2Last Post: 05132010, 11:14 PM 
I/O exercise
By Feldom in forum New To JavaReplies: 1Last Post: 10282007, 04:48 PM 
help with exercise
By e_as're in forum New To JavaReplies: 3Last Post: 09252007, 10:14 AM 
help with an exercise calcuting tax
By e_as're in forum New To JavaReplies: 7Last Post: 08012007, 03:17 AM
Bookmarks