Sunday, November 24, 2013

This week in competitive programming

This week was quite busy in terms of programming contests.

On Tuesday, Codeforces round 213 took place (problems, results, my screencast, top 5 on the left). The contest had some unusual problems, and among them I found the following problem (D) the nicest: you are given a million positive integers, each up to 1012. What is the largest positive integer that divides at least half of those numbers? I couldn't get it at the contest because I came up with only one of the two required insights. Can you solve it?

On Wednesday, TopCoder SRM 597 took place (problems, results, my screencast, top 5 on the left). Both 600 and 900 problems shared the same property: the real algorithmic problem was hidden behind an additional layer of logic which did not make them more interesting but made the statements more complex, so in my view was not really necessary. Here are the simplified statements in case you want to think about them. The 600 problem simply asked to check if all lattice points inside or on the boundary, but not the vertices themselves, of a given convex polygon all lie on the same line. The 900 problem asked to count the number of strings that contain character 'a' A times, character 'b' B times, and character 'c' C times, such that adjacent characters are different.

On Sunday, two ACM ICPC-style contests took place (well, there were probably more, but I'd like to highlight two :)). First, the Northwestern European regional contest (NWERC) took place in Delft (results, top 5 on the left). The strength of this regional varied over the years, but many times really strong teams competed there. This year three out of top five spots were occupied by teams from the University of Cambridge. I don't think they had such strong showings before, and it looks like this result is at least in part due to some Eastern European students with prior IOI and other high school programming contest experience joining the university and organizing trainings and selection. A somewhat similar situation happened to the Oxford University several years ago, where an all-Slovak team called "Marta, Irena & Sirup" earned the university their first ACM ICPC World Finals medal, coming fifth in the world! I think these examples show how important is proper training for ACM ICPC these days, and that it's probably impossible to even qualify for the World Finals without thorough preparation.

Another ACM ICPC-style contest was the All-Russian High School Team Olympiad (results in Russian, top 5 on the left). It is run under ACM ICPC rules, but with one change: instead of university students, this is a contest for high school students. Since there's no international competition for high school teams, this is the highest level these teams can compete in. As high school students are less likely to be fluent in English than university students, the problems are in Russian. This competition is also not as 'serious' as the ICPC, as I believe most of these teams only compete as a team several times a year, and don't run regular training sessions (please correct me if I'm wrong). Are there other countries/regions that run such high school team contests? Please share in comments.

Thanks for reading, and see you next week with the NEERC results!