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 10¹². 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!

This week in competitive programming

Tuesday and Wednesday were the days of TopCoder Open semifinals and finals. The final results are on the left, here's a link to problems. I had a very nervous wait for the final results because peter50216's successful challenge (on tourist's hard) meant he would be first if my hard failed as well. Luckily, it didn't fail, although it was very close - it took 1.5s out of 2s to run on some testcases.

Here's what the decisive hard problem from the finals boiled down to (link to full problem statement): you are given a NxN (N<=50) grid with some cells black and some cells white. How many ways are there to place non-intersecting T-tetraminoes onto the grid such that each "central" cell of a tetramino falls onto a white cell, and each white cell is the central cell of some tetramino? You need to find this number in O(N^2). I will try to write about the solution later this week, so that you have some time to try solving it yourself.

I've been thinking what was different this year that has allowed me to win. Obviously, this could be completely random, but that's not too interesting to think about :) One difference is Gennady's presence in the finals, that did certainly add motivation. Another possibly important thing is: Egor has convinced me to go and watch an ice hockey game, Capitals vs Blue Jackets, on the night between the semifinal and the final. Looking at my 1st place and his 3rd place, such a distraction might actually be a positive thing.

On Sunday, the fourth Open Cup stage took place, top 5 on the left, here's a link to full results. As far as I know, the problems for this stage were taken from the Polish ICPC quarterfinal, so we can compare the Russian teams with the Polish teams - Polish results are here. Judging from this contest only, it looks like SPb SU 4 is still the best contender for this year's World Finals among the teams I know.

Speaking of Polish teams, the Central European Regional Contest of ACM ICPC took place on Sunday, too (here's a link to final results, top 5 are on the picture). The top 3 are quite similar to last year's with the Warsaw team suprisingly losing 1 problem to Comenius and Jagiellonian. However this didn't stop the Warsaw team from becoming the best team from Central Europe at the World Finals, and I would still expect them to be an important player in the World Finals this year.

Most other regionals have already happened during the first two weeks of November, you can find their results on the official ICPC website: link. I don't want to paste all those results here, but please tell if there's something particularly interesting in there that I should discuss here! The regional which gave us the last two world champions, NEERC, is going to happen on December 1st in St Petersburg.

TopCoder Open 2013 Algorithm Finals day

The main event of the TopCoder Open - the algorithm finals - takes place today. Just 8 competitors, pictured above, will compete for the title. In the order of pictures: cgy4ever (China), Egor (Russia), peter50216 (Taiwan), Petr (Russia), rejudge (China), sdya (Ukraine), tourist (Belarus), wata (Japan).

There will be lots of live coverage. First of all, misof will continue his play-by-play commentary and problem analysis - check out his commentary for previous algorithm rounds here: http://apps.topcoder.com/forums/?module=Thread&threadID=803508. The link for the finals will appear in that forum thread, too. Moreover, there will be live video broadcast with John Dethridge at http://community.topcoder.com/tco13/overview/movies/live-streaming/. And of course there will be live coverage on SnarkNews (http://snarknews.info/), which appears to be down right now but will hopefully come back soon. Here is the translation of the cached version of SnarkNews TCO stats: link.

The finals start at 1pm Washington time. Starting time in other timezones: http://www.timeanddate.com/worldclock/fixedtime.html?msg=TopCoder+Open+2013+Algorithm+Finals&iso=20131113T13&p1=263&ah=2. The live video broadcast will start 30 minutes earlier.

(all pictures from the official TopCoder Open website)

TopCoder Open 2013 Marathon competition

Today's main event at the TopCoder Open is the Marathon Match finals. This year, the competitors are implementing resource harvesting strategies in a Starcraft-like setting - check out Rustyoldman's blog that actually has links that allow you to download the visualizer and start experimenting with solutions yourself! I think the problem this year is awesome - the problem statement is very simple and natural, it's fun to watch programs competing with each other, and it's easy to write and visualize a solution of your own.

Meanwhile, the start of the algorithm competition is getting closer. SnarkNews has launched a prediction contest for it, you can view the current favorites here.

(Photo on the left by TopCoder)

This week in competitive programming

There was just one contest this week - Codeforces Round 210 (problems, results). It was the last competition before the TopCoder Open, so several TCO participants took this chance to practice, including Egor, who won the round - congratulations! - and Tomek, for whom it was just the fifth codeforces round and who came eighth and achieved red rating - congratulations, too!

Meanwhile, most competitors have already arrived in Washington, DC for the TCO. We spent today's free day on sightseeing: the picture on the left shows tourist, andrewzta, Petr, darnley (algorithm contestants) and Milanin (marathon contestant) on the bank of the Potomac river; nothing reveals that we're right in the center of the capital of the United States. I will post more TCO pictures and updates during the week - stay tuned!

This week in competitive programming

Friday was the day of TopCoder SRM 596 (problems, results, my screencast), featuring three problems which left me wondering how could one ever come up with such questions :) I'm saying that in totally positive sense - they were interesting to solve, but just seemed to come out of nowhere. This was the last round before the TopCoder Open 2013 (program) which takes place November 11-13 in Washington, DC, and which is the oldest open programming competition which has onsite finals. This year the rules have been changed significantly, allowing contestants 20 minutes of downloading software and pre-written algorithms from the Internet before the contest starts. On one hand, it has always been weird to write Java without an IDE at TopCoder Open finals, so I'm glad I won't have to do that anymore. On the other hand, the TopCoder Open competition used to be a completely unique experience - coders entering the arena with nothing but their minds and simple text editors, and finding out who can solve problems faster and better; now it's becoming more similar to the online competitions.

