TCO R1, R2 and R3 screencasts

This is another interesting-only-for-TopCoder-players post.

I've uploaded the screencasts of TopCoder Open 2009 Elimination Rounds 1 (Streaming, AVI, MOV, AVI from narod.ru), 2 (Streaming, AVI, MOV, AVI from narod.ru) and 3 (Streaming, AVI, MOV, AVI from narod.ru). The R1 screencast is quite usual, with a resubmit because of a slightly too slow solution; the R2 screencast features my frustration as I'm unable to fix my solution for the medium (I knew that it was wrong because it has failed a stress test with a dumb solution) as the time is running out, and the R3 screencast features a new challenging strategy I've discovered: look at other challenged solutions (from other rooms) to see possible mistakes to look for in the solutions of your room. This sounds obvious, but I've never used that successfully before yesterday.

I've liked the hard problem from R3 a lot. I think it is an excellent example of how dynamic programming problems can be very non-standard (and the medium problem from the same round provides an example of how they can be very standard :)) and beautiful. The regular appearance of such problems makes me sure that we'll never run out of ideas in algorithm competitions. Although I'm biased for sure.

A couple recent FAILs

I've recently lost my 1st TopCoder rating to ACRush and have already fell quite a bit behind. This is mostly due to his superb performance (great job Lou!), but it also highlighted several of the weaknesses of the choices I've made for my competing style: namely, using C# and expecting the time limit to have some margin, and not having any pre-written code to use in the competition.

All 3 last matches made me think again about those questions. In TCO09 Round 1 the hard problem turned out to have a rather strict time limit, and thus my asymptotically correct solution timed out slightly (I believe it ran within 3 seconds) and I had to resubmit, placing only 10th. SRM 436's hard was about fast multiplication of polynomials, and as I don't understand Fast Fourier Transformation good enough to code it and don't have it prewritten, I've resorted to the Karatsuba algorithm and again, my solution was very little over the time limit, so I've spent a lot of time until finally getting it under the time limit (and again, it turned out that this solution was expected to be correct by the problem authors), scored very low and placed only 15th. Today, me failing the medium problem was totally my fault (I couldn't invent the correct solution) - but even if it didn't fail, I would place below Lou because he had a pre-written implementation of the Dinic maximum flow algorithm for the hard problem, and it turned out that one could run that 2500 times under the time limit. This was not possible with the stupid maximum flow algorithm I've used, and thus I had to spent a bit more time implementing a slightly more complex approach.

I still believe that all this happening in a row is just a bad coincidence, and in the long term my strategy has more pros than cons. Next couple of months will show :)

Self-referential sentence solution

OK, here's the sentence:

This sentence has seven hundred and seventeen letters, one hundred and fifty-six words, forty-six commas, one dot, six dashes, one hundred and forty-nine spaces, eighty-two quotes, two words "This", five words "and", two words "commas", one word "dash", two words "dashes", two words "dot", one word "eight", two words "eighteen", two words "eighty", one word "eleven", one word "fifteen", two words "fifty", two words "five", three words "forty", four words "four", one word "fourteen", two words "has", four words "hundred", two words "letters", two words "nine", one word "nineteen", one word "ninety", eighteen words "one", two words "quotes", two words "sentence", two words "seven", two words "seventeen", one word "seventy", four words "six", one word "sixteen", one word "sixty", two words "spaces", one word "ten", two words "thirteen", two words "thirty", three words "three", one word "twelve", two words "twenty", twenty-one words "two", thirteen words "word" and thirty-one words "words".

Now, how to build that one? Amazingly, the following very simple approach works. Start with some string. Build a sentence that describes it. Now build a sentence that describes the previous sentence. And so on, until at one point you find that the sentences stop changing. It's true that this can never happen - but it turns out that trying out several initial strings is enough to find one that leads to a solution. It's true that the solution will be excessively long (e.g., all [one word "smth"] clauses look really unnecessary, don't they?), but who cares?

Here's the code:
http://77.41.63.3/blog/self-referential/SelfReferentialSentence.html
http://77.41.63.3/blog/self-referential/NumberSpelling.html