Algorithm problems for dummies: Petr Mitrichev's blog

Ural Championship - aftermath

2013-05-09T09:57:00.001+04:00

The best team in the world right now, SPb IFMO 1, has only managed to get the second place at the Ural Championship, that was according to my plan :) However, my team has only got 13th place - and the winner was Moscow SU Unpretired, another veteran team that has 5 ACM ICPC medals between them - 2 gold, 1 silver, and 2 bronze - all in different teams. Congratulations Ilya (ilyakor), Jacob (Dlougach) and Ivan (Jedi_Knight)!

Here are the results of the top teams (full results here: http://acm.urfu.ru/chu/2013/standings.html):

Rank	Participant	A	B	C	D	E	F	G	H	I	J	Solved	Time
1	Moscow SU Unpretired	+ 0:14	+ 2:32	+1 2:35	+ 1:28	+3 1:17	+2 3:47		+9 4:43	+ 0:49	+ 0:37	9	1382
2	SPb NRU ITMO 1	+ 0:11	+ 1:33		+ 1:11	–19 4:59	+1 4:45	+4 2:31	+1 3:36	+ 0:48	+ 0:23	8	1018
3	Moscow SU Trinity	+ 0:29	+2 3:56	+2 2:01	+1 1:28	+3 4:48	+3 4:02		–7 4:57	+ 1:16	+ 0:17	8	1317
4	Moscow IPT Unutterable Team	+ 0:34	+ 3:28	+ 4:41	+1 1:29	+1 1:10				+ 1:26	+ 0:26	7	834
5	SPb SU Angry Muffin	+ 0:46	+ 4:53	+ 3:12	+ 1:54		+ 1:20		–3 4:57	+ 1:17	+3 0:56	7	918
6	SPb SU 4	+ 0:27	+1 4:12	+ 3:41	+1 0:37	–2 2:43		+4 3:47	–1 4:46	+ 0:48	+ 0:16	7	948
7	SPb SU Canyon	+2 0:58	+1 2:28		+1 1:24	+1 3:22	+1 4:06			+ 1:31	+1 0:54	7	1023
8	Moscow SU SG	+2 1:56	+ 2:49	+ 3:26	+1 2:12	+5 4:39	–1 0:24			+ 0:55	+2 0:58	7	1215
9	Warsaw U 1	+2 1:02	+1 4:43		+1 1:19	+8 2:52	+10 4:58		–2 4:55	+ 0:33	+1 0:34	7	1421
10	SPb SU ITMO 2009 #1	+ 0:44	+1 3:52	+ 1:46	+ 0:59	–5 4:57	–4 4:23	–4 4:50		+ 0:48	+ 0:15	6	524
11	SPb SU: Burunduchki	+1 0:32	+1 2:38		+ 0:40	–3 4:54	+1 2:29	–6 4:59		+ 1:15	+ 1:09	6	583
12	Moscow SU T@pirenock	+1 0:39	+ 1:26		+ 1:33	–2 2:33	+5 3:29	–1 4:55		+ 1:06	+ 0:51	6	664
13	Petr Team	+1 0:12	+1 2:13		+2 1:28	+3 2:07	–3 4:58		–4 4:55	+ 1:05	+3 1:37	6	722

At 2:13 into the contest, we solved the 6th problem and were in the first place. As you can see from the last line of the above standings, we didn't solve anything in the remaining 2 hours and 47 minutes. What happened?

For problem C (statements of all problems), we couldn't come up with the simple solution, and wrote down an long expression that we needed to integrate. Since it was a polynomial, that was an easy task, but the answer didn't match the sample output. We've found a couple of bugs in the calculations, the expression was no longer a polynomial, and integrating it numerically still produced an answer that's far off the example output.

For problem F, again we couldn't come up with a O(n^2) solution - we had one that we expected to be O(n^2), but closer to the end of the contest we realized it required O(n^3) time AND memory, and couldn't come up with anything better. What made me feel bad about this problem is that a few teams have submitted 'incorrect' solutions (that sacrifice some search space to stay O(n^2)) that still passed the system tests. It might be that it's impossible to fail those under the constraints (integer coordintes up to 1000), but still that feels bad.

For problem G, we knew the solution all along but postponed writing it since it was complex and since we had 3 other solutions ready but not working. After the end of the contest, I sat down to write it and it took 40 minutes and got accepted from the first attempt.

And finally, for problem H, which is somewhat standard, our solution had a bug - it did not handle several equal vectors in the input correctly. We've discovered this bug after the contest ended, and the solution got accepted after fixing it. Again, this problem left somewhat strange feeling since at least one team managed to squeeze through an (at least theoretically) incorrect solution - just sorting along several thousand random directions. Maybe I'm just feeling grumpy because of our result :)

Still, I'd like to thank the organizers for the wonderful Ural Championship and for making it not "yet another contest" but an awesome event :) And congratulations to the Unpretired!

Ural Championship - main competition

2013-05-03T08:09:00.002+04:00

Today is the main day of the Ural Championship - the competition! About 80 teams from all over the world, and just one cup. The contest should start in about 20 minutes, and you can already follow it live in English at http://russiasport.ru/user/226/node/503740 and in Russian at http://russiasport.ru/user/226/node/534137 - right now they're presenting the participating teams.

The scoreboard will be at http://acm.timus.ru/monitor.aspx?id=152, and some spectator discussion probably at http://codeforces.ru/blog/entry/7519. My team is called "Petr team"!

Offtopic: when walking through Ekaterinburg yesterday, I've noticed that the city's central area somewhat resembles Zurich's Bellevue area: a lake which starts a river, with a large bridge over the junction that is a tourist attraction by itself (pictured on the left).

Ural Championship - day 1 : Russia vs China

2013-05-01T10:26:00.003+04:00

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!

Ural Championship - flight to

2013-04-30T16:27:00.001+04:00

The 2013 Ural Championship will take place between May 1 and May 3 in Ekaterinburg. This is an annual contest held using ACM ICPC-like rules, but this year the organizers have stepped up to make it a top-notch event, inviting many teams of the highest level. I'm currently waiting to board a plane to Ekaterniburg in the cloudy Moscow, pictured on the left.

There will be two contests. On May 1, top 5 Russian teams (as defined by NEERC results) and top 5 Chinese teams (not sure what the definition is) will face off in what seems both a unique team-of-teams competition, and also one of the last contests featuring those strong teams before they meet again in the ACM ICPC World Finals in the beginning of July.

On May 3, the Ural Championship itself will take place. In addition to 10 teams mentioned above, there will be many other strong teams from the present and from the past, including my team with Egor Kulikov and Pavel Mavrin, a past ACM ICPC World Champion team from SPb IFMO, and many others. This will be a great chance to see the best teams from the past compete against the best teams of 2013.

There will be live TV broadcast in English and Russian on May 3: http://codeforces.ru/blog/entry/7519. I will try to post updates in my blog during the entire event, except the contest(s) I will participate in myself :)

Google Code Jam 2013 is underway!

2013-04-13T07:29:00.000+04:00

The qualification round for Google Code Jam 2013 has started, and will run for about 20 more hours (until 4am on Sunday Moscow time). If you haven't already, you should take part. I'm involved with preparing problems for this competition, and hope you will like them :)

Note that the time when you submit your solution doesn't matter in the qualification round, so those who started before you have no unfair advantage. You just have to submit before the round ends.

Also note that you must not discuss the problems and solutions with others before the round ends. Online programming competitions are based in a large part on the honesty of their participants, so don't spoil it for everyone!

Prime Contest on SnarkNews

2013-01-01T14:45:00.000+04:00

...tonight at twelve o'clock on New Year's Eve, plowing through a blizzard, they came in, these people who had more interest in bringing to a conclusion, or starting anew, a useful undertaking than stunning themselves with vodka, mindlessly kicking with their legs, playing charades, and practicing flirtations in various degrees of frivolity. Here came people who would rather be with each other than anywhere else, who couldn't stand any kind of Sunday, because they were bored on Sunday. They were magi, Men with a capital M, and their motto was "Monday begins on Saturday." True, they knew an incantation or two, knew how to turn water into wine, and any one of them would not find it difficult to feed a thousand with five loaves. But they were not magi for that. That was chaff, outer tinsel. They were magi because they had a tremendous knowledge, so much indeed that quantity had finally been transmuted into quality, and they had come into a different relationship with the world than ordinary people.

Arkady Stugatsky, Boris Strugatsky

Following in a wonderful tradition, a Prime New Year's Contest is running right now on snarknews.info. The name "Prime" is a Russian pun, as the russian word "Простой" translates both as "simple" and "prime", and this contest includes problems that were given at other programming contests in 2012 but have NOT been solved by anyone. Getting at least one problem accepted there is a great achievement.

The direct link to log into the contest is http://acm.math.spbu.ru:17249/~ejudge/team.cgi?contest_id=13, and you need an Open Cup login to participate. If you don't have one, you can email new.opencup[guess what]gmail[guess what]com asking for one. The contest ends on January 10.

NEERC 2012 Results

2012-12-02T21:43:00.002+04:00

