This week in competitive programming

This week wasn't too heavy with open programming competitions, with just TopCoder SRM 595 early on Friday, in the famous "5am" slot (for Moscow time zone) that has traditionally separated dedicated programming contest participants from casual ones :)

Here are the problems, results; top 5 is on the left. I've managed to solve the hardest problem very quickly because it relied on one of my favorite methods - using linearity of expectation, or, in other words, that the expected value of the sum of random values is equal to the sum of their expected values, even if the random values are dependent. I won't give more details for now so that you can try to discover the actual solution yourself. Here's the problem statement: you are given 50 points on the plane, with each point assigned a probability that it exists. Existence of different point is independent. What is the expected area of the convex hull of existing points?

There were also some more ACM ICPC competitions this week, the most notable (at least to my knowledge) being the NEERC Northern Subregional contest, featuring the best teams from St Petersburg and surroundings. Here are its results, top 5 is on the left.

SPb SU 4 leads the field by just one problem, but such small gap doesn't really do them justice - for example, after 3 hours they led 11 problems to 8. Looking at other recent competitions - for example the Moscow Subregional or the two Open Cup stages I mentioned earlier, it becomes clear that they're probably the strongest Russian ACM ICPC team this year by far.

The Northern subregional not just confirmed that they are very strong, which we already knew, but it confirmed that they are participating in ACM ICPC this year - something that was not certain until the very last moment, as they considered to skip this year to get more practice and get better results next year (since each person is allowed at most two ACM ICPC World Finals participations, and they've been there this summer, they have just one attempt left). The Northern subregional has also confirmed that Gennady Korotkevich (tourist), who's number one in all ratings right now, the current ACM ICPC World Champion, and who has beat SPb SU 4 on many occassions, is indeed not taking part in ACM ICPC this year, leaving the way clear for SPb SU 4.

Of course, no offense meant to other Russian teams - but right now SPb SU 4 look to be the main contender for the world championship from Russia. I don't have a good picture for other countries, though - please share what other strong teams have been formed in commments! In particular, do teams from the University of Tokyo and from National Taiwan University who got gold medals this summer compete again?