Codeforces

My friends from Saratov are building a new system for hosting contests and beyond. They aim for everything there to be available both in English and in Russian. Today was its second beta-test, which was a contest under ACM ICPC rules for 2 hours with 3 problems. Results: http://codeforces.com/contest/2/standings. Problems: http://codeforces.com/contest/2.

Problem B is very nice. I scratched my head for a long time before getting it, yet the idea is very simple and beautiful. I won't spoil it yet - I hope you'll enjoy solving it as well :)

Problem C turned out to be a tough implementation problem for me (I solved a system of two quadratic equations on 2 variables by eliminating the squares to get a linear equation, substituting one variable from that linear equation into one of quadratic equations, and solving the result. This required a lot of care about precision issues and corner cases, and took an hour). However, I have a feeling that it is doable by some binary/ternary search. Any ideas?

World Finals Recap

Here're the comments that I've posted during the ACM ICPC 2010 World Finals in Harbin.

Read more

09:08 - Everyone is still waiting on the spectator balcony, teams
are still kept away from the competition room. Problem statements have just
been distributed to team workstations.

09:20 - Still nothing happens. The competition is more likely to start at 10 than at 9:30.

09:23 - Teams are starting to come in.

09:26 - spectators are cheering all the time as the teams take their seats.

09:32 - all teams are at their workstations.

09:35 - Bill promises to start the contest at 10am sharp.

09:39 - if you have questions for me, please post them at http://forums.topcoder.com/?module=Thread&threadID=664073. I'll check that thread from time to time.

09:43 - they're testing the new procedure for photographing the team with their first baloon and with the first baloon for any particular problem.

09:44 - by the way, is the video stream live yet? Maybe it's unnecessary for me to explain what's going on? Please answer at the forum thread above.

09:54 - I've moved to the watching auditorium so I'm watching the same video stream as everybody on the Internet (hopefully) does now.

09:58 - The contest has started!

10:00 - 11 problems. They promised to get the problems to spectators in several minutes.

10:04 - we got the problems. Hopefully they'll be available on the Internet soon as well.

10:06 - problem C is: given a n times m map, with at most w 1-cell-high horizontal walls, find out the number of cells from which you can't get to the top right corner by moving top and right. The coordinates are up to a million, w is up to a thousand. The solution seems obvious - first you compress the coordinates (find all distinct ones) to get at most 1000 distinct ones, and then do a simple DP.

10:11 - problem E is: given a 20 times 9 field with some cells occupied by rocks, find the longest path from top left corner to bottom right corner that doesn't touch itself. 20 times 9 dimensions point us to DP on subsets or something similar. I believe something like that should work: go through the table row-by-row, and keep which cells in the bottom row are connected to which, and which are not occupied at all. Quite hard to implement correctly, but the algorithm is not very complicated.

10:17 - problem G is: given at most 100 points on a plan with distinct x-coordinates, find the shortest cycle that passes through each point exactly once, goes from the leftmost point always to the right until it reaches the rightmost point, then goes always to the left until it gets back to the leftmost point. Additionally, two points are given such that the the path from left to right contains the first point, and the path from right to left contains the second point. This seems to be a very simple DP: after processing the last k points, and with the first path ending in point a and the second path ending in point b, what is the smallest total length to achieve that? This is O(n^2) states, transitions in O(n). We deal with the two special points by forcing the first path to contain the first one, and the second path contain the second one.

10:23 - problem J is: given a rectangle, is it possible to split it by repeatedly splitting it into two parts along a line parallel to a side into several rectangles with the given areas. Maybe we can solve that by trying to do a DP over (rectangle, part sizes multiset)? Since the area of the rectangle should match the sum of part sizes, it seems that the number of states will be reasonably small.

10:24 - Belarusian State University has solved problem J. Many wrong attempts on other problems.

10:29 - Cornell has solved G. I will probably stop commenting on most submissions since the scoreboard is readily available anyway.

10:33 - Problem D has been solved as well. The statement is: given a tree of castles, you need to capture them all. For each castle, you know how many soldiers you need to capture it, and how many will disappear during the process, and how many you should leave in the castle afterwards. It seems that you should just add up the last two numbers. Additionally, you may traverse each road at most twice, which essentially means you should do a normal tree traversal, and the only freedom you have is to choose the order of visiting the children of each vertex in the tree. So the solution seems to be: first, check all possible poits to start the attack - the root of the tree. Then, for each vertex we calculate the best way to capture the subtree rooted at each of its children, and then figure out the best order to visit that subtrees given the total number of soldiers required to capture each subtree X and the total number of soldiers that must be left in that subtree Y. Figuring out the order seems to be a classical problem after that - we should sort them by something like X-Y :)