NEERC 2012 Results (full results at official site: http://neerc.ifmo.ru/information/standings.html). Teams at 2nd and 3rd places got their last problem accepted 3 seconds before the end and 24 seconds before the end, respectively :)

Rank	Team	A	B	C	D	E	F	G	H	I	J	K	L	=	Time

1	SPb NRU ITMO 1 (Kever, Korotkevich, Nigmatullin)	+ ~~14:14~~	+3 ~~105:18~~	+1 ~~42:11~~	+3 ~~238:02~~	+ ~~30:36~~	+ ~~205:53~~	+ ~~9:45~~	+ ~~19:13~~	+ ~~183:46~~	+ ~~78:00~~	-10	+1 ~~146:06~~	11	1229
2	Moscow SU 1 (Fedorov, Kaluzhin, Rogulenko)	+ ~~18:17~~	+1 ~~80:33~~	+ ~~142:36~~	+4 ~~299:57~~	+ ~~54:18~~	+ ~~183:44~~	+ ~~12:10~~	+ ~~36:50~~	.	+ ~~143:55~~	.	+1 ~~254:43~~	10	1341
3	Belarusian SU 1 (Malevich, Udavichenka, Zhgirovski)	+ ~~16:39~~	+ ~~170:35~~	+ ~~116:29~~	.	+3 ~~108:38~~	+ ~~214:43~~	+ ~~24:26~~	+ ~~29:59~~	+6 ~~299:36~~	+ ~~182:16~~	.	+ ~~153:35~~	10	1491
4	SPb SU 4 (Egorov, Kunyavskiy, Suvorov)	+ ~~13:02~~	+ ~~94:29~~	+ ~~74:20~~	+4 ~~295:35~~	+1 ~~45:00~~	+1 ~~278:39~~	+ ~~9:04~~	+1 ~~23:24~~	+2 ~~253:34~~	+3 ~~259:24~~	.	.	10	1583
5	SPb NRU ITMO 4 (Bardashevich, Kucherenko, Vedernikov)	+ ~~11:22~~	+3 ~~180:24~~	+ ~~110:13~~	.	+ ~~92:41~~	+ ~~233:45~~	+2 ~~33:57~~	+ ~~44:46~~	.	+ ~~164:04~~	.	+ ~~290:50~~	9	1257
6	Moscow SU 4 (Kumok, Permin, Tikhomirov)	+ ~~16:59~~	+1 ~~76:58~~	+ ~~176:44~~	.	+ ~~108:56~~	.	+1 ~~41:12~~	+ ~~47:44~~	+4 ~~291:35~~	+ ~~144:07~~	.	+ ~~278:57~~	9	1297
7	Moscow SU 5 (Artuhin, Ignatev, Paramonov)	+1 ~~32:19~~	+2 ~~159:37~~	+ ~~127:49~~	.	+ ~~91:53~~	+ ~~183:37~~	+ ~~51:06~~	+ ~~64:24~~	-2	+ ~~207:09~~	.	+5 ~~278:21~~	9	1352
8	Ural FU 2 (Dolgorukov, Shchelkonogov, Soboleva)	+ ~~16:34~~	+3 ~~221:44~~	+1 ~~137:18~~	.	+1 ~~281:08~~	+ ~~85:51~~	+ ~~43:21~~	+1 ~~68:16~~	.	+1 ~~172:57~~	.	+ ~~238:00~~	9	1401
9	Moscow SU 3 (Evstropov, Ivlev, Pyaderkin)	+ ~~24:49~~	+4 ~~194:06~~	+4 ~~76:55~~	.	+ ~~97:13~~	+ ~~289:16~~	+ ~~37:03~~	+1 ~~61:52~~	-1	+1 ~~196:58~~	.	+1 ~~261:24~~	9	1455
10	Moscow SU 2 (Dubinin, Mokin, Sadkov)	+1 ~~14:12~~	+1 ~~182:00~~	+3 ~~146:59~~	.	+3 ~~125:17~~	+1 ~~246:48~~	+1 ~~21:42~~	+5 ~~179:22~~	.	+1 ~~223:09~~	-1	+ ~~287:01~~	9	1743

NEERC 2012 - Комментарии

2012-12-02T09:42:00.001+04:00

15:16 - Контест закончен. Результаты будут известны сегодня вечером, через 4-5 часов. Я напишу про это отдельный пост, на английском. Трансляция на этом завершена, но если у вас остались вопросы, пишите их в комментарии, постараюсь ответить.

15:08 - ИТМО 1 стали посылать задачу K. Цитата из их первого решения:

if (rand.nextBoolean()) {
  out.println("Aastria and Abstria intersect");

15:07 - Во втором решении команды МГУ 1 по D (с тех пор уже пришло третье) была та же ошибка, что и у всех остальных команд в этой задаче - не хватает промежуточной вершины в замыкании Клини.

15:00 - Осталось 10 минут. В последние минуты посылают в основном задачу B.

14:55 - В предпоследнем решении команды Saratov SU 1 в задаче B не разобран крайний случай - когда нужно набрать вес 0. С тех пор, как я это обнаружил, пришёл ещё один сабмит, поэтому я могу теперь написать о результате предпоследнего :)

14:53 - А самое большое решение тем временем тоже у команды ИТМО 1, последний сабмит по задаче D, 10016 байт.

14:47 - Результаты конкретных посылок я не буду писать, но изменений очень много. Такое впечатление, что после заморозки команды стали делать меньше ошибок.

14:39 - Осталось полчаса до конца контеста. Уже многие команды-лидеры послали решения, и некоторые из них прошли :)

14:11 - Результаты заморожены, но видно, какие команды отправляют решения. Я где-то на полчаса ухожу обедать, но обязательно буду комментировать конец соревнования.

14:10 - Мы прорешивали эти задачи вместе с Андреем Халявиным, у нас было на момент заморозки 10 задач - не была решена задача J :) (ну и K).

14:08 - ИТМО 1 сдаёт D, им осталась только задача K. В ней основная сложность - за O(NlogN) проверить, есть ли самопересечения у ломаной, кроме этого нужно просто аккуратно всё написать.

14:06 - Тем временем, у ИТМО 1 10 задач, они по-прежнему не могут найти ошибку в D. У БГУ 9 задач, у МГУ 1, ИТМО 4, МГУ 5 по 8 задач.

14:00 - Из комментариев: "Что у СПБ ГУ 2 с В? И есть ли сабмиты на Delphi? Спасибо" Delphi на полуфинале нет с 2007 года. Решение СПб ГУ 2 не работает на тесте из условия - приходит в 2, а не в 5.

13:57 - Из комментариев: "Что у ижгту в B?" Не очень понятно. Они находят не максимальный возможный вес, само решение похоже на правильное.

13:56 - Из комментариев: "Сколько команд проходит в финал? спасибо" Это ещё не объявлено.

13:48 - Из комментариев: "Что с сабмитом СПбГУ 4 по J?" Что-то очень странное. Оно не работает на первом тесте, падая на строчке "assert(0)", и это выглядит, как будто они не разобрали один из случаев, и оставили там заглушку. Но если это происходит на первом тесте, то зачем посылать? В любом случае, очень странно что они уже очень долго ничего не посылают.

13:46 - Из комментариев: "Насколько близки БГУ2 к сдаче B?" Сдали :)

13:45 - Из комментариев: "А сколько сейчас решений на С++ у команды ИТМО 1?" A, B, F, G, I, L.

13:43 - Из комментариев: "Насколько близки MIPT 2 к сдаче I?" Мне кажется близки, решение очень похоже на верное. У них выдаётся 130 букв Q на тесте, где правильный ответ 400 букв Q.

13:41 - Из комментариев: "What can you say about difficalties in problem I? Are there some "underwater stone"?". Да, там требуется очень много аккуратности, чтобы не посчитать некоторые пики два раза.

13:39 - Из комментариев: "Петя, а не подскажешь, что с командой БГУИР 1 (Belarusian SUIR 1) - у них уже 6 неверных попыток в задаче C". У них ошибка в тесте с большим ответом, видимо проблемы с eps. Само решение похоже на правильное.

13:36 - ИТМО 1 сдали F. Теперь, видимо, Миша Кевер будет писать K, а Гена и Нияз будут искать ошибку в D.

13:32 - Может быть, вы хотите узнать ещё что-нибудь о сабмитах? Пишите в комментариях.

13:27 - Команда МГУ 3 досдала 2 задачи за 3 минуты, теперь у них 7. Пока что всё равно кажется, что составить конкуренцию МГУ 1 за выход в финал никто не сможет.

13:22 - От СПбГУ сейчас проходит в финал третья команда.

13:20 - В этом году командам приносят шарики, если они первыми сдали какую-то задачу. Пока что 6 таких шариков у ИТМО 1, один у МГУ 4, один у СПбГУ 4, и один у УрФУ 2.

13:14 - ИТМО 1 сдают I. Не очень радостная необходимость писать решение для K всё ближе. МГУ 1 сдали F, вернулись на второе место. ИТМО 1 тут же исправили проблему с пустой строкой в D - но теперь у них та же проблема, что и у СПбГУ 4.

13:11 - Тем временем МГУ 4 и ИТМО 4 сдали по 7 задач. СПбГУ 4 уже на 6 месте. У БГУ 1 уже 8 задач, они вышли на второе место.

13:05 - Первая посылка по I в Санкт-Петербурге от команды МФТИ 2. Решение у них идейно верное, но видимо есть мелкие ошибки. Идея там такая: сначала найдём, какие линейные комбинации P и Q у нас есть, потом идём динамическим программированием одновременно с двух краёв, где состоянием является сколько P мы поставили слева, и сколько справа. O(N^3) состояний и такое же время работы. Нужно идти одновременно с двух краёв, чтобы можно было посчитать всего один раз, если какой-то префикс и какой-то суффикс дают одну и ту же массу.

13:02 - Довольно странно, что задачи F и I кажутся сложными - F сдали две команды (Ural FU 2 и Saratov SU 2), I вообще никто не сдал. Мне кажется, что I проще L, а F проще D.

13:00 - Самая высокая команда, у которой нет неверных попыток - Ульяновский ГТУ, 3 задачи.

12:57 - На первых двух местах нет изменений - 8 задач у ИТМО 1, 7 задач у МГУ 1. Дальше 6 команд по 6 задач.

12:55 - 515 решений на C++, 77 решений на Java всего среди петербургских решений.

12:48 - У ИТМО 1 тоже есть неудачная попытка по D - они не заметили, что ответ должен быть непустой. Когда я тестировал задачи, я сделал ту же ошибку.

12:45 - Команда Белорусского ГУ 1 тоже сдала L. Основная идея решения этой задачи такая: для того, чтобы заблокировать все пути из левого верхнего угла в правый нижний, необходимо и достаточно заблокировать два крайних пути: тот, что получается, если все время держаться рукой за левую стену, и такой же для правой стены.

12:43 - Проблема в решении задачи L у ИТМО 1 была просто мелкой ошибкой. Из-за того, что у них есть "if" вместо цикла, они забыли одинаково обработать момент прихода в правый нижний угол в обеих ветках.

12:40 - У СПбГУ 4 проблема с построением автомата для замыкания Клини: они забывают добавить отдельное состояние для "прочли очередное повторение", и поэтому их автомат для (cb*)* принимает строку "b", сначала переходя по переходу "не брать ничего" для (cb*)*, а потом возвращаясь по переходу "взять еще одну" для b*.

12:38 - ИТМО 1 сдали L. СПбГУ 4 прошли чуть дальше, до такого теста:

(cb*)*
b

