This week in competitive programming

2117 programmers took part in Codeforces Round 221 on Tuesday (top 5 on the left). I didn't, so I can simply share the links to problems and results, and congratulate the winner Touma_Kazusa for whom this was just the third Codeforces round!

2075 programmers took part in TopCoder SRM 602 on Saturday (problems, results, my screencast, top 5 on the left). The 250 problem was simple dynamic programming, the 550 was a tricky case study with simple data structures, and 1000 was a mostly mathematical problem to be solved on paper. The 550 possessed an interesting property: despite being a very tricky case study when N is up to 100000, it allowed a very simple solution when N is around 5-10 that can be implemented in just a couple of minutes. That's why after submitting it, I've implemented that simple solution and compared it against my solution on thousands of random testcases. It helped discover a silly bug and I had to resubmit losing quite a few points, but I would've lost much more had my solution failed the system test. My point is that even in very short contests, like TopCoder, there are situations for such stress-testing against a simple solution.

2493 programmers took part in Codeforces Round 222 on Sunday (problems, results, my screencast that was unfortunately truncated after about an hour when I've locked my computer, top 5 on the left). The problems were fairly standard, but the last one required a great deal of accuracy. I'd like to highlight the easiest problem, though. The task was: given a connected set of cells on the grid and a number K, remove K cells from the set so that it remains connected. It is quite straightforward and can be solved in many ways, but it still requires some logical thinking and the statement is very easy to understand. I think this is a very good easy algorithmic problem.

One other peculiar fact about this week's Codeforces rounds is: today's top 5 are all from ex-USSR, while 4 out of Tuesday's top 5 are from China and Japan. There are several possible explanations. First, Tuesday's round was 1.5 hours later so it was less convenient for people in eastern timezones. Second, top 5 in a round is so random that there's nothing to explain at all. Third, one of the round's problems might be similar to a problem from an older contest that was only popular in a certain region. But these are the boring explanations :) Wouldn't it be interesting if different styles of education present in Russia vs Japan vs China led to different sets of skills that would in turn lead to such country-specific contest results? Has anybody seen more careful analysis of country distribution in algorithmic programming contest results?

This week in competitive programming

In contrast to last week, this week was quite light on programming contests. Late on Saturday, the final online round of the Facebook Hacker Cup took place (my screencast, top 5 on the left). Several things went wrong at the same time for me. First, I've spent an hour on the easiest problem by making a somewhat classical mistake: the problem statement had a constraint n_i<=4, and I immediately started thinking about solutions that rely on that constraint. It turned out that the correct solution works fine even for large values of n, and is much, much simpler that what I came up with during that hour. Then, I've implemented the solution for the third problem with the correct big-O asymptotic complexity, but without caring too much about the constant factor, and couldn't reduce the constant factor under the pressure of the last 30 minutes of the contest. I've made a desperate attempt to still run my solution against judges' input, but it timed out as expected.

When two problems go wrong at the same time, getting into the top 25 in the world is too hard, so congratulations and good luck to everybody who made it to the onsite finals!

On Sunday, TopCoder SRM 601 took place (problems, results, my screencast, top 5 on the left). Both the medium and the hard problems required tricky dynamic programming: the solution that comes to mind right after reading the problem has too many states in dynamic programming, so you have to somehow reduce the state space. While both problems look a bit artificial and thus not as exciting to solve, they are a good way to practice advanced dynamic programming if you want to (medium, hard).

Thanks for reading, and see you next week!

This week in competitive programming

 This week was very busy with contests. The week started with the second quaterfinal of the Kotlin challenge (problems in Russian, results in Russian, top 5 on the left). The round didn't go as smoothly as the first one, and the system had some downtime, so there will be a third quarterfinal to compensate those affected.

Then, Codeforces Round 219 took place on Friday (problems, results, top 5 on the left). Three out of four properties of an ideal contest held:
1) nobody solved all problems;
2) each problem got solved by somebody;
3) there's no problem solved by everybody.
The only missing part is
4) there's no contestant with zero problems solved.
But I guess the latter is quite hard to achieve in the Codeforces setting.

Saturday started with TopCoder SRM 600 which featured a T-shirt giveaway because of the round number (problems, results, my screencast, top 5 on the left). The screencast features two very long and probably boring situations: first, for the last 20 minutes of the coding phase I couldn't understand why my solution doesn't pass one of the samples, but couldn't. It turned out I was missing the fact that two lines can intersect in a point with non-integer coordinates, and it's unclear to me now how one can ignore this fact for so long. But even more disturbingly, during the last 13 minutes of the challenge phase I couldn't come up with a testcase for the medium problem with answer zero, but where there's exactly one way to reach zero. There's really no excuse for that.

