Google Code Jam 2011

daniel_the_smith · **#21**

Li Kao wrote:

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 · **#22**

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

Li Kao · **#23**

daniel_the_smith wrote:

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 · **#24**

Li Kao wrote:

daniel_the_smith wrote:

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 · **#25**

daniel_the_smith wrote:

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 · **#26**

Kirby wrote:

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 · **#27**

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

Kirby · **#28**

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 · **#29**

Nice going, Li Kao!

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

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

Li Kao · **#30**

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?

Li Kao · **#31**

Problem 1 reminded me of that SoS/SoSoS stuff we have in go tournaments. Where did your big solution go wrong?

Problem 2 was much easier than problem 3 IMO.
Once I realized that I can change into a moving frame, i.e. a vendor either stands or moves with 2m/s to the right it became much easier. Contained a trap in form of a 32 bit int overflow, luckily I was careful with the requirements and thus realized that 10^6*10^6 > 2^32 and used long instead. And I also tried with checked arithmetic to be really sure.

Problem 3 was evil. I think I got the room division code correct, but I couldn't think of a nice to implement coloring algorithm. Was planning to do some divide&conquer based stuff, but ran out of time.

Kirby · **#32**

I have not qualified, yet. The first problem from 1B was easy, I think, but I could not figure out the second one (with the hot dog vendors).

I did not even move on to the third one. I didn't end up even making a submission for the hot dog vendor one, either, because I really couldn't figure it out.

Kirby · **#33**

I guess this means I'll be getting up at 5am tomorrow :-p...

Li Kao · **#34**

Kirby what's your language of choice?

And lavalamp have a look at my helper methods. Those speed up coding the parsing a lot. Perhaps you should write similar methods for go.

Kirby · **#35**

My language of choice is C, Li Kao.

hyperpape · **#36**

Can I turn that same question on you, Li Kao and daniel_the_smith?

Li Kao · **#37**

Pure c? wow
How do you manage with all those built in collections, strings,...

I use C# and daniel uses google go/golang.

daniel_the_smith · **#38**

Li Kao wrote:

...Perhaps you should write similar methods for go.

Lol, ok I broke down and wrote another helper

hyperpape wrote:

Can I turn that same question on you, Li Kao and daniel_the_smith?

Yeah, I've been using Go (golang.org). These problems don't really take advantage of Go's main strengths (concurrency), but I find it very quick to write Go code. Honestly I could probably be just as fast in C++ if I wrote a bunch of string parsing functions ahead of time. But I hate dealing with strings in C++. I don't think choice of language really matters for this, as long as you know it well. Though I'm not sure how Kirby manages without STL.

I think even most interpreted languages would be fast enough if you have the right algorithm.

Sigh, for 1C I did exactly the same thing wrong as 1B: try problem C, give up with 20 minutes remaining, start B, finish seconds after the contest ended (although it didn't work).

C small was easy, I did that first. A was easy, too, though somehow I failed A large. :scratch:

I'm certain I could have done B if I had tried it instead of C large (I had an hour and a half left when I started writing C large). So, strategy fail. Again. I guess part of the problem was me underestimating the number of primes < 10e16, causing my "faster" algorithm to also be too slow.

I did get up at 3:40 am, but I don't think that was too much of a factor as I went to bed way early last night. For round 1A, me being tired was a factor in not solving anything--it was at 8pm my time, I'd programmed all day at work and not gotten much sleep the night before. None of the problems even made sense to me, hehe.

I'm really not used to solving these sorts of problems with time pressure. Maybe I'll actually practice before attempting it next year. :mrgreen:

I thought problem C from round 1B was the most interesting (catnip flavors)-- but my recursive room dividing algorithm didn't work and I didn't have time to fix it.

daniel_the_smith · **#39**

Li Kao wrote:

Problem 1 reminded me of that SoS/SoSoS stuff we have in go tournaments. Where did your big solution go wrong?

Gah, I should have been more curious and figured it out, it's the same thing that killed my A large solution for 1C-- golang's buffer.ReadLine returns a slice of its buffer, so for datasets larger than the buffer I need to make a copy, not store it directly (facepalm). The irritating thing is I knew this and figured I'd change it when it caused a problem. But the small data fit in the buffer completely, and the large output wasn't obviously wrong... grrr So... I'm dumb, in an irritatingly stupid way...

Well, it wouldn't have been enough to get me in the top 1000 for either one, I think. But at least I would have been in the middle of the pack and not the bottom!

Kirby · **#40**

Well, I valued sleep more than getting up this morning to participate in 1C. So I'm out, now. Good luck to you guys as you advance.

Google Code Jam 2011

Who is online