Google Code Jam 2011

[Kirby]

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]

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

[Li Kao]

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]

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]

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]

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]

Is it only possible to see the problems via registering?

[daniel_the_smith]

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.

[Li Kao]

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]

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]

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

[daniel_the_smith]

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]

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]

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]

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