Later that day, the second round of Facebook Hacker Cup happened (my screencast, top 5 on the left). With the format of competition penalizing very heavily for one's mistakes, the right strategy seemed to be to write two solutions for each problem, one fast and one slow, and compare them on many small testcases to make sure the fast solution is correct. That plan worked out well - but one may wonder if that strategy would be too slow to get into the top 25 in Round 3.

Just about 8 hours after the end of the Hacker Cup, on Sunday, the next stage of the Open Cup took place (top 5 on the left). The problems turned out to be too easy and the winner solved all of them in just over 2 hours. One must note the performance of the second-placed XZ team: I believe this is the first full team (as opposed to teams of just one person) regularly participating in the Open Cup from the Bay Area and from the USA in general. The convex hull of all participating teams on the globe (is there even such a thing on a sphere?..) just got bigger.

Later on Sunday, TopCoder SRM 600.5 took place (problems, results, top 5 on the left). It was a very unusual match, with 4 hours of coding and second and third problems being harder than the usual 'hard' problems from TopCoder. However, only those two problems got solved, with the grand total of 10 accepted submissions for about a thousand contestants and 4 hours.

The third problem was amazingly simply stated, and I still have no idea how to solve it (full problem statement). You are given a graph with N vertices numbered from 1 to N, where vertices A and B are connected by an edge if and only if abs(A-B) is in the given set S. How many connected components are there in this graph? N is up to 10¹⁸, S has up to 50 elements, each up to N. Any ideas?

Let me finish this very long post with a non-scoreboard picture, taken in Barcelona which I visited for 4 days and where I've solved most of the contests mentioned above:

The decisive TopCoder Open finals hard problem

Let me remind you the hardest problem from this year's TCO finals (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).

TopCoder has published a great editorial which you can consult for more details, but I want to share an approach that is a bit different. First, we can notice that if a white cell is on the border of the field, then the corresponding tetramino can be placed immediately in exactly one way. If, after placing such tetraminoes, we find a white cell that has one of its adjacent cells already covered, we can also place the corresponding tetramino (see the picture for an example of such deterministic placement, white cells are denoted with circles). Finally, if two white cells are adjacent, we can also place the two corresponding tetraminoes. We can repeat this process until we either arrive at a contradiction, in which case we have zero solutions, or there are no more 'deterministic' tetraminoes left.

In the second case, let's consider the graph formed by the edges connecting the white cells to four neighboring black cells. It's not hard to see that its connected components can be handled separately, with the final result obtained by multiplication. When a connected component is a tree, then exactly one black cell in this connected component will remain empty (because it has 3K+1 black cells and K white cells, for example the picture on the left has 13 black and 4 white cells), and it's not hard to see that we can pick any black cell to be empty, after which the positioning of all tetraminoes is determined similarly to the "tetramino on the border" case, so we have 3K+1 solutions here.

Finally, when a connected component contains a cycle, then there are two ways to place the tetraminoes along that cycle, and all remaining tetraminoes are then placed deterministically. In case a connected component has more than one cycle, in other words the number of edges more than the number of vertices, there will be no solution (for example because the number of black cells will be fewer than 3K).

This week in competitive programming

The weekdays featured just one contest, TopCoder SRM 599 on Wednesday (problems, results, top 5 on the left, my screencast). The hard problem was: you are given a directed graph with at most 50 vertices and at most 8 edges (so most vertices don't have any adjacent edges at all), and a rooted tree with the same number of vertices. How many ways are there to map the vertices of the graph to the vertices of the tree (one-to-one) such that each edge of the graph corresponds to ancestor-descendant pair in the tree? One funny aspect of this problem is the complexity of the solution. If 50 is N and 8 is M, then the expected solution complexity was O(N*5^M), the solution that the authors were trying to fail was O(N*9^M) (more details from the problem author at Codeforces), and I've managed to come up with a O(N*7^M) solution they didn't expect, and barely squeeze in the time limit.

The weekend featured elimination rounds for two annual contests. On Saturday, the first official round of the Kotlin Challenge took place (problems, results, top 5 on the left). This is a brand new competition with problems in Russian, final round in St Petersburg in April 2014, and only one allowed programming language - Kotlin. I'm pretty sure almost all contestants at the top of the scoreboard didn't know the language before, but it appears that it's conventional enough and learning to do simple things using it is not hard. Even if you missed this round, you still have a chance to register and participate in the next round this Wednesday, but keep in mind that all tasks and judges communication is in Russian.

For 24 hours between Saturday and Sunday, the first round of the Facebook Hacker Cup took place. Since they don't publish the problems and the scoreboard, I assume they don't want to encourage discussion so I won't go deeper here :)

Thanks for reading, and see you next week!

This week in competitive programming

The week started with Codeforces Round 215 on Tuesday (problems, results, top 5 on the left, my screencast). The round was unusually easy, with many competitors solving all five problems around the 1 hour mark, and the round was decided on challenges. There were two main strategies that could give one hundreds of challenge points. First, there was a nasty integer overflow possible in problem B, so a carefully constructed testcase could either make many solutions time out or make them produce a wrong answer. Then, problem C was to be essentially solved on paper, and asked to find some simple function f(n), so it was very easy to check this function in other solutions to see if it's any different from the correct one. Egor employed both strategies and achieved a commanding win, over 200 points above the second place.

On Friday, TopCoder Single Round Match 598 took place (problems, results, top 5 on the left). I didn't take part, so I can only admire Egor's second victory of the week. Another interesting fact is that the SRM took place at 6am Russian time, but the 4th and 5th place were taken by members of SPb SU 4 and SPb ITMO 1, two teams due to compete in NEERC just two days later - apparently they thought that additional preparation is worth more than not waking up early.

Did that work out? You can see the NEERC top 5 on the left (problems, results). SPb SU 4 won as expected, although they couldn't solve any of the 3 difficult problems, so they could easily lose the first place to another team. SPb ITMO 1 didn't do as good, but still qualified for the World Finals. Speaking of World Finals qualifications, in case NEERC competitors read my blog, it has just been announced that the ACM ICPC headquarters have agreed to give 17th slot to NEERC teams, so the Moscow Institute of Steel and Alloys is also going to the World Finals (all finalists from NEERC)!

As I mentioned before, I've test-solved this contest, my result was 9 problems. Out of the three difficult problems I've solved problem D, and I find it very beautiful. The author of this problem is Egor, so this seems to be his good week :)

Here's how it goes: you are given 50 strings of length at most 10. You need to construct a rooted tree and write exactly one character on each edge of the tree, in such a way that one can find each of those 50 strings in this tree. We say that we can find a string in such tree if we obtain this string using the following process. Start at some vertex, and repeat the following: pick one of the children of the current vertex (remember, the tree is rooted), write down the character from that child's edge, and make that child the new current vertex. In other words, there needs to be a path from some vertex in the tree to another vertex in the tree that always goes away from the root and has the string written along it (see the PDF for the complete statement, look for problem D "Dictionary"). What is the minimum possible size of such tree?

NEERC 2013

There's roughly 10 minutes left before the start of NEERC 2013, one of the strongest ACM ICPC regional contests. The live standings will be at http://neerc.ifmo.ru/information/standings.html, a much more magical experimental scoreboard at http://ctddev.ifmo.ru/, problems at http://neerc.ifmo.ru/information/problems.pdf, live text commentary in Russian by tourist and niyaznigmatul at http://neercnews.blogspot.ru/2013/12/neerc-2013.html, Twitter comments at https://twitter.com/NEERCNews and more generally at https://twitter.com/search?q=%23NEERC&src=hash&f=realtime. Some more preview links: http://codeforces.com/blog/entry/9784, http://codeforces.ru/blog/entry/9754, http://neerc2013.snarknews.info/, http://srv.snarknews.info/~ejudge/showvote.cgi?data=neerc2013.

I've test-solved the contest several days ago, and it has awesome problems of different types, so hopefully each team will find something it likes and we'll see a fierce competition. Good luck to all contestants!

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!

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?

This week in competitive programming

This week started with two competitions on Tuesday.

The first was Codeforces Round 207: problems, results. I didn't take part, so I don't have anything to share about the problems. Congratulations Gennady, and it's nice to see Bruce again in top 5!

Then, there was TopCoder SRM 594: problems, results, my screencast. The problemset composition was somewhat classical for TopCoder: a 250 that involves a careful check of all possibilities, a 550 that requires a standard algorithm - in this case König's theorem, and a 950 that nobody solves, although it does look quite tractable. This type of problemset places a huge emphasis on the challenge phase, and Gennady has again came out on top with 4 successful challenges.