12:36 - Оба решения команд МГУ по J - конструктивное построение ответа.

12:33 - МГУ сдаёт C и J за две минуты, и выходят на второе место. МГУ 4 сдаёт J и выходят на четвёртое место.

12:31 - Задача D основана на стандартном построении автомата, который принимает только строки, удовлетворяющие заданному регулярному выражению. Чтобы автомат получится маленьким, в нем нужно сделать eps-переходы. Дальше у нас есть два автомата, и мы делаем граф, вершины которого - пары состояний автоматов, и есть переходы стоимости 0 и 1, и запускаем модифицированный поиск в ширину.

12:30 - СПбГУ послали D, но не проходит такой тест:

b*a*
a

12:27 - Как-то не очень решают сегодня команды Саратова - не больше 3 задач у них. Надеюсь, ускорятся :)

12:23 - Вот тест, который у них не работает. Похоже, у них не работает, когда ответ 1?..

15 12
....#.......##.
###.##.#.##..#.
..#..###..##...
.###..#..####.#
.#.##.##..#.#..
....#..##...##.
#.####.#..#..#.
..#....#.###.#.
#...######.#.#.
..###.##.....##
.##.#.#..#.#..#
........##.##..

12:19 - У ИТМО 1 неудачная попытка по L. Главная идея в решении у них есть, но вот детали видимо не доделаны.

12:15 - 201 команда сдала хоть одну задачу (все они сдали задачу A), 114 команд сдали задачу G.

12:14 - Самое большое решение из уже отправленных - решение команды Ижевского ГУ 2 по задаче G на С++ - 4110 байт. Довольно мало.

12:00 - Не открыты четыре задачи: D, I, K, L. D и K - стандартные алгоритмы, но много писать, I и L нужно придумать, но писать меньше.

11:59 - У команды ИТМО 1 три задачи из семи сданы на C++: A, B, G - видимо, их писал Гена. Давно ничего не сдаёт МГУ.

11:56 - ИТМО 1 сдали B, избавившись от приближённой части. 60 штрафных минут потрачено на 3 неверные попытки, плюс довольно много времени за компьютером.

11:49 - у ИТМО 1 третья неудачная попытка по B, проблема с 1000 команд остаётся.

11:46 - СПбГУ 4 сдали B с первой попытки, у них тоже 6. Отставание 86 минут.

11:42 - ИТМО 1 исправили проблему со stop, но оставили приближенный поиск весов за 666 шагов, и теперь им не хватает 1000 шагов.

11:41 - Их перебор работает за 140 миллисекунд на самом медленном тесте.

11:36 - Открыта ещё одна задача: F, её сдала команда Ural FU 2. Сама задача - просто перебор, без особых ухищрений.

11:33 - МГУ 1 сдаёт B, теперь 6-5-5, СПбГУ обгоняет МГУ на 16 минут. Решение по B у всех успешных команд одинаковое: сначала уменьшаем вес до нуля, потом наращиваем до максимума, запоминая все n весов, потом перебором всех подмножеств находим нужный вес и уменьшаемся до него.

11:31 - Решение задачи J у ИТМО 1 конструктивное. Слева тратим почти все прыжки по 3 (туда-обратно-туда), справа тратим все прыжки по два (туда-обратно), получаются три случая в зависимости от количества оставшихся прыжка по 3 (0, 1 или 2).

11:28 - Открыты две новые задачи: ИТМО 1 сдали J, МГУ 4 досдали B. Единственное изменение в их решении - ответ на первый запрос :)

11:27 - МГУ 3 досдали C, избавившись от eps как ИТМО 1 - деля в конце на НОД.

11:26 - Две команды по 5 задач, отставание 70 минут.

11:25 - СПбГУ 4 сдали C. У них решение очень аккуратное - в целых числах.

11:22 - Что-то посылок стало очень мало, одна в минуту. Первые три места те же.

11:20 - У команды МГУ 4 по задаче B решение почти правильное, но они неправильно обрабатывают самый первый запрос - отвечают на него "decline", и поэтому вообще не знают, какое число является текущим.

11:18 - Проблемы с точностью продолжаются. Они уменьшили eps до 1e-14, и теперь выводят пустой файл - не находят никакого подходящего рационального приближения.

11:16 - У команды МГУ 3 ("Тапирёнок") по задаче C как раз, похоже, проблемы с eps - неправильный ответ в тесте с большим знаменателем.

11:11 - Теперь ИТМО 1 получили неправильный ответ по B. Я на этом уже один раз обжёгся, но опять скажу, что до правильного решения довольно далеко. Во-первых, они неправильно поняли формат обмена с проверяющей программой (говорят stop после accept, а не вместо него), во-вторых, у них приближённое решение для случая, когда есть совпадающие числа - пытаются по количеству раз, когда прибавляется какое-то число из первых 666 шагов, оценить количество таких равных чисел. Хотя, может быть, это и работает.

11:07 - Первые три команды те же, но теперь в другом порядке - из-за чистой сдачи МГУ вышли на второе место с четырьмя задачами.

11:04 - У первой команды Петрозаводского ГУ 1 странное решение по C - считают, что ответ либо целый либо полуцелый. На самом деле там знаменатели до ста тысяч. Собственно решение такое - отсортируем отрезки, бинарный поиск по ответу, пытаемся для каждого отрезка поставить его подотрезок как можно левее. Соответственно, возможные препятствия - сколько-то копий ответа влезло целиком между двумя целыми точками, а копий может быть до ста тысяч.

10:58 - Прошло 50 минут, первые три места 5-4-3 задач. Дальше должно идти помедленнее. Надеюсь. Иначе задач не хватит.

10:56 - У СПбГУ 4 задачи, сдали E. Решение стандартное: идём по возрастанию степени 10, для текущей степени 10 рассмотрим все мешки с достаточно мелкими монетами, и берём жадно от самого большого мешка к меньшему, пока не наберём достаточно, чтобы обнулить текущую цифру, потом переходим к следующей степени 10.

10:52 - Добавили модуль, прошло. У них решение проще, чем я видел раньше - вместо того, чтобы использовать eps и мучиться с подбором правильного значение для него, они без eps выбирают наилучшее рациональное приближение, а потом делят числитель и знаменатель на их наибольший общий делитель, чтобы выбрать нужное приближение из равных. Здорово!

10:49 - У ИТМО 1 неудачная попытка по C. До правильного решения пока далеко. Текущая основная ошибка - забыт модуль. В задаче нужно из числа в double получить рациональное число, и при проверке, на сколько отличается приближение от самого числа, они просто их вычитают, забывая взять модуль.

10:47 - По задаче H очень чёткая картина - все решения на C++ которые используют квадратные скобки для чтения из map получают TL, все остальные решения проходят. Moscow SU 1 сразу написали нормально, вышли на третье место.

10:45 - Пока что наборы задач монотонны - у всех команд с одной задачей только A, две задачи - A и G, три задачи A, G, H.

10:43 - По три задачи у СПбГУ 4, БГУ 1 и КБТУ 1. МГУ отстаёт.

10:40 - И четвёртая задача у ИТМО 1 - задача E. Тоже на Java, значит Гена готовится писать другие задачи :)

10:39 - Тем временем есть посылки по задачам C, F, L - но проходят пока только те три, которые сдали лидеры.

10:38 - Тем временем две команды по 3 задачи, 5 команд по 2 задачи.

10:36 - Оказывается, дело было не просто в map - по умолчанию квадратные скобки создают новый элемент, и соответственно получалось слишком много элементов со значением 0. Исправили квадратные скобки на find() - прошло.

10:31 - По задаче H: У ИТМО 1 решение на Java, и использует HashMap (из маски четностей по каждому символу в количество), а у СПбГУ на C++ и использует map - и у них Time Limit Exceeded из-за лишнего логарифма!

10:29 - У ИТМО 1 третья задача - H.

10:29 - Условия: http://neerc.ifmo.ru/information/problems.pdf

10:27 - у ИТМО 1 тоже две задачи. G - 20 строк, A - 22 строки. Все четыре упомянутые задачи на C++ - значит у ИТМО 1 их писал Гена.

10:25 - Решение задачи G СПбГУ - 17 строк, решение задачи A СПбГУ - 26 строк (кроме шаблона).

10:23 - у СПбГУ уже 2 задачи. Вообще сегодня много не очень сложных задач, начало контеста будет интересным.

10:21 - ИТМО 1 тоже сдают G. Еще 8 команд сдали A.

10:18 - Первая посылка! СПбГУ 4 сдали задачу G - одну из самых простых.

10:10 - 12 задач.

10:09 - Начали!

10:04 - Контест пока не начался, последние команды рассаживаются.

09:59 - Полуфинал проходит в четырёх городах одновременно: Санкт-Петербург, Барнаул, Ташкент, Тбилиси. Участники: http://neerc.ifmo.ru/regional/teams.html.

09:56 - Результаты будут здесь: http://neerc.ifmo.ru/information/standings.html.

09:53 - Конкурс прогнозов на SnarkNews: http://srv.snarknews.info/~ejudge/showvote.cgi?data=neerc2012. ИТМО:СПбГУ:МГУ 24:5:0.

09:41 - Команды пока ещё рассаживаются по местам.

This post will contain the blog for NEERC 2012 - refresh it to get new comments. The comments will be in Russian, you can try Google Translate to read them.

NEERC 2012

2012-12-01T18:15:00.001+04:00

Tomorrow is the day of ACM ICPC Northeastern European Regional Contest - probably the strongest semifinal ACM ICPC contest of all, home for 7 of the last 13 world champion teams. Best teams from Russia and ex-USSR, except Ukraine, gather in St Petersburg to select those who will go to the world finals, which will happen in St Petersburg as well this time, in July 2013.

There are many strong teams this year, but there are three teams that stand out (in my opinion): SPb NRU ITMO 1 (tourist, mikhailOK, niyaznigmatul, combined TopCoder rating 8957, tourist and niyaznigmatul on the picture above, taken today at the practice session), SPb SU 4 (Dmitry_Egorov, kuniavski, yeputons, combined TopCoder rating 8197) and Moscow SU 1 (SergeiFedorov, SergeiRogulenko, w_AleX_w, combined TopCoder rating 7877).