10:50 - Problem I. When we split the path into four parts, each part has at most 16 cells, so we can just build all possible paths for each part (there're at most 3^16 of them, and in reality much less since we can't self-intersect, can't go outside the labyrinth and should reach the specific cell - so I hope there'll be just several thousands of those). Then, we group the paths by the set of cells they're visiting. Then, we combine the first part and the second part in all possible ways; then we combine the third and the fourth in all possible ways; then we use meet-in-the-middle to combine the complete path (for each subset covered by first two parts, we check if the complement can be covered by the last two parts).

11:12 - Problem B seems to be mostly about accuracy, as a lot of wrong submissions are showing, and many good teams are struggling with it. Generally, the first step of the solution is to separate narrow bars from large bars. To do that, let's take the smallest bar, and then all bars that are less than 50% larger than it should be narrow, and all others should be wide. After that, we should just check all given conditions carefully, and check that the lengths of the all narrow bars fall withing the specified plus-minus 5% of some number, the same for all wide bars.

11:21 - Problem A seems to be a not very complicated simulation. I expect some teams to attempt it in the first two-three hours. There's not much
I can say about the solution - you should just do what's written in the problem
statement, the constraints are reasonably small.

11:23 - the scoreboard is at Shanghai 4, Stanford and Moscow 3, others 2 and less.

11:31 - ACRush correctly suggests that the answer for problem I should be at most about 10000 (even without the constraints for 3 squares, it's in the millions), so pretty much any backtracking-style solution should work in time.

11:41 - Problem H doesn't have constraints, so it's unclear what is
the expected running time. Generally, the approach for this problem should
probably be the same as for the 2-dimensional case of this problem, which is
to go over the vertices from bottom to top, merging the lakes until they reach a point where the water can pour out of the lake. In 3-D this will require a lot of code, like finding the intersection of a horizional plane with the 3-D triangle, but the logical 'pouring' part should be the same as in 2-D case.

11:47 - ACRush points out that in problem B there's no example on the case where the barcode is reversed, which is mentioned only once in the problem statement and is easy to miss. Maybe that's why the teams are struggling with this problem.

11:56 - Problem F. The first step is to notice that since we need to find the total length, we can solve the problem separately for each triangle. Within each triangle, the countour lines are parallel to each other, so we should find one of them and the distance between them, and then carefully find the total length as the sum of two arithmetic progressions. This seems fairly easy to implement, but one has to be careful with the boundaries. There're at most 10K triangles, so we can afford some processing for each of them.

12:04 - Problem K seems to be straightforward from the algorithmic side as well. We try to place it on each side, and just have to carefully calculate
the position of the center of mass and check for stability. The geometric part
is quite standard 3-D routines (for rotating) and 2-D routines (for checking
that projection of the center of mass is at least 0.2 away from the border of the base). The most complicated part seems to be dealing with various possible 'bases' for the paperweight when the figure is not convex.

12:09 - so that's all for my guesses about each of the problems. It seems that there's no really complicated algorithmic background to any of them, and they mostly require careful implementation. Two of them are 3-D geometry, five of them
are DP, the rest are mostly straightforward but tricky implementations.

12:12 - I'm going for lunch now. Please ask your questions on the TopCoder forum thread I've liked to above :)

13:33 - The contest is going, there seem to be 5 problems that are solved by the top teams, and then there are 4 more problems that are solved by at least one team. The contest can still go to any of the top teams.

13:35 - Regarding competing together with ACRush - yeah, if they make an online contest next year, that should be a good thing to try :)

13:42 - They've finally enabled WiFi for coaches!

13:42 - From the 6 "remaining" problems, I think the ordering from the easiest to the hardest is K-F-A-I-E-H.

