Google Code Jam 2011

[Li Kao]

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

[Li Kao]

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]

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]

Both problem C and D become extremely short once you have the right idea.

Problem C:

Code: Select all

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: Select all

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]

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.

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

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

[daniel_the_smith]

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.

Given N items in the wrong position, the probability that item 0 will get randomly dropped into the right spot is (N-1)! / N! . But you have N slots, so N chances, and N * (N - 1)! == N! , so it reduces to N!/N! == 1 correct item per shuffle. I did spend a lot of time convincing myself that this was so, because it seemed too easy.

EDIT: All the other write-ups of this problem are saying the probability is 1/N, which, now that I think about it, is what (N-1)! / N! reduces to...

[daniel_the_smith]

Gah, on B I didn't realize that an element can be opposed to more than one element. I'm dumb.

[Li Kao]

Gah, on B I didn't realize that an element can be opposed to more than one element. I'm dumb.

Can't say I really realized that too. But since I stored that stuff in a list of pairs it dealt with it automatically. If I had optimized it with a dictionary I might have fallen for the same trap.

[daniel_the_smith]

Gah, on B I didn't realize that an element can be opposed to more than one element. I'm dumb.

Can't say I really realized that too. But since I stored that stuff in a list of pairs it dealt with it automatically. If I had optimized it with a dictionary I might have fallen for the same trap.

Yeah, I used a map. I also tracked how many of each opposable element were on the stack, so I didn't have to search back whenever a new one got pushed. I suppose that would have mattered if the stack got to be mb's of data. A bug in this caused my incorrect small data set, so basically it was just plain not a good idea...

[Kirby]

Gah, on B I didn't realize that an element can be opposed to more than one element. I'm dumb.

I almost fell for that, but I am kind of a stickler on the input descriptions.

I think that it might have been an intentional trap, because none of the sample inputs on the problem description page had multiple combine or oppose element sets.

[daniel_the_smith]

I think that it might have been an intentional trap, because none of the sample inputs on the problem description page had multiple combine or oppose element sets.

Not only that, the small input won't trigger it either. Evil!

[Kirby]

Well, I guess we have two weeks to practice for the real thing!

[Kirby]

17 minutes to round 1A. I probably won't have time to participate in round the other two for this weekend, so I'll try to make this one count...

I had a dream about failing, though.

Either way, have fun, everybody.

[daniel_the_smith]

Nice going, Li Kao!

I decided to tackle C instead of B, had bugs and ran out of time.

...and I see I failed A large. Sigh.

[Li Kao]

Got 55 in round 1B, so I'm qualified unless they decide to deduct some points. The cats problem would have taken me much longer to code...

Lavalamp didn't do so well

Did you take part/qualify yet kirby? And what's your nick there?