I will be doing a live blog about the contest tomorrow, here at http://petr-mitrichev.blogspot.com/. The blog will be in Russian since most people watching the contest speak Russian, and I hope the Google translation won't be too bad :) Join me at 10am Moscow time tomorrow (Sunday, December 2, 2012). Time in other timezones: http://timeanddate.com/worldclock/fixedtime.html?msg=NEERC+2012&iso=20121202T10&p1=352&ah=5.

SRM 561 Screencast

2012-11-21T16:49:00.001+04:00

Here's the recording of myself solving TopCoder SRM 561.

Joy of solving easy problems

2012-11-18T00:42:00.000+04:00

Here's a problem from a recent Open Cup contest:

The similarity of two strings is defined as the length of their longest common subsequence. That, in turn, is defined as the longest string that can be obtained from both strings by dropping some characers. For example, the similarity of strings CATGT and GACTT is 3, as they have common subsequences of length 3, ATT and CTT, but no common subsequence of length 4.

You are given a string consisting of letters A, C, G, T (by far the most popular background for string problems these days :)). You need to find another string consisting of those four letters, and of the same length as the given string, that is least similar to the given string. Of course, there might be many such strings - for example, for CATGT discussed above there any many strings of the same length with similarity 1, like GAACC or TAAAC.

Can you solve it quickly?

This problem is not difficult, but I've enjoyed receiving "Accepted" from the judging system for this problem a lot. Most contests need easy problems, and it is so much better when those problems are not "easy because you just have to implement what's described in the problem statement", but "easy because you can just figure it out quickly".

Results of "kill backtracking" contest

2012-11-10T20:34:00.000+04:00

More than two years ago, I've launched a contest to crease the best (worst) testcase for a backtracking solution for a minesweeper-like problem. Rules are at http://killbacktrack.appspot.com/rules.jsp, and the contest site is at http://killbacktrack.appspot.com/.

The best testcase was actually found quickly - on the same day I've posted the contest to my blog, June 11, 2010. Here it is:

...2...
.2.....
.......
.......
.......
.....8.
.......

The trick is: we set up a pattern that has many possible solutions in the upper-left corner - but, all of those solutions but one require more than two stars. And we only have two stars available here because we have an 8 in the bottom-right corner, and just 10 stars in total - but the algorithm doesn't know and thus it tries different possible allocations of stars around 2s, then tries all possibilities for places where we don't have any adjacent digit - meaning we're free to put or not put a star there, only to find out in the end that there's not enough stars left.

This testcase requires 730272354 recursive calls. It was found by Dimon.Sobolev, felix.halim, Max.Khodak, shd, endagorion, merettm and mbuzdalov, in that order - congratulations!

The next best testcase found requires 629909575 calls:

..2....

.2.....

.......

.....8.

.......

The idea is the same but we have slightly less possibilities in the upper-left corner. Before the contest, I've had a testcase with a similar idea but not as polished as these two, requiring several hundred million calls.

I know it's been a long time, but if any of the participants remembers anything about the contest, I'd like to hear your impressions :)

Here is the breakdown of the contest website visits by country:

Petr Mitrichev Contest 10 solution ideas

2012-10-27T20:31:00.000+04:00

Petr Mitrichev Contest 10 is over, congratulations to WJMZBMR, to an unnamed team from China, to tmt514, to UPC-1 team and to scottai1 for solving 4 problems, to flashmt for being the only one to solve problem D, and to hirosegolf for being the only one to solve problem F!

You can still solve the problems for practice at http://codeforces.com/gym/100110, and you can even start a virtual contest when you'll see that standings of other teams as they appeared at the particular time into the contest.

When making this contest, I've tried to add a flavor of exploration (as opposed to just using standard algorithms), since that actually resembles my work quite a bit. Please tell whether you liked that or not!

In particular, I like problem C the most, and I'm pretty sure it can be solved for 8x8, 10x10 or even 20x20 fields - but I don't know how. We can probably set up a challenge to solve it for 10x10. My feeling is that some statistical methods should be the most powerful here.

Here are the solution ideas. Those are not complete solutions, but I hope they can guide you in the right direction. Problem statements can be found at http://goo.gl/uIW7S. You can also find a video of myself doing analysis of this contest (without problem G) in Russian at http://youtu.be/FN6FRXiQ7JE. Please don't read below if you still want to try solving those problems yourself :)

Problem A. Asymmetric Art.
This problem can be solved with backtracking. The straightforward backtracking tries all possible subsets, but that's obviously too slow. We can do several optimizations: first, let's consider the numbers in increasing order, and when taking each number we can 'mark' all numbers that we can't take anymore because of this new number. This is not fast enough, but we can additionally truncate our search by saying 'if we've reached number x, then we'll take not more than answer[n-x] more numbers', where answer[y] is the number of items in the largest quasi-symmetric-triple-free subset for n=y. Then we can find all answer[] values in under one minute, and then send a program that has all answers hardcoded for judging.

Problem B. Lots of Combinations.
We need to do two things: find (n,k) modulo 10**10, and check if (n,k) is greater than or equal to 10**10. The second part is relatively easy - if k <= n-k, then we can incrementally compute (n,1), (n,2) and stop as soon as we exceed 10**10. For the first part, we notice that it's enough to compute the answer modulo 2**10 and modulo 5**10, and then use the Chinese remainder theorem. Computing the answer modulo 5**10 is done by first calculating the power of 5 in (n,k) separately, and then calculating (n,k) with all powers of 5 removed from all numbers using the fact that we can now use division and thus just need to calculate factorials (skipping numbers divisible by 5) modulo 5**10, and numbers modulo 5**10 is a periodic sequence.

Problem C. Curiosity.
I'm pretty sure there are lots of different approaches that work in this problem. The two main directions I'm aware of is finding large blocks of data without unknowns and combining them together, or using various dynamic programming approaches that consider all possibilities. My solution is of the second kind: assume we've chosen the 6x6 field. We can then use dynamic programming to find the minimum possible number of contradictions in the input data (places where we know the color of some cell but it's different from the actual cell we're on). Now I use simulated annealing to find the 6x6 field that has zero contradictions. Of course, since all input files are given to you, you can do this without any time or memory limits and then just submit the discovered answers.

Problem D. Domination.
Since one of the dimensions is small (up to 10), we can do dynamic programming using a cut in that dimension as our state. More specifically, suppose we have filled first k columns and first p cells in the (k+1)-th column. Then we're only interested what happens on the first p cells in the (k+1)-th column and the last (n-p) cells in the k-th column. Each cell can be in four states (has '1', has '2', has '0' and doesn't have an adjacent '2', has '0' and already has an adjacent '2' (let's call this state '3')), yielding 4**10=2**20 states, but it turns out we don't need all of them - some pairs of adjacent cell states are not useful: '21' and '11' can always be replaced by '23', and '20' is plain impossible. That brings the number of states down significantly, but the program is probably still too slow. The final touch is to notice that things become periodic if we fix n and increase m.

Problem E. Easy Learning.
This one probably has even more different solutions than C. There is a lot of theory for this kind of problem that I don't want to recite here, my solution was using gradient boosting.

Problem F. Hash.
There are two main approaches here. One is called Pollard's rho algorithm, and does not depend on the hash function much, the other actually uses the specific hash function we use. Consider values x_i = hash('1000 zeroes but i-th character is 1') - hash('1000 zeroes'). Then we need to find two disjoint subsets of x_i with the same sum. Let's do the following trick: sort all x_i, and take y_1=x_2-x_1, y_2=x_4-x_3, y_3=x_6-x_5, and so on. It's not hard to see that now we have 500 numbers (2 times less), but the numbers themselves are about 1000 times less on average, and we still need to find two disjoint subsets with equal sums. Repeating this several times gets us numbers that are so small that two of them are bound to be equal. This problem has some very tricky cases when b=2 - you should watch out for those!

Problem G. RLE Size.
Here, you just need to carefully consider all cases. Each block of consecutive '?' signs can be solved on paper, based on what's to the left of it and what's to the right, and then you can just implement the formulas you've discovered on paper in your program.

Problem H. Good Students and Bad Students.
This problem can be solved greedily. Let's go from the highest numbers to the lowest numbers, and gradually fill all groups. Whenever we encounter a student that wants to be in the upper half, we place it in the first upper half that still has empty slots, if any. Whenever we encounter a student that wants to be in the lower half, we place it in the first lower half that has the corresponding upper half completely filled, if any, and in the first free upper half slot otherwise. The proof is a bit tricky but doable.

Problem I. Tennis Scores.
This was the classical 'long statement, straightforward but long code' problem. You just had to carefully calculate the probabilities of game outcomes for each player's serve, then use those to calculate the probabilities of set outcomes, and then use those to calculate the probabilities of match outcomes. It's important to notice that set outcomes depend on who's serving first in the set.

Problem J. Three Squares.
This problem was supposed to be solved numerically. One step that you need to make to avoid falling into a trap is to realize that we're not always rotating all three squares by the same angle, however improbable that might look. Here's an example:

Then you could either just iterate over possible rotation angles with a reasonable step and check whether there's intersection (since all coordinates are integers, there's no possibility to create a particularly nasty case for that solution), or, if you want a more robust solution, you can do a search in the 3-D space of angles that repeatedly splits the search space in two, but then throw away certain branches when we can see that for all possible triples in that branch there's still an intersection.

Petr Mitrichev Contest 10 - this Saturday!

2012-10-25T12:31:00.001+04:00

I will be hosting Petr Mitrichev Contest 10 this Saturday (the day after tomorrow) between 15:30 and 20:30 Moscow time (other timezones: http://timeanddate.com/worldclock/fixedtime.html?msg=Petr+Mitrichev+Contest+10&iso=20121027T1530&p1=166&ah=5).

The contest will be held at http://codeforces.com/gyms. In order to take part, you need to have an account on codeforces.com. Both teams and individual participants can join. The contest itself will be at http://codeforces.com/gym/100110, but this link will be accessible only after the start of the contest.

There will be 10 problems of varying difficulty (most are quite difficult) for 5 hours. Your solution needs to be correct on all test cases to be accepted (the standard ACM ICPC rules). People will be ranked by the number of solved problems, and by total penalty time in case they're tied on solved problems, so don't be late! :) Note that in each problem you need to read the input from a file and write the output to another file - so don't read from stdin and don't write to stdout!

Feel free to ask any questions that you might have, and also please tell if there are any issues with the contest system - it's the first time I'm using codeforces.com/gyms.