13:45 - They said they won't be distributing the balloons in the last hour, so I won't have any insider information to share :(

14:00 - So no more updates on accepted/rejected on the scoreboard. They're going to show the submitted runs, though.

14:03 - They told at the ICPC Live stream that SJTU have submitted their code for problem K on problem H, so it was either a mistake or they wanted to mislead other teams.

14:31 - Moscow State University and Warsaw University teams were happy
when they saw the outcomes of their respective runs, so it seems that they have
7 and 6 solved problems now, respectively.

15:16 - Results: Spb IFMO - 22nd. KTH - 12th. Fudan - 11th. Zhongshan - 10th. SpbSU - 9th. Warsaw - 8th. Saratov - 7th. Tsinghua - 6th. Petrozavodsk - 5th. KNU - 4th. Taiwan - 3rd. MSU - 2nd. SJTU - 1st.

16:23 - I've tried to upload a photo of the final scoreboard, but it turns out it is already available at http://uaimages.com/viewer.php?id=383434bord%201-21%20v2.png.

16:24 - Generally, SJTU obviously are very happy with their results, with many other medalists being disappointed they couldn't get better. For example the Bronze medal SpbSU have the same penalty time as the Silver medal Warsaw.

16:25 - Also, it seems that everyone here believes that Ural SU will also get a bronze medal for their 13th place since they're the only team except the first 12 to solve at least 6 problems.

16:25 - That's pretty much it, I think I won't be posting frequent updates here anymore, but may post some more news if I find them.

16:32 - The Moscow State University was trying to solve problem I as did the SJTU team, and both had a complete solution but failed to debug it. Spb IFMO team tried to solve two problems in the end and couldn't get any of them.

17:22 - The awards ceremony is going on. As Oleg Hristenko has rightly pointed out, we are still to announce some regional champions, and the results of the Russian teams that didn't make it to the first page of standings that was posted on the Internet.

18:00 - ICPC Challenge results: 4th place Saratov SU, 3rd place IME-USP, 2nd place Beijing Jiaotong, 1st place U of Canterbury.

18:24 - Tatiana Churina of Novosibirsk SU together with 6 other coaches (I'm being Russia-centric, I know :) got the Coaches' Award.

18:37 - Belarusian SU receives $1000 for getting the first accepted solution.

18:38 - Moscow SU (F), National U of Taiwan (I), NTU KPI (D), Kiev NU (B), Spb IFMO (C), SJTU (E), U of Wroclaw (K), U Maryland (H), Cornell U (G), Fudan U (A), Belarusian SU (J) are recognized for being the first to solve a particular problem.

18:48 - Africa and Middle East champion - British U in Egypt. Latin America champion - UF Pernambuco. North America champion - Stanford U. South Pacific champion - U of Western Australia.

18:54 - the medals are official! 4 gold + 5 silver (including SpbSU) + 4 bronze (including Ural SU). You know the rest, so I won't be posting the teams winning the medals again :)

19:02 - going to the stage with the Moscow SU team :)

ACM ICPC 2010 World Finals

I hope to be posting updates on the ACM ICPC 2010 World Finals here if I manage to get an internet connection in the Harbin Engineering University: http://77.41.63.3/icpc2010/finals.html.

A difficult problem ten years later

Here's another Russian IOI camp problem, this time one of the most difficult problems from the 1999 summer camp. Only one contestant was able to solve it back then. I wasn't. How does it look ten years later? I have testdata in case someone wants to actually write the solution :)

You are given eight pairs of numbers, x1, y1, x2, y2, ..., x8, y8. You need to find eight numbers z1, z2, ..., z8 such that (x1,y1,z1), (x2,y2,z2), ..., (x8,y8,z8) are the coordinates of the vertices of a cube with an integer side length, or to report that such numbers do not exist.

Gennady Korotkevich

Apart from interesting problems and breathtaking competition, the algorithm contests have their own astonishing personalities. Let me introduce the today's hero: Gennady Korotkevich. His name is also spelled Henadzi Karatkevich sometimes.

He is 7th top ranked TopCoder Algorithm contestant. He's won IOI 2009 (got the highest score, not just gold medal which he did several times before that). He's beaten my team (which included another TopCoder ex-target!) at an ICPC-style contest this September. He's topped all Belarusian teams in the Western Quarterfinal for NEERC 2009.

And yet he's only 14. That means he has 2 or 3 more IOIs to go. That also means I have three more TopCoder Open tournaments to fight for before he arrives :)

Some first-hand information: Gena's IOI 2009 interview in English, interview with his coach in Russian.

What feels so good about Gena is that he doesn't seem to lose the rest of his life to programming contest training, at least according to the above interview. He reminds me of myself, but of course on a greater scale. While I'm sure he's training a lot, it's important that becoming a world-class master does not affect the other aspects of his life badly.

Gennady, if you're reading this, I challenge you for a game of soccer or table tennis :)

More generally, I think this example supports the idea that the skillset (or maybe talent? that's probably a question for a separate discussion) that the programming challenges require is unique and is only partially related to CS or mathematical higher education. And seeing how many big companies are valuing that skillset in job interviews, it seems important enough for education of future software engineers to maybe borrow something from the algorithm contests. Another possible direction, of course, is that algorithm contest puzzles were just lucky to get into the limelight, and will just go away (or maybe become a pure sport) at some point when the big companies and universities discover a better way to educate and recognize the future engineers. Somewhat like Formula 1 which is becoming less and less important for the development of normal cars.

Torrent for screencasts

Okay, time to revive the blog.

Let's start with two more screencasts. I've decided to try using BitTorrent to allow downloading my screencasts even when my server is offline (the previous narod.ru solution had issues: files expire if nobody downloads them in 90 days). If you're familiar with BitTorrent, please use it to download my screencasts instead of direct links, and continue seeding them afterwards. The list of screencast torrent files I'm seeding will be up at http://sites.google.com/site/petrmitrichevtorrents/. I'll put all previous screencasts up there soon. Please report any problems you encounter or ideas you have about this.

SRM 446: Torrent, Direct Streaming, Direct AVI, Direct MOV. First of two consecutive SRMs where I didn't manage to solve all three problems, so you have a chance to see me frantically trying to complete the medium problem until the end of the contest, but needing several more minutes :( A nice successful challenge as well - the medium problem solutions were of that kind when you know they're wrong but coming up with a challenge is a problem in itself. Try staring at the same solutions as I did and challenge them yourself :)

SRM 447 was a real disaster. Ironically, I was in so bad form that I even forgot to turn on the screencast recording.

SRM 448: Torrent, Direct Streaming, Direct AVI, Direct MOV. Back to the alarmingly usual 2nd place form. The most interesting part to watch is probably squeezing the hard to run within the time limit (the final version worked 1.8s in the worst case, the first one didn't even manage to solve 40 cards case within 2s). And maybe handling the victory to ACRush in the challenge phase by doing an unnecessary unsuccessful challenge.

Later, the laptop I've been using for recording screencasts went under water and is no longer working. While I'm waiting for it to be repaired, there will probably be no more new screencasts, sorry.

Now, time to talk about something more serious. Stay tuned for philosophical posts about Gennady Korotkevich, Oleg Hristenko and OpenCup, and Moscow State University ACM preparation.

SRM 444 + answers to previous questions

Here's the SRM 444 screencast: AVI from narod.ru.

Summary: this screencast may seem a bit "slow motion". Somehow it took me much more time than usual to solve the problems (which I think were nice although probably too heavy with "standard" ideas, and I couldn't understand the problem statement of the easy problem for quite some time) - heh, it's strange to be sleepy at 3pm - but it's of course ACRush's superb performance that we should blame for the 500+ point margin :) Good job!

I wonder if there exists a non-exponential solution for the medium problem. Intuitively, it seems like with only one kind of block there might be some matching-style algorithm to solve it, but maybe the intuition is wrong. A reduction of an NP-complete problem to this problem would also be of interest, though :)

And here are the answers for the questions posted previously on this blog:

1) Why did the SRM 442 screencast interrupt in the middle? Imagine that you've coded the solution and submitted it almost without testing. Then, you realize you're not sure whether you should exchange i with j in one place in your code. You do that change, and see the code still pass all sample tests. You compile it in the arena, and find a test where it seems to break. You then change indexes back and compile in the arena again to see that the old version works on that test case. After all these changes, you realize that you don't remember which of the two versions you actually have submitted! How to find that out? Easy! Stop the screencast, open the recorded video and find the submission time :)

2) How to find last 10000 digits of x=a/b in base 31? First, if b ends with 0, then a also must end with 0, and we can remove both those zeros without changing the answer. Let's repeat that until the last digit of b isn't 0. Then, how to find the last digit x0 of the answer? Obviously, when multiplied by the last digit of b, it should give the last digit of a. But exactly one digit will satisfy that equation since 31 is prime! Then, we subtract b*x0 from a, and we can find the next-to-last digit x1 of the answer from the fact that multiplied by the last digit of b it should give next-to-last digit of a-b*x0 (the last digit of a-b*x0 is zero). We can repeat this process k times then. The final note is that one doesn't need to calculate a-b*x0 completely, as we only need the last k digits of it during the future process, and thus each step of the algorithm takes O(k), with the entire algorithm taking O(k^2).

Here's sample code that assumes a and b are given as arrays of digits with 0-th item representing the least significant digit (so the numbers are 'reversed'):

 1: int start = 0;
 2: while (b[start] == 0)
 3:     ++start;
 4: for (int i = 0; i < k; ++i) {
 5:     int x;
 6:     for (x = 0; x < 31; ++x)
 7:         if (x * b[start] % 31 == a[start + i])
 8:             break;
 9:     res[i] = x;
10: 
11:     // Subtraction
12:     int carry = 0;
13:     for (int j = start + i; j < start + k; ++j) {
14:           carry = carry + a[j] - b[j - i] * x;
15:           if (carry < 0) {
16:             int ncarry = (carry - 31 + 1) / 31;
17:             a[j] = carry - ncarry * 31;
18:             carry = ncarry;
19:           } else {
20:             a[j] = carry;
21:             carry = 0;
22:           }
23:         }
24: }