Internet Problem Solving Contest

• One possible correct output for P1
• One possible correct output for P2
• Python 3 program solving both subproblems
• C++ program to check submissions

The easy subproblem was easily solvable by hand. The smallest square that can be divided into four regions is a 2 × 2 square. One possible correct output looks as follows:

                                            ab
                                            cd

For the hard subproblem, we can start by making the following observation: We want to take a square of some size s and divide it into n equally-large regions. Obviously, that is only possible if n divides s². Thus, if we find the smallest such s and successfully construct an s × s square, we can be certain that it’s optimal.

Suppose we have said s × s square. How can we divide it into n connected regions? There are many techniques that work. For example, you could choose any Hamiltonian path (i.e., a path that visits each cell of the square once) and split it into n segments.

Probably the easiest solution in terms of implementation is the following one:

The size of each region will be r = s²/n. It is obvious that r is also a divisor of s². But we can show a stronger statement: in fact, if s is as small as possible, r must be a divisor of s. This is because for any prime p we have two possibilities:

• If the largest power of p that divides n is even, say 2k, then s divisible by p^k and r is not divisible by p.
• If the largest power of p that divides n is odd, say 2k + 1, then s divisible by p^k + 1 and r divisible by p.

Thus, for the construction we simply split each row of the square into s/r regions.

Example output for n = 18:

6
aabbcc
ddeeff
gghhii
jjkkll
mmnnoo
ppqqrr