Time and venue for Petr Mitrichev Contest 10

2012-10-22T10:44:00.000+04:00

There will be an online contest called Petr Mitrichev Contest 10. Problems are all mine, previously used in Petrozavodsk trainings for top Russian teams this September but not published elsewhere. The problems are not easy, but they are of different types and thus I hope everyone will find something interesting to solve. Both teams and individual participants can join.

I'm trying to choose the best time and place for the contest. My current proposition is: 15:30 to 20:30 Moscow time this Saturday, October 27 (in other timezones: http://timeanddate.com/worldclock/fixedtime.html?msg=Petr+Mitrichev+Contest+10&iso=20121027T1530&p1=166&ah=5). Looking at the contest list at http://clist.by/ and the new Yandex contest site not mentioned there (http://contest.yandex.ru/contest/ContestList.html), all weekends are very busy, but it looks like IFMO trainings are not attended by many teams this fall and thus overlapping with it is OK.

I understand that the contest ending time in my proposition is 1:30AM in Japan and Korea and 0:30AM in China. People from Japan, Korea and China (and from Asia in general): is that too late? I'd host it earlier but there's a contest on acm.timus.ru that ends at 15:00 Moscow time that was very popular last year (http://acm.timus.ru/monitor.aspx?id=100), so I fear many contestants from Asia will take part there.

For the venue, I propose http://codeforces.com/gyms.

Please share your suggestions.

TopCoder Open 2012 Finals Commentary

2012-10-03T20:35:00.001+04:00

16:09 - That's it about this TCO. See you next year! Feel free to ask me questions in comments, I'll do my best to answer.

15:57 - Marathon results! ainu7 is the champion, Psyho is second!

15:54 - Algorithm results! Both 500s and ACRush’s 250 fail. Egor, meret, RAVEman are the only non-zero scorers, in that order. Egor is the champion!

15:48 - They’ve announced design results (which were alredy known in advance), now development.

15:31 - I've taken a look at RAVEman's and andrew's 500s, and they both only consider moves by small_constant*first_vector+other_small_constant*second_vector. I fear that doesn't work for the following reason: when the vectors are very long, close in length to the size of the board, there can be two cells that can only be reached from one another via a linear combination with larger coefficients. So I'd bet on both 500s failing.

15:29 - They are starting announcements, but they usually do other tracks first and algorithm last.

15:21 - Waiting for systest. Currently RAVEman with just 500 first, andrewzta with just 500 second, Egor, meret and ACRush with just 250s from third to fifth. Let's hope at least the champion has one working problem :)

15:18 - ACRush one more -25 on RAVEman's 500, kills RAVEman's 250, -25 on meret's 250. Meret has got -25 on both standing 500s.

15:18 - Egor has got -25 in the meantime as well. Still above meret.

15:17 - And gets -25. Meret is also preparing the testcase for RAVEman’s 500.

15:15 - ACRush is preparing a testcase for RAVEman’s 500.

15:13 - assuming both remaining 500s will also fail, it's Egor vs meret challenge battle. Both have made their moves, still less than 50 separates them. ACRush gets -25 on Egor's 250.

15:10 - meret bring’s down marek’s 250, RAVEman brings down iwi’s 500, Egor brings down Andrew’s 250.

15:08 - admins are giving out a prize for another contest during intermission, using loudspeakers. What an AWFUL decision!

15:07 - RAVEman preparing a large and presumably tricky case for 500.

15:05 - iwi submits 500 but I'm not sure he has at least tested for TLE.

15:03 - marek.cygan doing nothing, meret writing his 1000, his solution has “layers” in it - we had an idea that involved layers, too, so that can be a correct solution.

15:02 - most people fight with not-passing-examples in 500.

15:00 - apparently RAVEman's 250 is wrong, and he's fixing it... And he resubmits!

14:59 - five minutes before the end. Marek has submitted and resubmitted his 250. I’m betting on many last-second submissions.

14:52 - actually nika’s hypothesis seems to be true and it’s even not hard to construct that ordering: let’s try all possibilities for the first vertex. Then, at every step the next vertex can be constructed by doing the following: if a vertex has more edges to the already constructed vertices then it’s closer to the last marked vertex. Also, if a vertex has less edges to the vertices yet to be constructed, then it’s also closer to the last marked vertex. And the only way both those numbers can be the same for two vertices is when they’re isomorphic. So we just reconstruct the ordering greedily.

14:45 - meanwhile, andrewzta and RAVEman have submitted the 500. I have a bad feeling about andrewzta's one, though, as he has probably patched his solution quickly to pass the sample case but he couldn't rewrite a large part of his solution since I've seen it.

14:44 - if that's true, then the solution is to handle groups of isomorphic vertices at once, and then the number of states will be really small - just linear.

14:42 - nika has the following conjecture for 1000: omitting isomorphic vertices, the ordering of vertices is uniquely determined up to a complete reversal.

14:41 - andrewzta's medium seems far from completion - he iterates over pairs of vectors but his check if the given pair of vectors gives a symmetry is too simple.

14:38 - shangjingbo’s 1000 is not working only on the last example case, which is huge. Poor guy :(

14:34 - RAVEman optimizing his 500, it’s working in 0.9s on what seems to be close to worst case. Will he submit soon?

14:29 - ACRush coding 500, meret coding 1000.

14:27 - Rustyoldman reports that iwi and andrewzta are coding their 500s.

14:18 - Meanwhile, ACRush resubmits 250. Current standings: Egor (with resubmit), RAVEman and meret (no resubmit), andrewzta and ACRush (with resubmit). ACRush has also opened the 500. RAVEman is coding on 500 and shangjingbo is coding on 1000.

14:15 - About 1000: maybe something like this can work - let’s start putting numbers from 1 to N. After we’ve put numbers from 1 to K, all that matters is which vertices are assigned the last D numbers, and which vertices have an assigned number at all. And because of the restrictions, I’d hope that the number of states will be quite small. But I’m not sure how to estimate that.

14:08 - Rustyoldman reports that nobody is still coding on 500 or 1000. meret submits 250.

14:06 - By the way, bmerry was test-solving 250 and 1000 in this round, and it took him 12 and 44 minutes respectively.

14:05 - RAVEman submits 250 as well. I’m trying to think about 1000...

14:02 - andrewzta submits 250, iwi gave up on 1000 and opened 500. ACRush went to 1000 after 250. Marek.cygan gave up on 500 and went to 1000. It’s 25 minutes into the contest and it’s weird we have just 3 submissions on the 250.

13:58 - about 250: First, we can forget about E by XORin S and E, and just making player A’s goal to achieve all zeroes. How can player A win? The only way is that the entire string has just one segment of consecutive ones. But how could B allow to make that happen? If the string has length of at least 5, it looks like B can always prevent that on his move, so when length is at least 5 we should just check if A can win in one turn, and when length is at most 4, the number of states is just 16 and we can analyze the entire game using the usual means.

13:55 - meanwhile, Egor submits and resubmits the easy, adding one more small “if” clause, ACRush submits the easy a bit later but has higher score because of Egor’s resubmit. Everybody who’s opened 500 and 1000 is working on paper.

13:51 - I’ve test-solved 500 before this contest. The basic idea is - any good tiling is defined by two “basic” shift vectors. In fact, if we fix the two basic shift vectors, then all vertices are split into groups of equal vertices, and we just need to check that all vertices in each group have the same color (it won’t be a problem to form a connected piece afterwards). Now all that remains is to iterate over all possible pairs of shift vectors and carefully check everything. This can be simplified further by noticing that we can always choose one of the basic vectors to be horizontal (but it might be up to size^2 in length then).

13:50 - formal problem statements: http://apps.topcoder.com/forums/?module=Thread&threadID=763920&start=0&mc=2.

13:47 - 500: A good tiling of the plane that is split into grid cells that are colored black or white is such tiling where each piece is a connected block of cells, all pieces are equal (will coincide after some transition), including colors, and the tiling itself is periodic (for each three tiles X, Y, Z there’s a tile at Z+(Y-X)). What is the smallest possible size of piece of a good tiling which has a given rectangle as its part?

13:45 - 1000: you are given a connected undirected graph with M vertices, and must assign distinct numbers from 1 to N (N >= M) to its vertices so that adjacent vertices have numbers differing by at most D, and non-adjacent vertices have numbers differing by at least D+1. How many ways are there to do that? N is up to 100, M is up to 50, D is up to 8.

13:43 - marek goes for 500, iwi and shangjingbo go for 1000, everybody else for 250.

13:41 - 250: you are given two strings S and E of the same length, consisting of ‘0’ and ‘1’ characters. Player A can (but is not forced to) choose its substring and change all ‘0’s to ‘1’s and vice versa. Player B can (but is not forced to) do the same for just one character. Player A’s goal is to obtain string E, and player B’s goal is to prevent him from doinh so. What is the minimum number of turns he needs (assuming both play optimally)?

13:37 - everything looks fine this time. Two minutes before start!

13:35 - based on this, spectators propose a new strategy: if meret and ACRush submit a problem very quickly, code maximum flow _before_ opening it :)

13:34 - ACRush has apparently been coding most of this time, implementing Dinic algorithm for maximum flow.

13:28 - not much happening now, people are relaxing, admins say everything will be fine this time :)

13:17 - Egor and andrewzta playing air hocket. Meret, [[iwi]] walking around the room. marek.cygan talking with friends. ACRush looked at something on a laptop and went walking with a surprised face. RAVEman talking with friends as well. Can’t find shangjingbo in the arena.

13:14 - the problems turned out to be more serious than expected. The new start time is 13:40. Hysterical laughing from contestants :)

13:12 - it looks like the contest won’t start at 13:15, too. The technical issues still unresolved. This must be a very nervous time for all contestants.

13:05 - admin announcement: The match will start at 13:15.

13:02 - Egor and andrewzta are playing "Cities": each player should name a city that has not been named before that starts with the last letter of the previous named city. So far: Moscow, Warsaw, Wrozlav, Voronezh, Hurghada, Athens, Sarajevo, Osaka, Astana, Amsterdam, Malmo, Orel, Ljubljana, Astrakhan, Novosibirsk.

13:00 - marek.cygan: "The winner will be the one who can find the problemset".

13:00 - 250, 500, 1000. No news on contest start time.

12:59 - it looks like the contest start is postponed, there’re some technical issues.

