- 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*^{2}. 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*^{2}/*n*. It is obvious that *r* is also a divisor of *s*^{2}. 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 2*k*, 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 2*k*+ 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
```