Friday, February 27, 2009

Self-referential sentence

Here's one funny problem back from 1998 summer training camp for Russian IOI team hopefuls. Construct a sentence of form:

This sentence has one hundred and ninety letters, twenty one word, twelve commas, one dot, seventy five spaces, fifteen quotes, one word "This", seven words "word" and two words "twenty".

Which is completely true and has nothing missing. At the camp, there were only so many participants, so the results were checked by hand with help of a computer program, and thus some leeway was allowed in interpreting the problem statement. However, the problem doesn't suffer if we fix what's needed precisely: the sentence should be like the above but obviously with different numbers (but still spelled in "canonical" English way) and all words listed with correct amounts in case-sensitive way, with no word from the sentence missing.

I couldn't solve it back in 1998, and the solution looked like a very innovative idea to me at that time. It doesn't anymore, but I hope some of you will enjoy thinking about it. Any suggestions on the approach? Any solutions? :)

// I know that this is a well-known idea, and Googling the title of this post reveals a lot of examples and solutions :)

// To give you some context: here's me at the similar camp a year later in 1999:
at 7 comments:

Saturday, February 21, 2009

Screencasts since fall

This will probably only be interesting for TopCoder players, and they've probably already seen this on the forum, but anyway. Here're the screencasts for the SRMs that happened since my next-to-last post.

With problems not being very difficult, all came down to the challenge phase, and I was lucky to emerge in the 1st place in the end :) There was nothing particularly interesting about my challenges - I've had a pre-crafted case for the medium where I felt many can hit integer overflow, but only found one solution to challenge with it; and I've found a timeout case for a backtracking solution in the hard.

Nothing exceptional except stupid switch to C++ to use upper_bound that costed me quite a lot of time and points instead of just using binary search :)

This SRM highlights one of the techniques that I believe has improved my TopCoder results quite a bit - doing a stress-test against a stupid solution on random testcases. I've managed to resubmit the hard problem correctly because of it.

SRM 433 - no screencast - but just a comment.
Wasn't it stupid to do a last-second challenge on a possible hash collision when I was in first place with less than 25 points of margin? Yes it was.

With problems that seemed to suit me and a late resubmission by ACRush, there was no need in much challenge activity. And since I've chosen the wrong problem to challenge (who would've thought of so many ways to fail the easy? :)), the screencast should be rather boring in the challenge phase.

Very nice problems, but too slow thinking at 5AM. And very thorough example cases.
at 3 comments:

Remembering Petr Mitrichev Contest 1

Naturally, after taking part in so many programming contests, one accumulates enough ideas to start being a problemsetter. My first ACM-style contest was Petr Mitrichev Contest 1, which I set in August 2006 at the Petrozavodsk training camp, and which was later replayed at http://acm.sgu.ru. I'll try to remember how I came up with those problems.

Problem A - Balance was created when went to a website with a lot of mathematical puzzles in search of inspiration; different "find fake coin" problems didn't seem very well suited to programming competitions, but requiring to output the script and placing rather low constraints turned it from a purely-mathematical problem to quite an interesting DP requiring some accuracy.

Problem B - Cipher was created (or found in some paper, I don't know exactly) by a friend of mine as a side effect of his research.

Problem C - Hyperboloid Distance was created in search of a geometrical problem requiring an algorithmic idea. The more I thought of whether it's possible to solve it exactly or at least reduce it to a computation of  some integral, the more I liked it (since mathematical solution, if at all possible, seemed way more difficult than the approximate algorithmic one); The precision of 0.1 was there to be absolutely certain that my solution was correct and to make the problem a little easier, although I believe my solution had output much more correct digits after the decimal point.

Problem D - Real Fun was a special case in a research article that I was reading; I was amazed at the beauty and simplicity of the solution, and I still believe this problem follows the spirit of ACM ICPC-styled contests the most (among the problems of this contest).

Problem E - Hippopotamus was created as the "first problem to solve" for this contest, by adapting the idea of a simpler problem requiring exactly k iron boards among each m. This problem is quite standard, and stands out a little in terms of difficulty, but without such problem the contest could've become even more boring :)

Problem F - Ice-cream Tycoon was created because I've wanted at least one problem requiring log(n)-style data structures. There's nothing particularly interesting about it, as almost every similar question can be solved in a similar way using almost the same data structures. This is the kind of problems that's very easy to come up with.

Problem G - 4-3 King was one of the problems that I've had in mind for a long time (maybe a couple of years), but it was difficult to choose the exact variation of this idea (separate the given not-necessarily-convex n-gon in the given way) that will be both solvable and interesting to solve. I like the final version of the problem, and I've thought it would be the second easiest problem in the contest, but somehow the contestants didn't prove that :)

Problem H - Circular Railway was again a special simple case in a research article that I was reading. Luckily, it allowed for several different solutions, and thus I think was quite appropriate for the format.

Problem I - Shortest Paths was directly based on an entire research paper by David Eppstein, and I didn't expect anyone to solve it during the contest - the sole purpose was to share the amazing fact that there's such an effective solution to it with the participants :)

Comments?

And while we're talking about problemsetting, please note the two upcoming contests: These contests will take place at http://acm.sgu.ru under the standard ACM ICPC rules. They were set earlier at the Petrozavodsk training camps. For those of you who find this timing inconvenient, they'll be available on http://acm.sgu.ru afterwards as virtual contests, so that you can solve them and have the scoreboard reflect your 'current' position.
 
at 2 comments: