Ural Championship - day 1 : Russia vs China

Russia vs China match - 5 best Russian teams versus 5 best Chinese teams - starts in just 7 minutes. The teams are seated facing each other in a large hall, with spectators all around. We will blog about the contest.

12:25 - 5 minutes before start. From the practice session, it looks like the format is: the total score for Russia is obtained by just summing the total solved problems and total penalty time, same for China.
12:28 - Russian teams are: SPb IFMO 1, SPb SU 4, Moscow SU ST, Ural FU Orange, MIPT Lambda.
12:30 - Unfortunately one of the Chinese teams has only two people due to visa issues.
12:32 - The practice session is still going on, the contest is delayed.
12:34 - Actually, it was schedule to start at 13:00 - in 30 minutes, so there’s no delay. Practice session standings: http://acm.timus.ru/monitor.aspx?id=149
12:38 - Main contest standings - http://acm.timus.ru/monitor.aspx?id=150
12:42 - Important people speaking. Among them Leonid Volkov, who invented the Russia vs China format in the first place, and at the same time is the organizer of the first mass non-government elections in Russia last fall.
12:43 - Moscow SU ST won the practice session by getting all problems accepted from the first attempt. Back when I was competing, many top-level teams actually tried to win the practice session, too, to get more confidence for the main contest.
12:54 - 6 minutes before start.
12:59 - There will be 12 problems.
13:10 - Problem statements: https://docs.google.com/file/d/0B2d37tm1YmE3QmdXazhnN2lRdDQ/edit?usp=sharing.
13:13 - So far, 1:1: SJTU solved B, ITMO solved E.
13:14 - Problem B: given a sequence of Ws and Ls, find a set of segments of maximum total length such that each segment has more Ws than Ls. Looks like it should be solvable by some kind of greedy.
13:14 - E is pretty easy. We are given bitmap image (maximum size 50x50). We want to draw disk of some positive radius with center at some pixel. It should be fully within our bitmap. We can switch any pixel. What minimum number of pixels need to be switched? We can just check all centers, order all pixels by distance and then try to color black all pixels with distance up to r for all valid rs (and white all other pixels).
13:18 - Commentary today is by myself and Egor Kulikov.
13:19 - Score is 4:2, SPb NRU ITMO is the only team with two tasks as of now.
13:21 - The solved H in addition to E. H is very, very simple: given a set of squares and circles, how many pairs “figure A fits inside figure B” are there? Just sorting.
13:23 - This problem shows the “Polish flavor” of the problem statements today (they were prepared by Jakub Pachocki, also known as meret): whenever a nlogn solution is expected, n will be at least a million. If there was a linear-time solution in mind, n would be at least 10 million :) In Russian contests, nlogn is usually tested via n equal to about hundred thousand.
13:25 - The score is 5:5, there are two teams - Russian and Chinese - with two problems, and two teams - again Russian and Chinese - with zero problems.
13:29 - Development environments: Russian teams 4x FAR manager, 1x Visual Studio. Chinese teams: 2x Visual Studio, 1x Eclipse, 2x something like GVIM or Notepad++.
13:35 - Task G is also solved by ITMO. Given number n, find minimum of values popcount(n * k) for integer k > 0, where popcount is number of 1 bits in binary representations. Also problem statement gives emphasis on the fact that for n = 2^m - 1 such value is achieved for k = 1.
13:38 - Task I is also solved by ITMO - find number of comprime subsets of {1, 2, … , n}. Subset is coprime if every pair of its elements are coprime.
13:40 - Apparently ITMO were too fast - now all three are just reading problem statements, they’re not using their computer since they don’t have any more solved problems :)
13:43 - 13:8. As I expected, top 3 Russian teams stand out, only SJTU (2010 ACM ICPC World Champions) manages to keep level right now.
13:44 - Problem G looks to be a BFS on a graph with 0 and 1 edges: let’s look at the multiplier from the least significant digit. It determines the last digit of the product, and the carry which is a number up to n. So vertices of our graph are correspond to those “carry” values, and edges have 0 or 1 or them depending on what the corresponding last digit of the product turns out to be, and we need to find the shortest non-trivial path from 0 to 0.
13:48 - Task A is solved by SJTU. In graph with weighted edges we need to select subset of edges with minimum total weight that would connect given 4 vertices.
13:51 - The main idea of problem I: we need to keep track of whether we used each of the prime numbers up to sqrt(3000). For larger prime numbers, we can process them in sequence since they don’t interfere with each other.
13:58 - It looks like the connecting graph in problem A can always be represented as: a path connecting two of the chosen nodes, another path connecting two of the chosen nodes, then a path connecting those paths. Then we can do the following: first, for each vertex in the graph, let's find the shortest distance to each of the chosen nodes. Then, by summing two of those, we obtain "the cheapest way to connect two nodes with a path going through vertex X". And then, we can run another Dijkstra starting with those values that would deduce "the cheapest way to connect two nodes with a path and then connect that path to vertex X". Finally, summing those numbers for two different pairs of nodes should give the answer.
14:21 - Sorry for not updating the blog for some time. Not much is happening, as the top teams look to be searching for the next solvable problem, but haven’t found it yet.
14:28 - Problem L talks about a nice constructive object - a Fibonacci graph (see the problem statements like above for the definition). It would seem that the solution will have to be equally constructive, but I can’t see it yet.
14:29 - In task J we are given list of numbers s_i and we need to answer the following queries - find the maximum of s_i+z*(i-a) for i between a and b. There are additional constraints on s, but they are irrelevant to my solution. First, the “-a” part doesn’t affect where the maximum is located, so we can forget about it. Let’s build an interval tree, where each node would be able to tell the required maximum for the corresponding segment for each value of z - by keeping a list of (minimum value of z, maximum value of z, linear function for maximum). We can build such tree in nlogn time and nlogn memory. Then we can answer each query naively in log²n time, but if we would sort queries by z we can achieve total time of O(m log m + m log n).
14:34 - Score is pretty close - 21:20 with Russia still in the lead.
14:42 - Problem C: given a polygon and several queries, each query containing a direction, is this polygon a combination of two non-decreasing chains in that direction?
14:43 - It looks like the difficulty in this problem is technical, not algorithmic. As we rotate the direction, we can maintain the leftmost and rightmost corners, and then need to answer queries "is it true that all polar angles of edges between leftmost and rightmost are between alpha and alpha+pi, and all polar angles of edges between rightmost and leftmost are between alpha+pi and alpha+2*pi. This should be doable in nlogn by appropriately choosing "events".
14:45 - In the meantime, China is ahead again - 21:22. They were ahead for about one minute between 10th and 11th minutes of the contest :)
14:45 - While top Russian teams do better than top Chinese teams, at the bottom China performs much better.
14:50 - It looks like the main driver of Chinese rise was Sun Yat-Sen U - they used to had wrong attempts on 4 different problems, now they’ve corrected their solutions for 3 of them.
14:52 - Problem D: we start with a sequence of integers. Now we take all n*(n+1)/2 its subsegments, sort each of them separately, and then sort them as sequences lexicographically. What will be the k-th sequence?
14:55 - to be precise, sorting is not exactly lexicographical - when one word is a prefix of another, it’s considered greater than the other, not less.
14:57 - It seems that we should first count how many segments contain all 1's, then how many contain all but one, and so on. Once we've established how many ones are there in the answer, what to do next? :)
15:00 - ITMO is the first team to solve L.
15:01 - The condition "has exactly X occurrences of number Y" defines a set of rectangles on the (left end, right end) plane. So we could try to maintain a set of (non-intersecting) rectangles on that plane as we build up our answer, but I'm not sure if the running time won't explode.
15:10 - Problem F: you are given a set of crates, each with a base area and a height, the product of those two being its volume, and we need to hold a given volume of honey. In case we have more than enough crates, we can save storage space by putting one crate inside another - more precisely, the total base area of crates directly inside a given crate should not exceed its base area, and that will result in less honey fitting into the outer crate.
15:18 - Also each base area is a power of two. This seems to be quite easy. First, let’s do a binary search on the total area. As soon as we’ve fixed the area, we go from the largest boxes to the smallest boxes. At each size, we have a certain number of “slots” for crates of this size. It’s easy to see that we should put the highest crates there (and all others inside them so they’ve effectively skipped), and we should put the highest crates so that they stand above the existing crates as much as possible, so that the smallest amount of volume is wasted. Just greedy in several aspects.
15:26 - Tweets about the contest: https://twitter.com/search/realtime?q=%D0%B1%D0%B8%D1%82%D0%B2%D0%B0%20%D0%B3%D0%B8%D0%B3%D0%B0%D0%BD%D1%82%D0%BE%D0%B2&src=typd
15:27 - Problem K is hard to describe quickly, you will need to read the problem statement using the link in the beginning of this post. I would expect that the biggest difficulty there is understanding what the given definition really means.
15:30 - Not too many problems solved in the past hours. The bottom two teams are still from Russia, 3 and 2 problems, last one solved almost an hour and a half ago. There are 3 teams with 7 problems at the top: ITMO, SJTU, MSU, the fourth team has just 5.
15:35 - For ITMO, Gennady is solving problems on paper, while Mikhail and Niyaz are alternating in coding the problems they’ve solved already. Righ now Mikhail has found a bug in his solution, probably for F, so we should be seeing another submit there soon.
15:39 - SJTU and Zhejiang are actually not using their computers right now, apparently solving problems requires a lot of effort today.
15:41 - And my prediction was true: ITMO does solve F, leading with 8 right now.
15:41 - Task L: for each vertex i let’s consider Fibonacci coding of i - 1. We can see that two vertices are connected by edge iff their codings differ in just one position. That means that shortest path length is always the number of positions in which endpoints differ. But we cannot alter digits in any order as not every binary string is valid Fibonacci coding. Hence we need dynamically count number of permutations of positions where coding have different digits. State would be (number of permutations of said positions with indices <= k, position of k in this permutation).
15:48 - ITMO solves C and leads 9-7!
15:54 - Gennady sat down to code J. The teams are so close to spectators that we can almost see the code, or literally see it using a camera with zoom :)
15:56 - A view from above by Leonid: http://twitpic.com/cnb2w2.
15:59 - Meanwhile, https://twitter.com/lperovskaya tweets under https://twitter.com/niyaznigmatul's account. Imagine what would real tweets from a contestant look like :)
16:18 - The only submission in the fourth hour of the contest so far is SPb SU 4’s L.
16:20 - And just as a wrote that, two more submissions, including ITMO’s J. Now they have just 2 problems to go, D and K. I don’t know how to solve both yet, although I suspect K is easy.
16:29 - Problem K: first, making the sequence non-periodic can be obtained using inclusion-exclusion, and making it lexicographically largest just means dividing the answer by m. The only problem is counting plain sequences with the given sum and the given restriction.
16:42 - Now every team except Tsinghua is coding. Generally, this looks to be the time when MIPT and Ural FU have to perform - the top 3 Russian teams will saturate, and even if they solve more problems, they will not solve many.
16:47 - It seems that Gennady is solving one of the remaining problems, while Niyaz is coding the other under supervision of Mikhail.
16:55 - And ITMO solve K. They really are several heads above the competition. Just one problem remaining for them - D.
16:57 - Russia leads by 7 in top 6, but trails by 4 in last 4.
17:00 - Standings are frozen now. Russia leads 34:31, top 3 is ITMO with 11, MSU with 9 and SJTU with 8.
17:22 - The scoreboard is frozen now. In the last 30 minutes the teams themselves won’t know the outcomes of their submissions. I’ve been coding a soluton for D in the past 20 minutes along the lines of the above idea, and ended up being O(n^2) and got a TLE :)
17:26 - Even despite the time limit being 30 seconds. Jakub (the author of the problems) says that his solution runs in just 2 seconds.
17:31 - Interesting info in Codeforces comments: Jakub prepared this contest, and in return the organizers paid for his and his team’s trip to the championship. A model similar to Petrozavodsk camps.
17:36 - Submissions after the freeze are not frequent. MSU and SJTU are working on C, SPbSU on F. Several submissions from MIPT and Ural FU, hope they’re fighting well for Russia :)
17:47 - Most teams are looking at the screen together (all three people), trying to find bugs in their code. ITMO have submitted D but haven’t received any outcome, as promised, so they’re trying to find bugs anyway.
17:50 - Actually, that’s not true - they haven’t submitted D, so apparently it’s not working even on their examples.
17:51 - I think the format is awesome. There are two awesome things: first, the Russia vs China aspect, and second, the total low number of teams participating, meaning that spectators can get a really detailed picture about what’s going on. I think we might want to have TopCoder-style elimination tournaments for teams, with the final round of just 8.
17:54 - Since no other team has submitted K, it would seem that ITMO’s fight with D doesn’t matter - but it does beause it would still affect the overall Russia score.
17:56 - Apparently the official results will only be announced at the closing ceremony two days layer. There will only be rumors until then, although with just 10 teams it would probably not be hard to figure out Russia/China scores.
18:01 - The contest is over. ITMO submitted D during last 5 minutes.
18:05 - That’s probably all for today, will post rumors if there are any. Thanks for reading!