Results 1 to 9 of 9
  1. #1
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default 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));
    		}
    	}
    }
    Unfortunately it is not efficient enough since it has so much to do every time a number is input. Once it is expected to work on numbers over 1 million it takes a few seconds or more. I am trying to make this more efficient, unfortunately I cant think of a way to manipulate numbers alone and the easiest way for me is to populate an arraylist then make changes. Any help on, I guess, the number theory to solve this problem?

  2. #2
    aspire1 is offline Member
    Join Date
    Jan 2011
    Posts
    13
    Rep Power
    0

    Default

    Google the Josephus problem, that's what it looks like.

  3. #3
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,585
    Rep Power
    12

    Default

    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
    Notice how the first round losers (1,3,5,...) all end in a 1.

    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; 01-24-2011 at 01:41 AM.

  4. #4
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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.

  5. #5
    Iron Lion is offline Senior Member
    Join Date
    Nov 2010
    Posts
    210
    Rep Power
    5

    Default

    At the risk of giving too much away, it seems that the << operator is key to this problem.

  6. #6
    aspire1 is offline Member
    Join Date
    Jan 2011
    Posts
    13
    Rep Power
    0

    Default

    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;
    Although of course I could be wrong :)

  7. #7
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,585
    Rep Power
    12

    Default

    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.)

  8. #8
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    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.

  9. #9
    aspire1 is offline Member
    Join Date
    Jan 2011
    Posts
    13
    Rep Power
    0

    Default

    At first appearance that's what it looks like, although to correct myself, it should be <= input I think rather than < input.

Similar Threads

  1. Have I done this exercise right?
    By ccie007 in forum New To Java
    Replies: 7
    Last Post: 09-28-2010, 06:54 PM
  2. Exercise for java 3d
    By armiri in forum Java 2D
    Replies: 2
    Last Post: 05-14-2010, 12:14 AM
  3. I/O exercise
    By Feldom in forum New To Java
    Replies: 1
    Last Post: 10-28-2007, 05:48 PM
  4. help with exercise
    By e_as're in forum New To Java
    Replies: 3
    Last Post: 09-25-2007, 11:14 AM
  5. help with an exercise calcuting tax
    By e_as're in forum New To Java
    Replies: 7
    Last Post: 08-01-2007, 04:17 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •