Wednesday, June 24, 2009

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

Sunday, June 14, 2009

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)?

Friday, June 5, 2009

TopCoder Open 2009 - Going Back

So that's how it goes. I've fallen into the same trap the second consecutive year: trying to solve the medium problem when the hard problem is actually easier, and lacking some 5-10 more minutes to finish the hard problem after that. Well, better luck next time, and congratulations to crazyb0y, UdH-WiNGeR and marek.cygan!

What are your impressions of the Final round and overall of the TopCoder Open?

Thursday, June 4, 2009

TopCoder Open 2009 - First Two Days

So how does it go here at the TCO? Well, I have to admit that the atmosphere is quite a bit more 'neutral' than usual. There's little people talking to the sponsors, there's just one or two groups at any given moment talking to each other, people spend quite a bit of time with their own laptops. Why? Maybe it's the reduced amount of Algorithm competitors, which might be more talkative than others; maybe it's that most competitors don't actually compete here, since the results for most tracks were ready before the start of the event, so they just don't come at the Arena and explore Las Vegas attractions instead. I'm sure that TopCoder will find a way to address this problem, since each TopCoder event was always very exciting, and they should become even better, not worse :)

Speaking of yesterday's semifinal round (Results) - all went well. I didn't make mistakes, I had time to stresstest both the second and third problem solutions, and I was lucky to find a reasonably easy-to-write approach for the third problem (I've used Arena compiling and testing a lot to run dummy programs that will help me see which approaches will run for reasonable time - it's probably the first time I do that at an onsite round).

And here's a couple more lousy videos. First one shows the announcement of semifinal's results (you should press the "HD" button if you want to see the handles):

And this one shows the breakfast room today - just to give you a picture of a TCO place other than the Arena. Notice how people are grouped by language (Spanish, English, Chinese, Russian):

Tuesday, June 2, 2009

TopCoder Open 2009 - Marathon Introduction

Before the start of each onsite competition, there's a brief introduction for each competitor. Here's how it happened for the first competition of the TCO, the Marathon Match track:



Any suggestions for future movies?

TopCoder Open 2009 - Arena Room Overview

Hi all,

here's how the arena room looked like yesterday during the welcome reception. Lousy quality of both video and audio, but hopefully still interesting for those of you who're not in Vegas now :)