A plus four week

Codeforces hosted two rounds during the Aug 27 - Sep 2 week. AIM Tech Round 5 took place on Monday (problems, results, top 5 on the left, analysis). All problems were solvable this time for LHiC and OO0OOO00O0OOO0O00OOO0OO, but Mikhail was considerably faster of the two. Congratulations on the win!

Manthan, Codefest 18 was the second Codeforces round of the week (problems, results, top 5 on the left, analysis). The contest really came down to the wire, with the top three participants all completing the problem set with just a few minutes to go. Tourist was just a tiny bit faster with the easier problems, and thus earned the victory. Well done!

This week also marked the end of the summer Petrozavodsk training camp (results, top 5 on the left), the 9-contest event for top Russian and some other ICPC teams to practice before the new season. Given that the second-placed team in those standings is not actually going to participate in official ICPC contests this year, the gap between the first team (current ICPC World Champions) and the rest of the field is daunting, even though it's only August yet :)

In my previous summary, I have mentioned a TopCoder problem: you are given a 10x10 grid and can place at most 150 unit cubes onto it. A cube can be placed onto a cell of the grid, or on top of another cube. Given a number s between 1 and 500, you need to place the cubes in such a way that the surface area of the resulting figure (the total number of sides of the cubes that do not touch the grid or other cubes) is equal to s, or report that it's impossible.

The approach I will describe is a very typical one for such "constructive" problems. Suppose we have found the solution for some value of s. Let's take one extra cube and put it on top of an existing one. This will increase the surface by four (five new sides appear, and one old one is covered), so we'd get a solution for s+4. We can now apply the same trick to get a solution for s+8, s+12 and so on.

Since we spend one cube to increase the surface by 4, and 150*4 is significantly bigger than 500, we won't run out of cubes.

Now the only task that remains is to find out the smallest possible figure for each remainder of s modulo 4. This can be done by analyzing a few cases by hand: it turns out the minimum solvable s for each remainder are 8, 5, 10 and 11.

During the round I've initially discovered another induction idea: just placing a new cube on the grid in such a way that it's disconnected from the rest adds 5 to the surface, so I've tried to build a similar solution modulo 5. However, in that case we do run out of space as we can have at most 50 independent cubes on the 10x10 grid, and 50*5 is less than 500.

Thanks for reading, and check back for more!