The 550 allowed two approaches - minimum vertex cover in a bipartite graph and minimum cut in a network. The two approaches are, of course, very similar in this case. The first goes like this: let's make a bipartite graph, with the left part containing white cells, the right part containing the empty cells, and edges connecting adjacent cells from different parts. Consider a vertex cover in the graph - such set of vertices that every edge has at least one of its ends in this set. It's not hard to see that vertex covers correspond exactly to sets of cells that we can leave occupied at the end: if we put black stones to the empty cells from the vertex cover, then all white cells not from vertex cover will have all adjacent cells occupied and will be removed. Since we need to maximize the number of empty cells in the end, we need to minimize the number of occupied cells in the end, and thus minimize this vertex cover.

The second is: let's make a network consisting of source S, sink T, all white cells, and all empty cells. We draw edges from S to all white cells with capacity 1, from each white cell to its adjacent empty cells with infinite capacity, and from each empty cell to T with capacity 1. Why infinite capacity? It helps enforce the following property: for each finite cut A | B of this network, all neighbors of each white cell in A will also be in A - because otherwise there'd be an infinite edge from A to B and the cut would be infinite. Given this property, each cut gets a natural meaning: the white cells in A are those white cells that we will capture, and the empty cells in A are where the black stones will need to go. Finally, the capacity of the cut is the sum of the number of white cells in B and the number of empty cells in A, which is exactly the cells that will end up occupied, so we need to find the minimum cut.

This idea - adding appropriate infinite edges to the network to make sure each finite cut possesses the properties we require - actually comes up pretty often in algorithmic competitions.

Apart from the open competitions, this week featured quite a few ACM ICPC rounds for eligible university students. The ACM ICPC season is in full swing now, with subregionals and regionals happening across the world. Most regionals will happen in October or Novemeber, with a few slipping to December. There were several rounds this week featuring teams that will definitely challenge for medals in the World Finals, for example the NEERC Saratov Subregional (results) and the NEERC Moscow Subregional (results). Only teams from the corresponding geographical area can participate in each of those subregionals, but other teams can and usually do take part online and thus we get an early glimpse at the relative strength of the teams and determine the favorites for the regionals and World Finals.

Addition problem

Let me remind you of a problem I've mentioned last week: 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?

The first step is to find the greatest common divisor of A and B: gcd(A, B) = G. If S is not divisible by G, then clearly we can't get it. Otherwise, let's divide everything by G - in other words, we've reduced the problem to the case where gcd(A, B) = 1.

Now, it's clear that each number we can obtain is equal to N*A+M*B for some non-negative N and M. But is any pair of non-negative N and M possible? No. For example, it's not hard to see that we can't obtain 2*A+2*B. We start with A and B, continue to A+B and B (A+B and A is similar), and then it's not hard to see that the multiplier of B in all following numbers will be greater than the multiplier of A.

It helps to look at this problem as a geometric one. Let's plot N on one axis and M on the other axis. We start with vectors (0, 1) and (1, 0). At each step we add one of our vectors to another. We can notice an invariant: the area of the triangle induced by our vectors stays equal to 0.5! The area is one half of the vector's cross product, and the cross product doesn't change when we add one vector to another. This picture is similar to what happens when studying continued fractions.

In other terms, if our numbers are N₁*A+M₁*B and N₂*A+M₂*B, then N₁*M₂-M₁*N₂ is always equal to 1. One consequence of this invariant is that N₁ and M₁ (or N₂ and M₂, for that matter) are relatively prime: gcd(N₁, M₁)=1. So we have limited the set of obtainable numbers to those where gcd(N, M)=1.

But it's not hard to see the reverse also holds! Suppose gcd(N,M)=1. That means there exist such numbers X and Y that N*X+M*Y=1. Let's say that X is non-negative and Y is non-positive. Then we can define N₁=N, M₁=M, N₂=-Y, M₂=X, and we obtain the above invariant: N₁*M₂-M₁*N₂=1. But then we can repeatedly subtract either (N₁, M₁) from (N₂, M₂) or vice versa, reconstructing the path from (1,0), (0,1) from the end.

So the original problem boils down to: is there a way to pick non-negative N and M such that gcd(N, M)=1 and N*A+M*B=S? We can solve the latter Diophantine equation in the standard way using the Extended Euclidean algorithm, obtaining N(T)=N₀+B*T, M(T)=M₀-A*T. The condition on N and M being non-negative gives us a range of possible values of T, and in case that range is empty, we have no solution. But in case it's non-empty, how to check if N and M will be relatively prime for some T in that range?

And here's the key trick: I've guessed that we can just check possible values of T until we find one that gives relatively prime N and M, and we will either find such T quickly or run out of possible values of T quickly. Why? I didn't prove it during the contest, and the more I try to prove it now, the more it looks it might be false :) Any ideas?

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!

