In addition to the disclaimer, one thing which worried me was the N <= 1000 in the large problem specification. I got a quite elegant fast solution and a so low bound was really surprising.
My solution for 4 was quite efficient in design (and very simple). I was able to be very inefficient in the rough implementation (being lazy and copying arrays, reading the entire input file at once and breaking it up into lines in memory) and still, using JS, solve the large set in only a few milliseconds.
That should probably be a few orders of magnitude higher to realistically make the time constraint remotely difficult.
This was a fun problem to think about, though. Naomi is such a cheater.
Yeah, that disclaimer scared me off at first. I solved D last, but in the end I do feel that it's easier than C. I suppose you can solve C-small with a more naive method though.
The odd thing is, though, I still don't really see how you can solve C-small without solving C-large at the same time (other than actual brute-force). Guess I'll be keeping my eyes peeled for the write-up.
I'm always amazed at the speed of these guys. Top guy got it all done in an hour. I don't know if they are geniuses or if they practice this stuff every day.
Speaking as the current #20 position [0] on the Google Code Jam scoreboard...
I'm in my university's team for the ACM ICPC [1]. We practice about one or two times per week, where each practice session is 5 hours. Some of the stronger programmers really practice this stuff every day. cf. Nick Wu's description of his preparation for programming contests [2].
[0] In 5 hours, the large input sets will be judged. I might move up or down the rank list depending on whether my answers for the large input were correct.
If you don't mind me asking, how do you guys? I always compete in my university's "local" contest, which is basically a tryout for competing for a spot on the team that goes to the ACM. I try doing practice problems, but when I can't solve one, I'm not sure where to go from there.
It just takes a bit of practice. Once you've seen a certain type of problem before, it is easy to identify other problems that can be somehow reduced to a known problem. Speed comes with practice too... soon, basic constructs like for-loops just get etched into muscle memory. Don't worry, I couldn't even solve a single problem in my first tryout at my university.
At my university, after a practice session, we sometimes discuss solutions to problems so that those who couldn't figure them out will know how to solve them in the future. After being told the solution to a problem you couldn't solve, you should try coding it up anyway.
First place was taken by Gennady.Korotkevich, also known as "tourist." He has a history of placing extremely highly in sport programming contests[0], is at the top of topcoder's algorithm section[1], and has had several articles[2,3] written about him.
I imagine there's a lot of practice involved, but I wasn't able to spot an interview that specified the exact amount of time tourist spends coding or studying algorithms every day.
Three to four hours of practice a day is quite a lot, in comparison Johnny Ho (http://www.quora.com/TopCoder/Who-is-Johnny-Ho) only did about 1 or 2 a day while practicing for IOI 2012
Source: me asking that exact question to him at IOI 2012
"Not more than three to four." != "Three or four hours practicing every day consistently"
Also, this guy has been performing at an extremely high level for years. If he didn't do any competitive programming practice at all for a year, I doubt you'd notice a big difference in his performance.
Some of the top guys at Topcoder Open / Google Code Jam don't even participate in matches outside of the yearly tournament and I doubt they are practicing consistently (i.e. once you get to that level at problem solving, performance doesn't seem to decay much and certainly much less than in a similar situation for athletes - though these guys are students / engineers whose brains are still being stimulated and solving other kinds of problems outside of competitions).
Just a thought: I supposed many of them are in fact very smart people. Hours of practice certainly helps a lot as you can break down a complex problem into smaller and familiar problem sets. Some people like Nick Wu probably isn't your average student. Also luck plays a major part. If you just happen to know how to solve problem X you can solve it quickly.
"I don't know if they are geniuses or if they practice this stuff every day."
It's not an either/or question though =) By most common definitions, the guys at the top, specially those that reach the finals are "geniuses" at algorithmic problem solving, yes.
I have a suspicion that they have solved thousands upon thousands of these problems, developing a library of sorts. They can probably translate these problems into ones they have solutions for and just work from there.
I think it is a feat to practice to the point of having seen thousands of problems and still know (or have a felling of) the way to go.
(Actually, most of the good sport coders that I know develop that knack of knowing where the solution is headed, without pinpointing a previous problem)
Well, looks like 20,594 people made it through the qualification round. Higher than last year, when 17,054 people made it:
http://www.go-hero.net/jam/13/round/0
I disagree. Unlike other years, there is no "hard" problem in this round. So far, 2581 users have submitted an answer to C-large (the "hardest" this year). Last year only 547 users submitted an answer to D-large (and only 141 got the correct answer).
That's what I thought initially as well, but in the end I ended up solving more than last year or the year before. I felt like I wasn't going to get anything after A and B at first, though.
It's my first time this year, I can't understand why my answer for the mine sweeper is not correct. I think I found all the edge cases and even checked my results one by one :(
You'll find the same countries consistently at the top: Russia, Poland, Belarus, Ukraine (i.e. Eastern Europe) and China, Japan (i.e. East Asia) as well as a few others. No news here.
Regarding "but if you go to the last page, there are a bunch of them trying", this is also a function of how many "bad programmers" participate. There's no way to tell whether bad Polish or US programmers filter themselves out of these competitions but Indians not so much.
There's not really much difference between the top 1000 places, since all that matters is solving all 4 problems. This is the qualification round that goes on for 27 hours, so there is not much pressure to solve the problems fast. The Indian programmers are in a time zone that makes it difficult to get up at 4:30am just to solve the problems a bit faster.
Comparing the performance in the next few rounds would make more sense.
Wait, do the results from each round make a difference in subsequent rounds? I didn't take the time to implement a solution to problem C because I felt like it would take too long.
What kind of reasoning is this? How is performing in a programming competition like Code Jam an indication of whether you are a good developer or not? Unless of course if you just want to hate on outsourcing, in which case, go ahead and do it but please don't try to make it sound like you are basing yourself on logic.
Performance at Google Code Jam != Ability as a software developer, for sure. However, being unable to solve a couple of the simple qualification round problems in a language of your choice with no time pressure is a strong negative signal (for reasoning and/or coding skills that are essential to any software developer).
I'm American, but this kind of statement pisses me off: just because some people from India didn't perform well in the Google Code Jam, we shouldn't hire them?
Looking above (dllu's comment) a significant factor in success at these competitions is practice. There's a good chance a lot of these folks are just students trying this for kicks. Basically, its really unclear how much self selection goes on with these contestants.
Genuinely "trying" here means genuinely practicing; its unlikely that you would fail the first round if you practiced
There are a lot of people who've only solved a single problem, and the ranking will tend to cluster people from the same timezone together (even if they eventually solve more problems)
Also, competitive programming contests are really popular at Indian schools, so a lot of these could be HS students (nothing to back this up, though - they don't publish this information)
I assume outsourcing is done to save money. The amount it would cost to have each developer get their answer would be interesting to me, and would remove the perceived racist element too.
