Google Code Jam 2011

Kirby · #1

Google code jam will commence shortly:
http://code.google.com/codejam/

If you're interested in programming, these competitions are sometimes fun.

daniel_the_smith · #2

Thanks, I think I'll give it a shot...

Li Kao · #3

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

Sevis · #4

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.

Li Kao · #5

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.

hyperpape · #6

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.

SpongeBob · #7

Is it only possible to see the problems via registering?

daniel_the_smith · #8

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:

Li Kao · #9

Finally done. nick: CodeInChaos

My thoughts about Problem D:

Google =

I probably put more work into Problem D than into the rest together. F**ing trolled.

daniel_the_smith · **#10**

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... :/

Kirby · **#11**

I thought C was harder than D, as well. I actually ran out of memory on C :-p.

daniel_the_smith · **#12**

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

Kirby · **#13**

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.

Li Kao · **#14**

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.

daniel_the_smith · **#15**

Lol, after reading Kirby's description I realized that anyone reading my code for that problem is going to have a major WTF moment.

Li Kao · **#16**

Just noticed that the number 9 in the highscore is called "Weiqi"

Li Kao · **#17**

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.

daniel_the_smith · **#18**

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.

Li Kao · **#19**

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.

daniel_the_smith · **#20**

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

Google Code Jam 2011

Who is online