A problem that requires being careful and determined

In my earlier post I've told you about a problem that almost guaranteed me a win in the Russian Code Cup. Here's how I solved it.

Problem statement: you are given a rectangular grid of white and black cells, N rows of M columns each. Top-left and bottom-right corner cells are black. You start at the top-left cell. Every second you move to an adjacent cell (sharing a side). You're not allowed to stay in the same cell. If you move to a white cell, then you're instantly teleported to a random white cell that is picked uniformly and independently. Note that it's possible that you're teleported to the cell you're already in. Your goal is to reach the bottom-right corner as fast as possible. Of course, random teleportations mean you can't guarantee how long it will take, so you need to minimize the expected (average) time to reach the bottom-right corner.

The first step is standard for this kind of problem: we treat it as a dynamic programming problem. We have N*M states, one per cell of the grid, and we should calculate the expected time to reach the bottom right-corner starting from each of those cells. Let's denote this expected time for cell X as T_X. Suppose the possible moves from cell X lead to cells Y₁, Y₂, ... If all of those cells are black, then it's not hard to see that T_X=1+min(T_Y1, T_Y2, ...). This equation simply says: we will spend one second and end up in one of those cells - so it's obvious we should pick the cell with the smallest expected time. If at least one of those cells is white, then T_X=1+min (W, T_Y1 if Y₁ is black, T_Y2 if Y₂ is black, ...), where W is the average value of T_Z over all white cells Z. This equation says: we can either go to a black cell, in which case we know the expected time, or to a white cell, in which case the expected time is the average expected time over all cells we could be teleported to.

It might seem that we already have a working dynamic programming solution - but we don't. The equations we've written down have cycles. Adjacent cells depend on one another, and many cells, including some white cells, depend on all white cells. So we can't just compute the values of T.

Here's the problem-specific part: we will now simplify the equations so that it becomes clear how to find T. First, suppose we stand on some cell. It's not hard to see that there are only two feasible strategies: either we go to the bottom-right cell using only black cells, and using the shortest possible path over black cells, or we go to the closest white cell in order to teleport. Indeed, if we ever go to a white cell, then our state is completely reset - we can end up in any white cell. So there's no need to pick a particular white cell to jump to, and it's fastest to go to the nearest one.

Now, let's consider the value of T_Z for a cell Z. Let A_Z be the length of the shortest path over black cells from Z to the bottom-right corner, and B_Z be the length of the fastest way to get to a white cell starting from this white cell. Then T_Z=min(A_Z,B_Z+W). Now remember that W is the average value of T_Z over all white cells Z: W=sum(T_Z)/NW, where NW is the number of white cells. So W=sum(min(A_Z,B_Z+W))/NW. We have an equation over W, but we can't solve it immediately because it has 'min's in it.

Since A and B are integers, we could tell which part of each 'min' is smaller if we know the integer part of W: K<=W<K+1. Indeed, we can just compare A_Z with B_Z+K. If A_Z is smaller or equal, then it will be the value of the corresponding 'min'. If A_Z is greater, then the corresponding 'min' is simply B_Z+W. After we know what each 'min' turns out to be, we're left with a simple linear equation on W that we can easily solve. The only remaining thing is indeed to check that K<=W<K+1. Of course, we also need to find the proper K. We can just check all values starting from 0, and exactly one will yield the answer. Alternatively, it's not hard to see that if the value of W that we obtain from the above equation ends up being larger than K, then the value of K is too small, and if it's smaller than K, then K is too big - that allows us to do a binary search on K.

Having found W, we can solve the rest of the problem easily. Remember that the answer for each cell, black or white, is just T_Z=min(A_Z,B_Z+W). One further observation that doesn't help much in this problem: B_Z for white cells is either 1 or 2. If there's another white cell next to Z, we can just jump there, and if not, we can go to any neighboring black cell and back.

What do you feel when looking at the above solution? Well, for one, it's rather long. But at the same time, it didn't require any out-of-nowhere tricks or fancy algorithms (well, it did require breadth-first search for shortest paths over black cells). The only real requirement is the ability to carefully simplify the problem step by step until it becomes solveable. Note that we could make many wrong assumptions that would lead us to an incorrect answer - the main difficulty is to be careful and determined enough to avoid that. Many programming contets problems are like that, and I think this problem is an excellent example that you can train on to improve this skill. I think this skill is also extremely useful in software engineering and helps me a lot in my daily work.

Do you have a favorite problem of this kind? Please answer in comments!