This week in competitive programming

On Thursday, TopCoder SRM 606 has woken the European competitors very early in the morning (problems, results, top 5 on the left). I've slept through it, so I can't tell you much about the problems.

On Sunday, the Open Cup has resumed after the holiday break with the Grand Prix of Saratov (problems, results, top 5 on the left). The round had several nice problems requiring some creative thinking, but here's one that's easy to explain and not so easy to solve (you can find the full problem statement using the above link, this is problem G): you are given an R times C grid, where both R and C are powers of two, at least 4 and at most 256. Since R and C are powers of two, so is RC, let's say RC=2^N. You need to place some subset of the first N letters of the alphabet into each cell of the grid in such a way that all subsets are distinct (there's just enough subsets for all cells), and that for each letter, the figure formed by the cells containing that letter is 4-connected and "without holes" (its boundary should be a simple non-self-touching polygon).

Here's an example for a 4 times 4 grid:

AB..	ABCD	ABC.	A.C.
AB.D	A.CD	A..D	A...
.BCD	.BC.	.B.D	.B..
..CD	..C.	...D	....

Here's the figure formed by letter D in that grid - it's connected and without holes. The same is true for all other letters:
.D..
DDD.
D.D.
D.D.

Good luck with solving this problem, and see you next week!