This week in competitive programming

At the end of last week, the Fourteenth Open Cup has started. The Open Cup format is similar to the tennis rankings or to the cross-country skiing/biathlon world cups: there are about two five-hour contests each month, and you get 100 points for the first place, 80 points for the second place, ..., 1 point for the 30th place. Then your scores from different contests are added up and the team with the highest total score wins the cup. It started as a competition for Russian teams, but more and more teams take part each year, including veteran teams like my team.

Last Sunday, the first stage took place: results. You can see top 5 to the left. The problemset was composed by the St. Petersburg State University coaches, and it had a few very nice problems. One surprising problem was: you are given N vectors in D-dimensional space. How many different 2-dimensional planes do they induce? Mathematically, this isn't really a problem - each pair of vectors defines a plane, and we should count the number of different planes among them. But how to check if two such 2-dimensional planes in D-dimensional space are the same plane? I'll tell my approach in a later post.

This Sunday (today), the second stage took place: results. Again, top 5 is on the left. This time the problemset was taken from the South-Eastern European Regional Contest, the ACM ICPC regional for Ukraine, Romania and neighboring countries. The Open Cup teams performed much better than the teams participating in the regional itself - the winner of the regional, SobolevTeam from Kharkov, placed tenth in the Open Cup. The problemset was composed by people from many different universities in the region. Here's one problem I enjoyed: you are given three non-negative numbers up to 10^18: A, B and S. At each step, you can replace either A or B with A+B. Is it possible to make at least one of A or B equal to S? Again, will share my solution later, feel free to discuss the problem in comments.

After two stages, three teams are close at the top of overall standings: tourist and SPb SU 4 have 160 points each (60 + 100 for tourist, 80 + 80 for SU 4), then my team has 150 points (100 + 50).

Finally, later today Codeforces Round 206 took place. I didn't take part and didn't have a chance to read the problems yet, so I can only admire rng_58's yet another commanding win. Congratulations!

Thanks for reading, and see you next week!