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: }

A funny problem

Here's a funny problem that I've composed for the Russian IOI training camp that's happening now.

Given two numbers a and b in base 31 with at most one million digits each such that a is a multiple of b, find the last k digits (again, in base 31) of a/b, where k is not more than 10000.

SRM 443

Here's the screencast: Streaming, AVI, MOV, AVI from narod.ru.

Once again the easy-hard-medium strategy worked quite well, although it was a bit more nervous this time (a submission with about 2 minutes to go in the coding phase, and a succesfull challenge with about 20 seconds to go in the challenge phase). It's funny how I've chosen over-complicated solutions for easy and hard problems (well, for hard the main idea is common to most solutions, but my implementation is too long and it took me too many iterations to even get that one), but got the easiest to implement one for the medium under the time pressure :)

The hard problem for the round is a reasonably complex example how matrix multiplication can chime in to speed up DP. If you want to learn the more advanced DP techniques, this problem might give you a level-up :)

A lot more screencasts

I've been not updating the blog with the more recent TopCoder screencasts. I can't remember any spectacular parts of those except the last one since the matches were long ago, but here they go anyway:

TopCoder Open 2009 Round 4 (Streaming, AVI, MOV, AVI from narod.ru). Resubmissions on all 3 problems (if I remember correctly), was just lucky that nobody else got all three.

TopCoder Open 2009 Round 5 (Streaming, AVI, MOV, AVI from narod.ru). Tried my best and made almost no mistakes, but ACRush spent so little time on the hard. No challenges either, so the screencast is probably no so spectacular.

SRM 437 (Streaming, AVI, MOV, AVI from narod.ru). Couldn't figure out all the cases in the hard problem, although the approach I've chosen should be doable. Also underperformed during the challenge phase - but to be fairself-assuring, I didn't even have as many wrong 250 solutions in my room as ACRush has challenged, so there was little or no chance to fight for the win.

SRM 440 (Streaming, AVI, MOV, AVI from narod.ru). Wrote a reasonably logical solution for the hard - but rem has invented a brilliant way to express it in very simple terms, and thus his score is almost twice mine. Just one challenge with seemingly good prepared-before case - too little boundary in binary search - and then a couple of unsuccessful challenges on possible precision problems.

SRM 441 (Streaming, AVI, MOV, AVI from narod.ru). Once again my score on the hard is significantly lower than the best one due to me implementing an easy-to-invent but difficult-to-write solution - but luckily, ACRush resubmitted the medium. Several good challenges on a prepared-before case (forgetting about isolated vertices) - one more confirmation that such cases can be crucial when they exist.

SRM 442 (Streaming, AVI, MOV, AVI from narod.ru). Implementing the "TCO reslution": try the unusual strategies many times to see how they perform in the long run. Easy-Hard-Medium this time, turned out to be not so important since it was rather easy to solve all three (although rather hard not to make a bug in the medium). The screencast has an unusual feature at 48:11 - I had to stop the recording and restart it. Can anybody guess why (the screencast is no spoiler for this puzzle, so you can look at its nearby parts when figuring out the answer)?