Editorial for DMOPC '19 Contest 5 P3 - Captivating Construction Challenge
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For the first subtask, it suffices to iterate over all possible 3-tuples or 4-tuples of lattice points in the grid, and to determine whether a rectangle can be formed from these points. Measures can be taken to avoid over-counting by dividing the final result by the number of times that a given rectangle is counted in this process.
Time complexity: or
For the second subtask, we seek to eliminate the redundancy of counting congruent rectangles multiple times. To do this, we must find a method of enumerating all possible rectangles that can fit within the grid, and for each rectangle, calculate , the number of times that it can be translated in the grid. The answer is then the sum of all such .
One way of doing this is to iterate over all non-ordered pairs of points with one point on the top of the grid, and the other on the left of the grid. This fixes one side of the rectangle . Next, iterate over all , which are all translations of in the direction orthogonal to that fall on lattice points in the grid. This will enumerate over all rectangles such that the separation between the left-uppermost point and right-uppermost point is .
To find , apply the translation to , where and . It can be shown that applying this translation is the smallest translation such that is different from and is in the directional orthogonal to .
Pseudocode:
answer = 0
for x in [1, v)
for y in [0, h)
dx is y / gcd(x, y)
dy is x / gcd(x, y)
x_i is x + dx
y_i is y + dy
while x_i in bounds and y_i in bounds
add (h - y_i) * (v - x_i) to answer
add dx to x_i
add dy to y_i
Diagram:
Time complexity:
Comments
https://oeis.org/A289832
They even give a Python solution, though it needs some modifications to pass under the time limit.