Internet Problem Solving Contest

IPSC 2018

Solution to Problem P – Partitioning a square

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:


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 s2. 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 = s2/n. It is obvious that r is also a divisor of s2. 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:

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

Example output for n = 18: