SRM 561 Screencast

Here's the recording of myself solving TopCoder SRM 561.

Joy of solving easy problems

Here's a problem from a recent Open Cup contest:

The similarity of two strings is defined as the length of their longest common subsequence. That, in turn, is defined as the longest string that can be obtained from both strings by dropping some characers. For example, the similarity of strings CATGT and GACTT is 3, as they have common subsequences of length 3, ATT and CTT, but no common subsequence of length 4.

You are given a string consisting of letters A, C, G, T (by far the most popular background for string problems these days :)). You need to find another string consisting of those four letters, and of the same length as the given string, that is least similar to the given string. Of course, there might be many such strings - for example, for CATGT discussed above there any many strings of the same length with similarity 1, like GAACC or TAAAC.

Can you solve it quickly?

This problem is not difficult, but I've enjoyed receiving "Accepted" from the judging system for this problem a lot. Most contests need easy problems, and it is so much better when those problems are not "easy because you just have to implement what's described in the problem statement", but "easy because you can just figure it out quickly".

Results of "kill backtracking" contest

More than two years ago, I've launched a contest to crease the best (worst) testcase for a backtracking solution for a minesweeper-like problem. Rules are at http://killbacktrack.appspot.com/rules.jsp, and the contest site is at http://killbacktrack.appspot.com/.

The best testcase was actually found quickly - on the same day I've posted the contest to my blog, June 11, 2010. Here it is:

...2...
.2.....
.......
.......
.......
.....8.
.......

The trick is: we set up a pattern that has many possible solutions in the upper-left corner - but, all of those solutions but one require more than two stars. And we only have two stars available here because we have an 8 in the bottom-right corner, and just 10 stars in total - but the algorithm doesn't know and thus it tries different possible allocations of stars around 2s, then tries all possibilities for places where we don't have any adjacent digit - meaning we're free to put or not put a star there, only to find out in the end that there's not enough stars left.

This testcase requires 730272354 recursive calls. It was found by Dimon.Sobolev, felix.halim, Max.Khodak, shd, endagorion, merettm and mbuzdalov, in that order - congratulations!

The next best testcase found requires 629909575 calls:

..2....

.2.....

.......

.......

.......

.....8.

.......

The idea is the same but we have slightly less possibilities in the upper-left corner. Before the contest, I've had a testcase with a similar idea but not as polished as these two, requiring several hundred million calls.

I know it's been a long time, but if any of the participants remembers anything about the contest, I'd like to hear your impressions :)

Here is the breakdown of the contest website visits by country: