Ask HN: how do people solve the 3 Google Code Jam problems in 25 minutes?

https://news.ycombinator.com/item?id=801835

by Tichy • 17 years ago

40 27 17 years ago

news.ycombinator.com

If I read it correctly, the leader of the scoreboard submitted the solution for problem A in 7 minutes, problem B 11 minutes later, problem C 7 minutes later. (see http://code.google.com/codejam/contest/scoreboard?c=90101#)

I was expecting some people to be way, way faster than me, but that seems stunning. Can't wait to see what programming language they used.

Me, I tried to solve the problems in Ruby. I am not that experienced with Ruby, so I lost a lot of time debugging. My solution for problem A was too slow in Ruby 1.8 (only 8 minutes are allowed for computation) and only barely made it with Ruby 1.9 - Google Q&A claimed it should be doable in less 8 minutes with Ruby 1.8, though.

In general I had no problems thinking of an algorithm (except maybe some really clever optimization), but I can't imagine coding them in 7 minutes. My solution for problem B is 93 lines long - even just typing it might take longer than 7 minutes...

I did not practice at all - perhaps with more practice of the typical class of problems for such competitions, it becomes more of a copy+paste thing?

nostrademons• 17 years ago

It looked like you could view the problem statement first, and then the timer only starts when you download the input file? If so, then write out the solution in full according to the spec, proofread it, then quickly download the input, run the program, and submit the solution. The total time taken is only what you need for program execution and debugging; I could easily see that coming to 7 minutes if you write fairly solid code to begin with.

I'm really tempted to give a couple of these a try, but I'm not eligible (Google employee - heh, never thought I'd be disqualified from a contest for that reason), and I'd rather work on my compiler. :-)

Tichy3• 17 years ago

No, I think it is the time from the beginning of the project. Once you download the file, you actually only have 4 minutes to submit the solution.

(Edit: I just realized that you could look at the problems without logging in. So maybe time measurements only started from the time the user logged in - then you would be right).

The only thing is that apparently in the beginning there was a problem with the downloads, so Google extended the available time. Maybe they only started counting time one hour later. 1:30 hours would still be very fast, though.

Edit: hm, just thinking, supposing the counting really only started 1 hour later, they could have cheated by letting different people work on each problem. 1 hour per problem seems doable. I don't think the counting really started late, though.

hc• 17 years ago

the timer starts from the time the contest opened (2 Sep 2009 23:00 UTC).

mquander3• 17 years ago

My observations: The contest started at 7:00. I didn't visit the site until around 8:45. My first submissions of problems A and B were around 10:00 (because I couldn't submit the first one thanks to the aforementioned problem.) and my time was marked as 3 hours.

So I think the timer just started at 7:00 for everyone. I agree that 10 minutes per problem is remarkable and intially shocking, but I think it's correct because it's proportional to the times that the same caliber of programmers get in Topcoder matches (where 3 problems of on-average-higher difficulty are presented with a total time limit of 1:15.)

l0nwlf• 17 years ago

In contest like TopCoder I had seen people doing problems in 5 minutes flat. It depends on expertise and regularly solving algorithmic problems (i.e. being in touch). However 3 problems in 25 minutes is awesome !!

mbrubeck• 17 years ago

How fast can you type? Once you've implemented an algorithm enough times, you can almost do it in your sleep. My team at the ACM Intercollegiate Programming Competition had so much practice banging out breadth-first search implementations that we used it for everything we possibly could.

ulvund• 17 years ago

Did you use linear programming solvers ?

marketer• 17 years ago

What's even more insane is that the leader, Neil Wu, is 16 years old.

http://www.topcoder.com/tc?module=MemberProfile&cr=22663...

Alcides• 17 years ago

I really don't find it insane. Young people have much more powerful brains, they just have to learn programming at a younger age. I did it, and I find myself (and others who learnt programming as kids) better programmers than those who learnt in college.

Tichy3• 17 years ago

Is that chart on the bottom of the profile his performance improvement over time? That would be pretty cool, like 3 years ago he was just a normal programmer (a 13 year old programmer, though)... Or is it accumulated points?

mquander3• 17 years ago

It's the former.

holdenk• 17 years ago

I decided to use haskell as it has been awhile since I've touched it, I made the mistake of not compiling with -O for the first question (and it did not complete in the 8 minutes). When I re-ran afterwards (sadly no points) with -O it completed very quickly.

johnfn2• 17 years ago

I'm not familiar with haskell - what is O? Optimization?

Deestan• 17 years ago

