Life In 19x19
http://www.lifein19x19.com/

Google Code Jam 2011
http://www.lifein19x19.com/viewtopic.php?f=8&t=3808		 Page 1 of 3
Author:  Kirby [ Fri May 06, 2011 9:05 am ]
Post subject:  Google Code Jam 2011
Google code jam will commence shortly:
http://code.google.com/codejam/

If you're interested in programming, these competitions are sometimes fun.
Author:  daniel_the_smith [ Fri May 06, 2011 10:04 am ]
Post subject:  Re: Google Code Jam 2011
Thanks, I think I'll give it a shot...
Author:  Li Kao [ Fri May 06, 2011 11:48 am ]
Post subject:  Re: Google Code Jam 2011
The two sample programs for the qualification round looked very easy to me. Parsing the input file is probably harder than solving the actual problem. So I guess I'll put in a few minutes tomorrow to solve them. No idea if I have the time/brain for the later rounds :P
Author:  Sevis [ Fri May 06, 2011 1:23 pm ]
Post subject:  Re: Google Code Jam 2011
I'm going to be participating, but seeing as my algorithms' complexity is usually best represented with up arrow notation, I doubt I'll get through the qualification rounds.
Author:  Li Kao [ Fri May 06, 2011 3:40 pm ]
Post subject:  Re: Google Code Jam 2011
The round 2 problems on the other hand are evil. I just tried last year's bacteria problem. Wrote by program, and it worked. The limits said that the initial configuration has at max 1M bacteria on a 1Mx1M field.
What they didn't say that the number of bacteria grows far beyond 100M in some of their testcases. Out of memory :( And once you have that testcase you just have 8 minutes to submit the solution.
Author:  hyperpape [ Fri May 06, 2011 3:56 pm ]
Post subject:  Re: Google Code Jam 2011
The qualification problems did look remarkably easy. Which is a way of saying that I think I might have had a chance at solving them.
Author:  SpongeBob [ Sat May 07, 2011 3:42 am ]
Post subject:  Re: Google Code Jam 2011
Is it only possible to see the problems via registering?
Author:  daniel_the_smith [ Sat May 07, 2011 7:55 am ]
Post subject:  Re: Google Code Jam 2011
Yes, but you can see problems from prior events.

What are people's handles there? I'm lavalamp if you want to add me to your scoreboard. :mrgreen:
Author:  Li Kao [ Sat May 07, 2011 1:37 pm ]
Post subject:  Re: Google Code Jam 2011
Finally done. nick: CodeInChaos

My thoughts about Problem D:

Google = Image
I probably put more work into Problem D than into the rest together. F**ing trolled.
Author:  daniel_the_smith [ Sat May 07, 2011 2:14 pm ]
Post subject:  Re: Google Code Jam 2011
In two hours when it closes, please please please explain to me what rabbit trail you were following, it's driving me nuts. I was super extra careful on D, but only because I could see half the people were getting it wrong-- figured it was a trick question... What are people so commonly doing that is wrong? C was way harder, I thought.

...plus the large input for C triggered a condition in my parsing code that I didn't handle initially... that was fun, having to fix it with the clock running...

I looked at some of the questions for earlier round 1's-- I don't expect to make it to round two. Some people were submitting answers in the time it takes me just to read the problems... :/
Author:  Kirby [ Sat May 07, 2011 2:27 pm ]
Post subject:  Re: Google Code Jam 2011
I thought C was harder than D, as well. I actually ran out of memory on C :-p.
Author:  daniel_the_smith [ Sat May 07, 2011 2:35 pm ]
Post subject:  Re: Google Code Jam 2011
Kirby wrote:
I thought C was harder than D, as well. I actually ran out of memory on C :-p.


Really? Wow, we must have had completely different solutions...
Author:  Kirby [ Sat May 07, 2011 3:14 pm ]
Post subject:  Re: Google Code Jam 2011
My algorithm was kind of basic. I got a list of all permutations of the candy values for a particular set. Then, for each of those permutations, I split the set of candy values into two sets, drawing the line at (1, n-1), (2, n-2), etc.

For each of these set divisions, I took the bitwise XOR of the values in the sets, and saw if they were equal. If they were equal, I grabbed the real sum of the set, and kept track of the maximum.

This seemed to work for the sample input I used before trying to submit, but when I got a larger dataset, I had some memory errors due to some arraylist cloning that I was doing. I'm assuming there's either a bug in the code i wrote to get all of the permutations, or I'm doing something inefficient in that method.

I guess I could still work on the problem, as there's still time to investigate it, but I'm not too worried about it since you only need 25 points this round to qualify.
Author:  Li Kao [ Sat May 07, 2011 3:28 pm ]
Post subject:  Re: Google Code Jam 2011
Kirby what's your nick there?