On Sunday, the third round of the Open Cup took place (results). In a funny coincidence, one the hardest problems of this round (problem 10) relied on the fact that the area of a polygon can be represented as f(e₁)+f(e₂)+...+f(e_m), where e₁, e₂, ..., e_m are its edges. This is precisely the fact that allowed the linearity of expectation to work in last week's TopCoder problem I mentioned.

Let me remind you of the problem statement: you are given 50 points on the plane, with each point assigned a probability that it exists. What is the expected area of the convex hull of existing points?

The convex hull is a polygon, and thus its area can be represented in the above form - as a sum of functions of its edges (with each function being the area of the directed triangle or the directed trapezoid - see http://en.wikipedia.org/wiki/Polygon#Area_and_centroid, for example). We can even look at this function as the sum of functions g(u, v) over all pairs u and v of our points. This function will be equal to f(uv) for edges uv of the convex hull and 0 for all other pairs. And here comes the linearity of expectation: finding expected value of the sum of g(u, v) is equal to finding the sum of expected values of g(u, v)! Finding the expected value of g(u, v) for the given u and v is relatively easy: it's equal to f(uv) * p(uv is an edge of the convex hull). Finally, the probability that uv is a (directed) edge of the convex hull is obtained by multiplying the probabilities that u and v exist by the probabilities that all points that would stop uv from being an edge of the convex hull don't exist. Such points are those lying on the line uv outside the segment uv, plus points on the "wrong" side of line uv.

For further clarification, here's my solution from the competition in full:

public double expectation(int[] x, int[] y, int[] prob) {
    double res = 0;
    int n = x.length;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) if (i != j) {
            int x1 = x[i];
            int y1 = y[i];
            int x2 = x[j];
            int y2 = y[j];
            double pr = prob[i] * prob[j] / 1000000.0;
            for (int k = 0; k < n; ++k) if (k != i && k != j) {
                int x3 = x[k];
                int y3 = y[k];
                int z = (x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1);
                boolean bad = false;
                if (z > 0) bad = true; else if (z == 0) {
                    int z1 = (x3 - x1) * (x2 - x1) + (y3 - y1) * (y2 - y1);
                    int z2 = (x3 - x2) * (x1 - x2) + (y3 - y2) * (y1 - y2);
                    if (z1 < 0 || z2 < 0) bad = true;
                }
                if (bad)
                    pr *= (1000 - prob[k]) / 1000.0;
            }
            res += pr * ((x1 - x2) * (y1 + y2)); 
        }
    return res / 2;
}

And here's the editorial with a much more detailed and careful explanation, although that solution is a bit more complex.

Thanks for reading, and come back next week!