The Google Code Jam competition is one of the largest in the world and is held annually with over 50,000 participants, about half of whom pass the qualifying round. This year 26 finalists competed for the $15,000 prize. Gennady Korotkevich, as the winner of the previous year’s competition, didn’t have to participate in the qualifying rounds.
The competition is organized in such a way that the participants solve problems made of two parts: a small input and a large input. The small input is usually easier, as a less complicated algorithm is required and there are less constraints. As soon as the answer is submitted, the programmer immediately finds out if the answer is correct or not, and can change it if necessary. Then they are allowed to solve the large input, which requires more complex algorithms and the answers to which are judged only after the contest ends, meaning that participants don’t know if they gave the correct answer until the award ceremony. Another special feature of this particular competition is that the competitors may use any programming language and development environment to obtain their solutions.
This year, the Google Code Jam finalists had six problems to solve. According to the official analysis of the contest, the majority of participants first solved the easier half of the problems and then started going through the second, harder part. At the end of the round, the organizers went through all the answers and results were updated in real time in front of all the participants. Gennady Korotkevich took first place for the fourth time in a row, receiving 120 points out of a possible 200. Evgeny Kapun, took fourth place, with 100 points. Gennady Korotkevich didn’t complete a single problem during the first 2.5 hours, but in the last 1.5 hours he submitted one answer after another.
“The first two and a half hours I was reading and trying to understand all the problems. It became immediately clear what to do for the A and B problems, so I could put them aside. I answered problem C, but then spent most of the time thinking over the last problem. I generally knew that I needed about 1.5 hours to write and send all the answers. For example, I had to write one of the answers in Java, and there was also a problem of computational geometry which requires a very thorough code. The most difficult problem for me to solve was the airplane travel problem. A flight route between airports was given and it was necessary to check that the route circumnavigates the earth, that is that it touches every possible hemisphere.” commented the winner.
The competition also takes into account the total time taken to complete the problems: for example, the second, third and fourth winners each got 110 points.
Gennady Korotkevich is a two-time winner of the ACM ICPC international world championship on programming (2013 and 2015), just like Evgeny Kapun (2009 and 2012).
“I usually try to solve the more challenging part of the problem first, the “larger input” part. This year, however, I couldn’t solve the more difficult parts of the three last problems in the first two hours, and so I decided to solve the “easier” parts. In this situation I thought that one of the other finalists will solve the more challenging parts, and would get more points than me” - says Korotkevich explaining his tactics when participating in Google Code Jam.
The Distributed Code Jam competition also took place in Dublin, which Google organized for the third time in a row. The problems in this competition are similar to the traditional Code Jam, but programmers can only use distributed computing to solve the problems. Distributed computing means running several processes on different computers connected to one system. As with the normal Code Jam, Distributed Code Jam is focused on developing the necessary skills for working in large IT companies like Google. The winners of the championship receive a $10,000 prize.
This year, there were 21 finalists and Evgeny Kapun took second place, with 49 points out of a possible 100. Pavel Mavrin (ACM ICPC winner in 2004), tutor at ITMO’s Computer Technology Department, took fourth place with 48 out of 100 points. He managed to solve two problems (both parts), and also the easier parts of the third problem. The overall champion took the prize with 59 points.
“Preparing for the competition was quite challenging.The competition has a really specific structure, meaning that one can't just replicate the solution on a computer and see if it works. That’s what makes it interesting! While not incredibly challenging, I liked the question about a robot on a grid. In each cell of the grid there was an arrow pointing up, down, right or left. The robot can start in any cell and will move according to the arrows, which means that at some point it will either fall off the grid or enter a loop. You have to replace a few arrows with an end spot so that no matter where the robot starts it’ll end up at the finish line. It’s easy to solve such a task on a small grid but on a 30,000 x 30,000 cell grid it’s much hard” commented Pavel Mavrin.
According to the analysis, the first two problems of the competition were solved by almost all participants, while the more challenging parts, the fourth and fifth problems, were left unsolved. The organizers have noted that the skills of Distributed Code Jam’s finalists are increasing each year.