12:49 - 10 minutes before the start. Andrewzta showed up, now almost everybody is coding the easy problem from the wildcard round for practice, except meret who’s writing max flow again.

12:44 - Everybody is preparing except Egor and andrewzta - the two Java coders. One doesn’t need much preparation when there’s no necessary bolierplate :) Egor is already ready, andrewzta not yet here.

12:35 - Hi! This is live commentary for TopCoder Open 2012 Algorithm Finals. The round will start in about 25 minutes. I will update this post with new comments.

TopCoder Open 2012 Finals preview

2012-10-03T18:31:00.000+04:00

This year's TopCoder Open finalists are a very diverse group of people. The most telling statistic, in my view, is the time when they first acquired 3000+ rating on TopCoder (not surprisingly, all of them did at some point :)):

andrewzta - May 2006
ACRush - September 2006
Egor - January 2007
marek.cygan - September 2007
RAVEman - June 2010
meret - July 2010
shangjingbo - December 2011
[[iwi]] - July 2012

So we have four people that I'd call veterans, playing the TopCoder algorithm games at the top level for at least five years, and that group is clearly separated from the other four, who have only reached the top recently. None have been the TopCoder Open champion yet, though!

Here are the micromatch scores between the today's finalists (the first number is how many times the person on the left has been ranked higher in rated TopCoder rounds, the second number is how many times the person on the top has been ranked higher):

Handle	ACRush	marek.cygan	andrewzta	Egor	meret	RAVEman	shangjingbo	[[iwi]]	Average
ACRush	0/0	68/23	60/27	98/37	15/2	85/14	30/2	70/9	82%
marek.cygan	23/68	0/0	51/51	73/53	6/6	57/18	13/11	41/13	56%
andrewzta	27/60	51/51	0/0	69/53	6/6	43/20	7/9	36/14	53%
Egor	37/98	53/73	53/69	0/0	16/18	90/67	41/14	71/36	51%
meret	2/15	6/6	6/6	18/16	0/0	15/14	15/9	18/11	49%
RAVEman	14/85	18/57	20/43	67/90	14/15	0/0	39/17	70/41	42%
shangjingbo	2/30	11/13	9/7	14/41	9/15	17/39	0/0	14/25	34%
[[iwi]]	9/70	13/41	14/36	36/71	11/18	41/70	25/14	0/0	34%

A funny aspect of yesterday's Wildcard round was that fourth-placed people from both Semifinals advanced, meaning that we'd get just the same set of finalists if four advanced from each Semifinal and there was no Wildcard. Historically, Wildcard round advancers has won TopCoder tournaments once (tomek in TCO 2008), got second place twice (ZorbaTHut in TCCC 2004, JongMan in TCO 2007).

What strategy would people use at today's finals? Judging from the semifinals, [[iwi]] will go Hard-Easy-Medium while everybody else will use the usual Easy-Medium-Hard order. I'm pretty sure the TopCoder admins want to make sure at most one person will solve all three problems, which might well in practice mean nobody will solve all three, so starting with Hard (or doing Easy-Hard-Medium) does look like a viable strategy. I'd propose Easy-Hard-Medium switching to Medium if Hard is not solved (and it's not clear how much is left) about 30 minutes before the end.

Also take a look at vexorian's finals preview at http://community.topcoder.com/tco12/our-algorithm-finalists/.

What other stats on finalists would you like to see? :)

TopCoder Open 2012 Wildcard Commentary

2012-10-03T01:43:00.000+04:00

19:53 - That’s it for today! Join us tomorrow for the coverage of the ultimate round - the finals! http://www.timeanddate.com/worldclock/fixedtime.html?iso=20121003T13&p1=867.

19:52 - It’s easier to tell which solutions passed than which failed :) iwi’s 1000, meret’s 500, SergeiFedorov’s and dzulgakov’s 250s. That’s it. iwi and meret to the finals!

19:49 - it looks like most 250s were indeed brought down by d=2. The results are being announced now!

19:40 - Kankuro also loses 25 in the dying minutes, on Romka's 500.

19:39 - both meret and Romka got -25 from Dmitry_Egorov's 500.

19:36 - and meret brings down SergeiFedorov's 500. Will we have two non-zero scorers to advance to the finals? :)

19:35 - Romka brings down sdya’s 500.

19:34 - dzhulgakov brings down Dmitry_Egorov's 250.

19:34 - sdya is not reading solutions, seems to have given up.

19:31 - Kankuro brings down sdya’s 250. What about 500s?

19:30 - Challenge is on! Surprisingly, no blind challenges. SergeiFedorov brings down _Romka_’s 250 and meret’s 250, but it seems that he reads them.

19:26 - Apparently iwi’s easy tries to approach (0,0) from (x,y) somewhat greedily. Is it an obvious failure or is that greedy actually some kind of gcd?.. We’ll find out soon. His code contained return “I hate math”; at some point :)

19:25 - Last seconds of coding phase were quite eventful - [[iwi]] submitted easy and SergeiFedorov resubmitted medium. [[iwi]] is the current leader.

19:24 - _Romka_ resubmits the medium, and drops to the last place. Yeah, I’d guess there’s plenty of space for bugs there as well. Looking forward to challenge phase.

19:19 - not much more action, just 4 minutes left. Everybody except iwi has 250+500, iwi has just 1000.

19:14 - SergeiFedorov submits the medium after giving up on the hard and it’s the fastest by far! He’s now in first place.

19:13 - apparently the sample cases for 250 don’t include the “all coordinates odd” case (for example d=2). I predict a lot of challenge fun :)

19:11 - iwi’s 250 is not working, he’s debugging.

19:06 - we’ve missed that dzhulgakov has resubmitted the 250. Promising for challenge phase?.. It looks like challenges will be very important if there’s nobody with 3 tasks.

19:04 - 20 minutes left. I’d say iwi is actually in a great position, as most competitors can’t get their 1000 working - many already coded up some DPs.

19:03 - SergeiFedorov gave up on hard and moved to medium.

18:59 - I guess we can speed things up by considering where will the first letter of large string go. It’s either removed at some point, in which case we get a suffix of large string and the same small string, or mapped to the first letter of the small string. So this can get us a DP on (suffix of large, suffix of small), although it’s not clear to me if we can still manage not to overcount solutions where one of consecutive letters is removed several times. Maybe we should add something like “last removed letter” to the state?.. Anyway, it’s too late to think about this.

18:57 - I can’t see iwi’s solution now, but wata tells its complexity is 50^3, not 50^6 as my proposition below.

18:54 - Currently _Romka_, sdya, Kankuro, meret, Dmitry_Egorov and dzhulgakov submitted easy and medium (and all moved on to the hard), [[iwi]] submitted hard and moved to the easy, SergeiFedorov submitted easy and moved to hard.

18:49 - So the rough approach for the 1000 is: let’s count the number of ways to obtain a substring of the small string from a substring of the large string. We do that by checking which character will be removed last, which leaves us with two substrings of the large string that should be matched somehow to the small substring, so we also have to check all ways to split the small string into two. One challenge is not to count things twice with consecutive equal letters, but that should be doable although I’m too lazy now to figure out how. Another challenge is running time: currently we have something like (50^3/6)*(50^3/6) - (the number of ways to choose a substring and a letter in it)*(the number of ways to choose a substring and a split point in it), which is about 500 million which might be too slow. But in reality we have more restrictions like length of large substring should be at least length of small substring which divides everything by 2 more, and the same for both halves which should divide by something like 2 further, bringing the total running time under control?..

18:43 - About 1000: let’s go from the long string to obtain the short string. The only way we can confuse two removals is when there’s a string of consecutive equal letters in the long string. In that case, removing each of those letters produces the same string, so we should always remove the first one of them. Still don’t know what to do next...

18:39 - forgot to post the link to statements: http://apps.topcoder.com/forums/?module=Thread&threadID=763830&start=0&mc=2

18:36 - 250 and 500 solved by Romka.

18:35 - the complexity of that solution is 50*2500 (maximum number of steps)*50(number of equations to check on each step). We can check each equation in O(1) time using hashing.

18:30 - 500 does look straightforward-ish. We will construct all strings from the end. We take any equation, and if one of its parts has more letters known in the end than the other, we reconstruct the missing letters. We repeat this until we can’t reconstruct anything, or until one of the strings is of length more than 2500. In the latter case, there’s no solution (we’ve entered an infinite cycle), and in the former case, our current suffixes are a valid solution, and the smallest one.

18:28 - Meanwhile 7 people submitted easy and [[iwi]] works on hard. Also SergeiFedorov switched to hard after easy.

18:25 - Here’s why the solution for the easy works. If we have a jump by (a,b), then we have jumps by (2a,0) and (0,2b), and also jump by (b,a). Thus, we can get jumps (2g,0) and (0,2g). Then if there’s a jump (2kg, (2m+1)g) then we can get to (0,g) using those two jumps. Otherwise, all jumps are ((2k+1)g,(2m+1)g) and we can get to (g,g) but can’t get to (0,g).

18:22 - 500: We have a system of equations a_i = b_i + c_i, where a_i and b_i are variables, c_i are constants, + is string concatenation (like s = t + “a” and t = u + “b”). We need to find the minimal sum of lengths of its solution.

18:19 - So together with Egor we kind of figured out the 250. Suppose the gcd of all coordinates of all possible jumps is g. Then there are two cases: if at least one jump has an even coordinate (after division by g), then we can get to any point where both coordinates are divisible by g. If all jumps have odd coordinates after division by g, then we can get to any point where both coordinates are divisible by g and their sum is divisible by 2g.

18:09 - Apparently my thinking gets slower as the day comes to an end. It’s kind of obvious that you have to generate all integer vectors of length sqrt(d), but where to go from there?..

18:07 - Romka has just submitted 250! I still have no clue how to solve it.

18:02 - 1000: let’s consider sequence of strings good if for each applicable i s_i is s_{i + 1} with one letter erased. You have two strings, how much different sequences exists with this two string as first and last element? String lengths are up to 50.

18:00 - 250: one starts at (0, 0) and can jump to other integer points. Each jump should be exactly sqrt(d) in length. Is it possible to get to (x,y)?

17:56 - meret has coded max flow to warm up and in case it shows up at the contest. Three minutes before start.