The majority seems to agree that ProbD is hardest. At least it has by far the least correct solutions.
Author:  daniel_the_smith [ Sat May 07, 2011 3:33 pm ]
Post subject:  Re: Google Code Jam 2011
Lol, after reading Kirby's description I realized that anyone reading my code for that problem is going to have a major WTF moment.
Author:  Li Kao [ Sat May 07, 2011 3:36 pm ]
Post subject:  Re: Google Code Jam 2011
Just noticed that the number 9 in the highscore is called "Weiqi" :)
Author:  Li Kao [ Sat May 07, 2011 4:00 pm ]
Post subject:  Re: Google Code Jam 2011
I thought C was the easiest of all. At least I instantly had the right idea for it.
The broken adding is equivalent to binary xor. Then xoring all in A and xoring all in by and setting that equal is equivalent to xoring everything and setting it to zero. How you divide the among the heaps doesn't matter at all. You just need to make sure the heaps aren't empty, i.e. give the other guy the cheapest item.

B posed no problems either, it's just implementing the requirements.

And in A I had a stupid off-by-one error which lead to my two wrong submissions.

And problem D. I didn't realize that the number of items which aren't sorted yet equals the expectancy value. So I devised some complicated recursive memoizing algorithm. Fed the number of unsorted items into it. And it simply returned what I fed it with. T_T
My algorithm started with the number of items-to-sort, then calculated the individual probabilities for how probably each number of items-to-sort after the move is. Then there was the additional problem that no progress might be made at all, but I can't recurse without a change in parameters since that recurses infinitely. So I used the rule for geometric sums to fix it.

--------

Everything correct for me, Lavalamp lost 15 points.
Author:  daniel_the_smith [ Sat May 07, 2011 4:13 pm ]
Post subject:  Re: Google Code Jam 2011
OK, it's over now :)

I had a brain fart and got XOR mixed up in my head. On a related note, I now know how to do an XOR using bitwise or, and, and not.

My solution for C is like Kirby's, but:
* I used an array of bools to count off the permutations; a true in the array meant the number was in pile A, false meant it was in pile B. So, just one tiny allocation.
* I kept a sum and an XOR sum for each pile, every time I changed a bool I updated both piles.
* That's an O(2^N) algorithm, but it solved the first data set just fine (after I added the condition that neither pile be empty, duh).
* To solve the large data set, I added the optimization that if either pile XOR'd to 0 at any point, I can remove the whole pile from consideration and add its value to the largest equal pile. Then I noticed that if pile B ever XORs to 0, I'm already done.

I'm still not sure if there's a data set that could have broken this. I think that it can only "cancel out" groups of numbers with the same bits set-- I think with the numbers all less than 1e6, it will be fine.
Author:  Li Kao [ Sat May 07, 2011 4:21 pm ]
Post subject:  Re: Google Code Jam 2011
Both problem C and D become extremely short once you have the right idea.

Problem C:
Code:
int accu = 0;
int count = ReadLine().ToInt();
int[] values = ReadLine().Split().ToInt();
Debug.Assert(values.Length == count);

//xor all of them
foreach (int value in values)
   accu ^= value;

Write(CaseStr + " ");
if (accu != 0)
      WriteLine("NO");
   else
      WriteLine(values.Sum() - values.Min());//Take everything but the lowers item


Problem D:
Code:
int count = ReadLine().ToInt();
int[] initial = ReadLine().Split().ToInt();
Debug.Assert(initial.Length == count);
int wrong = initial.Where((v,i) => v != i + 1).Count();
WriteLine(CaseStr + " " + wrong.ToStringInv());


But how did you find the solution for Problem D? It's not obvious to me that the number of unsorted items equals the expected number of turns.
Author:  daniel_the_smith [ Sat May 07, 2011 4:29 pm ]
Post subject:  Re: Google Code Jam 2011
Li Kao wrote:
I thought C was the easiest of all. At least I instantly had the right idea for it.
The broken adding is equivalent to binary xor. Then xoring all in A and xoring all in by and setting that equal is equivalent to xoring everything and setting it to zero. How you divide the among the heaps doesn't matter at all. You just need to make sure the heaps aren't empty, i.e. give the other guy the cheapest item.


Ah, good point. If I'd realized it was an XOR maybe I would have noticed that. :oops:

Li Kao wrote:
And problem D. I didn't realize that the number of items which aren't sorted yet equals the expectancy value. So I devised some complicated recursive memoizing algorithm. Fed the number of unsorted items into it. And it simply returned what I fed it with. T_T
My algorithm started with the number of items-to-sort, then calculated the individual probabilities for how probably each number of items-to-sort after the move is. Then there was the additional problem that no progress might be made at all, but I can't recurse without a change in parameters since that recurses infinitely. So I used the rule for geometric sums to fix it.


Yeah, D was a math problem, not a programming problem... N * ((N-1)! / N!) = 1

Li Kao wrote:
Everything correct for me, Lavalamp lost 15 points.


Yeah, I just ran another large data set through it and it failed that one, too... hm...
Page 1 of 3 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/