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.