17:44 - One more comment from Gennady Korotkevich (made before the semifinals) - he said that almost anyone could win, but if forced to bet on somebody, he’d bet on meret. Well, now meret has to qualify from the Wildcard to live up to the expectations :)

17:43 - 250, 500 and 1000.

17:41 - Hi! This is live commentary for TopCoder Open 2012 Algorithm Wildcard Round. The round will start in about 20 minutes. I will update this post with new comments, and so will Egor who’s joining me again.

TopCoder Open 2012 Semifinal 2 Commentary

2012-10-02T20:41:00.003+04:00

15:03 - that’s it for Semifinal 2. Join me later today for the coverage of the Wildcard round at http://www.timeanddate.com/worldclock/fixedtime.html?msg=TCO+2012+Wildcard&iso=20121002T18&p1=867!

15:01 - results: dzhulgakov’s 275 and 950 fail, kalinov’s 500 and 950 fail, marcina007’s 500, wata’s 500. shangjingbo, marek.cygan, andrewzta to the finals, meret, Kankuro, Dmitry_Egorov, dzhulgakov to the wildcard.

14:48 - kalinov’s 500 will also fail.

14:42 - dzhulgakov says his hard solution fails.

14:40 - waiting for systests.

14:38 - nika says that several mediums will time out, and contestants themselves know that. Meanwhile andrewzta’s 500 goes down, and there are two more -25s.

14:37 - Right! Now everybody can see the submissions and it’s actually non-competitors who look at leaders’ solutions. (14:37:34) qiuiuu> spectators are interested in top submissions actually.

14:35 - no more action yet, we’re in the middle of the challenge phase.

14:32 - lots of people are reading shangjingbo’s and kalinov’s solutions. As in the first semifinal, solutions of leaders are attracting more interest, which looks illogical to me.

14:31 - (14:31:03) System> marcina007 unsuccessfully challenged shangjingbo's 500-point problem.

14:25 - dzhulgakov also submits the 950 with 30 seconds to go. The current situation: shangjingbo 1375, kalinov 1285, marek.cygan 1145, andrewzta 1084, dzhulgakov 1047. The only less-than-50 gap is between andrewzta and dzhulgakov. Waiting for challenge phase!

14:20 - andrewzta submits the 950. As things stand, he’s still fourth and needs two challenges to overtake the 3rd place, but solutions may fail at systest, you know :)

14:19 - Marek’s solution is the same as ours and kalinov’s. Kankuro has his solution timing out (and it has a weird “for (int t = 24; t >= 5; --t)” loop :)), andrewzta gets wrong answer and is trying to add more and more debug output.

14:14 - Marek submits the hard, 3 people with all problems now. Lining up nicely for the finals, but I’d guess there will be more submissions as the end approaches.

14:06 - pieguy opened hard abandoning his medium. wata had not opened easy, so he is either still working on medium or trying to finish hard.

14:04 - So his solution has complexity of 47 (for k) times 47*4 (for number of bad events happening) times 4 (for number of bad events on this team). The problem is solvable for much larger constraints!

13:59 - Here's how shangjingbo's solution works. We'll do inclusion-exclusion, with the basic event being “rabbit X gives a carrot to someone from his team”. Then how do we count the number of cases with T such events happening? We’ll do a DP over “first k teams, T events”. For a new team, we iterate over how many rabbits in that team give a carrot to someone in his own team, and multiply that by 4*3*.. to account for giving that carrot to different people on his team, and by c[rabbits][num] to account for different rabbits on the team taking part.

13:59 - Meanwhile we have shangjingbo and kalinov with all 3 problems, meret, andrewzta, marek.cygan, dzhulgakov and Kankuro with easy and medium, wata with medium only, pieguy, marcina007 and Dmitry_Egorov with just easy. wata is the only one that had not followed easy-medium-hard approach.

13:49 - Studio finalists are introduces quite loudly. Not sure how algo semifinalists could think about problems currently.

13:48 - shangjingbo submits the hard. His solution is even simpler than what we wrote below, he has just 47*(47*4) states in his DP. kalinov is writing something similar to our solution, but his solution doesn’t work on examples yet. meret is writing some solution which has a DP state of “5 numbers with sum up to 47”. Nobody else is writing code for 950.

13:45 - dzhulgakov also submitted medium.

13:44 - andrewzta is sitting with his notebook and pencil, trying to figure out 950.

13:43 - Marek has submitted the 500.

13:42 - Nothing changed during recent minutes, we are now into the second half of the contest.

13:36 - wata abandoned hard and switched to the medium instead.

13:34 - Easy and hard are DPs if we don’t have issues in our solutions, medium does not involve any standard approach.

13:32 - Medium submissions started to flow in, kalinov, shangjingbo, meret and andrewzta currently submitted and moved on to the hard.

13:31 - actually, 16 can be replaced by 4 since we’re just interested in how many team members are receiving the carrots, not which ones. We just have to be careful to multiply by appropriate coefficients to make sure we’re counting all possibilities.

13:28 - the complexity seems to be: 47 for the boundary position, 47*4 (actually 47*4/2) for the left-to-right number, 47*2 for the right-to-left number, 2^4=16 for the subset of this team that will receive carrots, 4 for the number of carrots from this team that go to the right (all remaining go to the left), and 4 for the number of carrots for this team arriving from the right. All in all, that’s 47*47*2*47*2*16*4*4=106314752, so that should work.

13:27 - here’s our idea for 950: let’s do a DP over “how many carrots cross the boundary between team x and team x+1 from left to right, and how many cross that boundary from right to left”.

13:26 - kalinov and shangjingbo submitted medium.

13:25 - All competitors but wata submitted easy and opened medium, wata still works on hard. This commentary is brought to you by Egor, who’ll be helping me during the rest of this round.

13:25 - 950: There are n teams with 4 players each, and each team brought 0<=a_i<=4 carrots. Find the number of ways to distribute the carrots in such a way that each carrot is given from a team to a different team. All carrots are considered distinct.

13:22 - actually, that solution was wrong, as ACRush has pointed out. The correct solution is: iterate over the set of “important” bits, and then just check if there’s a number that has one important bit set and all others cleared, for all important bits.

13:13 - 500: a set of numbers is called good when all bitwise ors of its subsets are different. What is the subset of the given set of numbers that is good and has the maximum sum of elements? Egor solved it in about 30 seconds: the “good” condition is equivalent to “each number has at least one bit that is zero in all other numbers”, so we can do a DP over “maximum sum of subset of first k numbers that have the given mask of bits as their chosen bits”.

13:11 - Three submissions for 275: shangjingbo, pieguy, meret.

13:05 - Problem statements as contestants open them: http://apps.topcoder.com/forums/?module=Thread&threadID=763801&start=0&mc=2.

13:03 - it looks to be a straightforward DP. For each segment of balls, we determine whether it's possible to remove that segment completely. To check that, we iterate over which two balls will be removed the last, and they separate that segment into subproblems.

13:01 - The 250 problem: you are given n balls (n is odd), each marked with either “left” or “right”. In one turn, you take one non-boundary ball and remove it and the ball to the left or right from it, correspondingly, until there’s one ball left. Which balls could be the last one left in the end?

12:56 - announcements are done, 3 minutes before start. There are several in-form competitors in this round: meret has won Google Code Jam just several months ago, Kankuro has won Russian Code Cup a month ago.

12:49 - There are two Java coders in this round as well: andrewzta and wata. In the first round the Java coders took the first and last place :)

12:48 - There are 11 contestants in this round. Burunduk1 couldn’t come, and he told that too late to rearrange everything.

12:48 - 275, 500, 950.

12:39 - Hi! This is live commentary for TopCoder Open 2012 Algorithm Semifinal 2. The round will start in about 20 minutes. I will update this post with new comments.

TopCoder Open 2012 Semifinal 1 Commentary

2012-10-02T16:35:00.001+04:00

11:07 - that’s all for Semifinal 1. Join me later today for Semifinal 2, and then for the Wildcard! Semifinal 2 starting time: http://www.timeanddate.com/worldclock/fixedtime.html?msg=TCO+2012+Semifinal+2&iso=20121002T13&p1=867

11:06 - and the results are in! Tom’s 250 and Dlougach’s 1000 did fail indeed, so did Tom’s 500. All other solutions passed. Egor, ACRush, RAVEman to the finals, iwi, SergeiFedorov, Romka and sdya to the wildcard round.

10:56 - not much news from contestants. It looks like Tom’s 250 and Dlougach’s 1000 will fail, no news about other solutions.

10:49 - PaulJefferys got -25 on Tom’s 500 (not 250 which we know to have a bug), and on iwi’s 500, sdya got -25 on dolphiningle’s 500 in the last seconds. Waiting for systest!

10:47 - sdya killed exod40's 500. Apparently his resubmit was not for nothing.

10:45 - Since the difference between 7th and 8th place is 60 points now, it looks like it’s almost riskless for 7th or 6th place to challenge blindly.

10:43 - No more challenges yet, most people are reading Egor’s and ACRush’s solutions.

10:40 - Romka has killed Dlougach’s 250.

10:38 - dolphinigle has resubmitted both his 250 and his 500, sdya has resubmitted his 500. It would seem that dolphinigle has the best chance at challenging.

10:35 - And Dlougach submits 250 just 7 seconds before the end! Now it’s Egor, ACRush, Dlougach at the top. MikhailOK suggests the best challenge opportunity is integer overflow in 250.

10:33 - Some other contestants from China are recording ACRush's duplicate screen using a camera on their laptop. And he does submit his 1000 just 1 minute before the end! Egor has given up on his stresstesting since his stupid solution doesn't work on the first sample.

10:24 - Egor is writing a stupid solution for 1000 to compare with his solution on random testcases - great thinking! I think that's the best thing he can spend his time on now. Meanwhile, Dlougach submits 1000, not sure if he has changed his matrix to be of size k or have optimized his solution in some other way.

10:15 - And Egor submits 1000! I was right that his solution looks good.

10:10 - ACRush, Egor and Dlougach all seem on the right track in the 1000 - they have matrix power, and they have some formulas for the matrix. Actually, Egor seems to be the closest to our solution as his matrix has explicit formulas and has size k, which is the right thing to do. ACRush computes the matrix in some complicated way which doesn’t work. Dlougach seems to have the examples passing, but his matrix is not of size k but of size k^2, which presumably causes timeouts.