Yep.

    $ ghc --help | grep -e "-O"
      -O    An `optimising' package of compiler flags, for faster code

kobs• 17 years ago

The leader is also Neal Wu (http://www.topcoder.com/tc?module=MemberProfile&cr=22663...), one of the top contest programmers in the world.

johnfn2• 17 years ago

A) is completely possible in a few minutes if you have a prewritten permutation function.

for C) I wrote about 30 lines in python - 20 of them file handling - to solve the problem (after a few hours of deliberation). What matters is your speed in figuring out how to write a proper algorithm. The codewriting will not take near as much time.

B) is the one where they surprised me the most. It took me about 150 lines to finish off that beast in about 3 hours, and there are definitely errors in the large output even still. I would love to see how they did it.

Tichy3• 17 years ago

A) true I think I fell just for premature optimization and made my solution too complicated. I assumed that they would pose the problem in a such a way that the naive approach would be too slow.

C) yeah that was the shortest - my first "naive" algorithm was not fast enough, though. I have now thought of a better one and can't wait to try it out, but it is too late for the competition. Still, that alone was worth participating to me - it is a kind of "revelation feeling". I love it when by improving an algorithm a problem becomes solvable.

B) Was actually the easiest for me - the naive algorithm worked well enough. Took me a while to get the program bug free, though...

alexkay• 17 years ago

It also took me awhile to code the correct algorithm for B. I ended up with 60 lines of Python code, and 2 hours :/

All in all, this year's qualification round is much easier than the last's. No real algorithmic challenges, just boring debugging.

mbenjaminsmith• 17 years ago

I got so upset after B) I skipped C), which I was confident I could tackle. My first version of A) worked without issue and I ended up timing out on A.2 because I had overlooked the fact that I couldn't cut and paste the whole result from my terminal.

B) I could solve the sample and the B.1 test case 'looked' like they could have been right but I kept getting incorrect answer on it. It wasn't anything with the dimensions of the map (something I ran into and fixed) so I still can't imagine how you can solve the examples and not solve the test cases.

Kinda fun though...

mquander3• 17 years ago

Regarding:

A) If you're in a language with a good regular expression library, there is a very fast cheesy way ;)

B) I'm equally mystified, I'm satisfied that my solution was correct, but it took 80 lines and multiple passes through the array. I'm impressed that the top tier polished it off in around ten minutes. There must be a fairly simple way.

C) I agree that this one just depends on how quickly you can figure out an algorithm. It's entirely plausible to me that someone with algorithm competition experience has almost literally seen this problem before.

der_ketzer• 17 years ago

I found this today, I think it's worth reading. It's regarding A) http://swtch.com/~rsc/regexp/regexp1.html

RiderOfGiraffes2• 17 years ago

Firstly they ask me to create a Google account, then they ask me to register, including giving all sort of details such as my address and gender, and I get partway through the process and just can't be bothered. I've proved I'm a human, why do they need all this other information?

If I don't win, they don't need to contact me. If I do win, I can prove who I am. Don't make me go through all this crap up front just to what it's all about. I can't bring myself to care.

It's been said over and over before - the same thing goes for your web site. If you want people to visit, don't create barriers. If you want them to participate, don't create barriers. If you want a dialog, make it clear why it's worth participating.

Interesting to see Google think it doesn't apply to them.

lamby• 17 years ago

> If I don't win, they don't need to contact me

Hey, how would they recruit you otherwise?

RiderOfGiraffes2• 17 years ago

I've given them my email, it's the seemly endless remainder of the form I object to, especially asking my gender. Why should they care?

vmanor• 17 years ago

Stupid me tried to start an hour before it ended, found out about it at 4:30 and didn't get home until 5:00. I don't really do these competitions so took me about 2 1/2 hours but still those guys are fast. Here are my thoughts on the problems:

A) Trick was to reverse the problem. Instead of checking if different permutations of the test cases matched the dictionary, see if you can build each dictionary word out of the test case. My python solution finishes the large input in about 6s.

B) Nothing tricky here, like others said it just required some debugging.

C) A dynamic programming problem. Work backwards along the reference string finding the solution to each 'subproblem' using the solution for the character following it. Ran the large input in 0.5s.

manzyuk• 17 years ago

I am curious, what languages did those of you who participated use for your solutions? I have seen Ruby and Haskell mentioned. I downloaded a few solutions of different participants at random, and they all were in C++. I used Common Lisp (and my own small library of utility functions and macros), and it was a very satisfying experience.

jonp• 17 years ago

Of the top ten entries eight used C++ and two used Java. I used Python.

Ask HN: how do people solve the 3 Google Code Jam problems in 25 minutes?

Related Stories