Tuesday, May 6, 2014

This week in competitive programming

The week started with the final round of the Kotlin Challenge (problems in Russian, results in Russian, top 5 on the left). The competition took place onsite in the JetBrains office in St Petersburg, and featured just 25 best competitors. In the end, the round was decided on the following problem: you are given an arithmetic expression containings integers, operations "+","-","*","/", parentheses, and at most three occurrences of variable "x". The expression has at most 500 characters. Is there a real value of x that leads to a division by zero in this expression?

On Saturday, Google Code Jam Round 1B gave the second chance to qualify to Round 2 (problems, results, top 5 on the left). I couldn't follow this round, because it was in the middle of ...

Challenge 24 (problems, results, top 5 on the left)! The final 24-hour round for the top 30 teams took place in Budapest from 9am Saturday to 9am Sunday. As usual, the round featured many different types of problems, requiring very diverse skills from the competitors. The winning team, PrecisionScrewdrivers from Poland, found an edge by getting the maximum score of 4000 in problem B which required understanding and improving a large program in a functional language - congratulations! (photo below from the official site)

Here's one of the problems I've enjoyed a lot (problem L): you are given a dump of the OpenStreetMap's road graph of the Earth - about 700 million nodes (id + latitude + longitude) and on the order of one billion edges, two gzipped text files taking about ten gigabytes in total. Then, you're given ten pairs of nodes in this graph and are asked to find any path from the first node to the second one. The time limit is on the order of minutes or even hours - you run this on your own machine and submit the paths. The difficulty of this problem changes greatly depending on the amount of RAM you have. In our case the laptop with most RAM had 8 gigabytes, so we had to work inside that limit. What would you do?

No comments:

Post a Comment