10:03 - ACRush, Egor and SergeiFedorov solved 250+500, iwi solved 500, everybody else except Dlougach solved 250, Dlougach still working on 1000. His projected score on 1000 is approaching scores everybody else has on 500, though.

9:59 - most people are implementing something with disjoint-set-union structure for the 500, so it seems that everybody is on the right track and we’ll see many 500 solutions, so many people will try to solve 1000 and thus it’s possible all three finalists will solve everything.

9:51 - ACRush and Egor have 250+500, everyone but the two people who started with 1000 have 250.

9:47 - 1000 solution - it was right there, but we were missing it for some time :) So we should do a DP with “how many last numbers are linearly independent” as the state. It’s straightforward to count how many ways are there to transition from a state to another state, since all situations are essentially the same: if we know that x last numbers are linearly independent, it doesn’t actually numbers what the numbers are themselves. And of course we do fast matrix power to handle that n can be up to 10^9.

9:39 - Meanwhile, ACRush has submitted 250 and 500 and 7 other people have submitted 250.

9:37 - The problem statement looks like Burrows-Wheeler Transform, but it doesn’t seem relevant to the solution.

9:34 - The 500: given a prefix of a permutation, find the lexicographically smallest permutation with that prefix that is one big cycle. I’ve test-solved this problem before the TCO so I already know the solution, but it’s actually quite straightforward anyway. When placing each unknown number in the permutation, we place it to the smallest possible number unless that number would form a cycle, in which case we place the second smallest possible number - it will not form a cycle in that case.

9:31 - it seems that Tom’s solution in 250 has an overflow bug.

9:26 - Essentially, it means that each k consecutive numbers must be linearly dependent as vectors in Z_2^(log m). This is always true when k > log m. When k <= log m, it looks like when choosing the next number, the only thing that matters is the dimension of the space defined by the previous k-1 numbers.

9:24 - The 1000 problem: count how many ways are there to choose n numbers each up to m (where m is power of two minus one) so that for each consecutive segment of k of those numbers (segments [1st, 2nd, …, kth], [2nd, 3rd, …, (k+1)th], and so on) some non-empty subset of that segment xors to 0.

9:19 - Problem statements as contestants open them: http://apps.topcoder.com/forums/;jsessionid=0CE09A8F5F29689F1259D2D102B38B34?module=Thread&threadID=763756&start=0&mc=2.

9:18 - And ACRush readily submits the easy. It looks like there’s no catch, it’s indeed straightforward.

9:14 - This problem looks straightforward. The white connected components actually correspond to triples of consecutive equal characters in each string, and the ones adjacent to the boundary are those adjacent to the boundary in at least one string. So it looks like the answer is something like total_length_of_white_in_A*total_length_of_white_in_B*total_length_of_white_in_C+(same for black)-total_length_of_white_in_A_not_adjacent_to_bounary*(same for B)*(same for C)-(same for black).

9:11 - Dlougach and iwi start with 1000, everybody else with 250. 250 problem statement: you are given three strings A, B, C. Let’s color 3D cell (i,j,k) white if and only if A[i], B[j], C[k] are all the same. Now we need to count the number of white cells that are in the connected components adjacent to the boundary. A, B, C are up to 2500 characters.

9:08 - One minute before start.

9:05 - Spectators can log into the arena, but the contestants can’t see their messages. However, they can see who’s in the room. It looks possible to pass some information that way (as in “I will enter the room if your solution looks wrong”).

9:02 - Jessie tells everybody to line up for introductions.

9:02 - 250, 500, 1000.

8:58 - Almost nobody is preparing, people are just walking around and chatting.

8:54 - Jessie says ten minutes before start.

8:53 - There seems to be some admin activity onstage. Apparently one machine is not working?..

8:50 - Exclusive commentary from Gennady Korotkevich - it turns out Gena is closely following the TCO and is watching this semifinal. He says that it’s a pity that rng_58 doesn’t get to defend his title - couldn’t agree more.

8:48 - And here’s the (one of) prediction contest current standings: http://snarknews.info/showvote.cgi?data=tco2012.

8:45 - The overview of all semifinalists: http://snarknews.info/index.cgi?data=tco/2012/finalists&head=index&menu=index&year=2012&contest=tco&class=tco2012. This round includes those with “1” in the last column.

8:43 - It looks like we have two Java coders - Egor and theycallhimtom. Everybody else is in the ugly world of C++.

8:38 - The contestants started preparations. Not much to do since Arena and plugins are already set up, and there’s no Internet access to set up additional software. As usual, C++ coders are writing #includes.

8:33 - Hi! This is live commentary for TopCoder Open 2012 Algorithm Semifinal 1. They’ve just opened the arena but haven’t let the contestants to start preparations yet, so 12 anxious people are walking around :) I will post commentary by updating this post.

TopCoder Open 2012 - more arena flyovers

2012-10-02T03:27:00.006+04:00

Here are some more videos that illustrate how TopCoder Open works.

TopCoder Open 2012 - arena video overview

2012-10-01T09:34:00.002+04:00

Here's a less serious view at TopCoder Open 2012 - a standard "overview of arena" video, this time from a flying camera though :) Unfortunately the arena is quite dark and picture quality is quite bad. I'm trying to explain what's going on in the audio.

TopCoder Open: problem difficulty

2012-10-01T08:32:00.002+04:00

Tomorrow is the first day of TopCoder Open 2012, and I'll try to blog on its algorithm track.

Here's a small analysis of TopCoder Open problem difficulty.

Let's consider the time taken to solve the problem as the ultimate measure of problem difficulty. Then, we can estimate the difficulty of, say, a medium problem in a TopCoder Open semifinal by comparing the solving time for this problem for each competitor with the solving time for other medium problems for the same competitor. More precisely, for each competitor in each TopCoder Open onsite round, I've compared the solving time for each problem with the solving time for this competitor in all rounds that took place in the same year, and the percentage of problems that were easier plus half the percentage of problems that were of the same difficulty is the declared measure of difficulty of the onsite problem for this competitor. The median of those numbers over all competitors is the difficulty of the onsite problem.

Here's the result:

TCO '03 Semifinals 1 98% 69% 79%
TCO '03 Semifinals 2 89% 81% 73%
TCO '03 Semifinals 3 92% 87% 68%
TCO '03 Semifinals 4 82% 78% 82%
TCO '03 Finals 91% 90% 81%
TCO04 Semifinal 1 87% 80% 67%
TCO04 Semifinal 2 92% 79% 67%
TCO04 Semifinal 3 84% 51% 64%
TCO04 Wildcard 66% 88% 72%
TCO04 Finals 86% 79% 87%
TCO05 Semi 1 91% 76% 64%
TCO05 Semi 2 90% 71% 64%
TCO05 Semi 3 78% 81% 64%
TCO05 Wildcard 88% 81% 64%
TCO05 Finals 91% 77% 74%
TCO06 Semi 1 93% 77% 69%
TCO06 Semi 2 75% 77% 68%
TCO06 Semi 3 88% 77% 70%
TCO06 Wildcard 66% 84% 71%
TCO06 Finals 66% 85% 77%
TCO07 Semi 1 65% 79% 68%
TCO07 Semi 2 89% 77% 66%
TCO07 Semi 3 86% 83% 65%
TCO08 Semifinal 1 64% 81% 62%
TCO08 Semifinal 2 85% 79% 63%
TCO08 Semifinal 3 76% 80% 63%
TCO08 Wildcard 94% 44% 66%
TCO08 Championship 96% 86% 64%
TCO09 Semifinal 84% 59% 60%
TCO09 Championship 95% 87% 56%
TCO10 Semi 1 89% 84% 61%
TCO10 Semi 2 87% 75% 53%
TCO10 Wildcard 81% 86% 57%
TCO10 Final 90% 54% 61%
TCO11 Semifinal 1 74% 73% 55%
TCO11 Semifinal 2 91% 84% 57%
TCO11 Wildcard Round 87% 90% 56%
TCO11 Championship Round 83% 78% 62%

You can see that the numbers for the hard problem are lower than those for easy and medium; the reason is that I consider "not solved" to be equal to "not solved", and thus when a person solves just 60% of all hards, the perceived difficulty of any problem will not exceed 80%.

With that effect in mind, the above list reveals that 'easy' problems are hovering around 90% mark (more difficult than 90% SRM 'easy' problems), while 'medium' problems are sometimes around 80-85% difficulty but sometimes have huge drops to just average difficulty, around 50%.

Another interesting slice of the same data is the list of competitors ordered by decreasing average difficulty of onsite problems. Here's the list, limited to only those competitors with at least 5 onsite rounds:

PaulJefferys - 6 rounds - 58%
reid - 5 rounds - 59%
tomekkulczynski - 5 rounds - 64%
Eryx - 6 rounds - 65%
gawry - 7 rounds - 66%
Yarin - 5 rounds - 67%
bmerry - 7 rounds - 67%
nicka81 - 5 rounds - 67%
antimatter - 5 rounds - 70%
liympanda - 6 rounds - 70%
ACRush - 8 rounds - 71%
Im2Good - 5 rounds - 71%
Ying - 5 rounds - 71%
ploh - 6 rounds - 71%
grotmol - 6 rounds - 72%
marek.cygan - 10 rounds - 72%
John Dethridge - 9 rounds - 73%
cyfra - 5 rounds - 73%
misof - 5 rounds - 74%
andrewzta - 7 rounds - 75%
tomek - 10 rounds - 75%
SnapDragon - 8 rounds - 77%
Petr - 11 rounds - 81%

So for PaulJefferys and reid, the onsite rounds are actually not much more difficult than normal rounds (I guess partially because they don't do much SRMs, and thus "normal" rounds are the TCO qualification rounds for them), while I'm actually the one who struggles the most at the onsites :)

Russian Code Cup 2012

2012-09-09T23:06:00.000+04:00

Tomorrow is the day of the final round of Russian Code Cup (http://russiancodecup.ru/). Just several days before Gena turns 18, our last chance as Egor puts it :) There will be live broadcast on the website. I need your support! Click for date/time in all timezones.

This event itself is just marvelous! Today was mostly board game day, met a lot of friends, the atmosphere is amazing. Here's a picture from the event's place:

2012-07-03T09:46:00.002+04:00

Here are some more recent TopCoder screencasts (double-click on the video for full screen):

SRM 548:

SRM 547:

TCO12 Round 3A:

SRM 531:

SRM 529: