Editorial for DMOPC '19 Contest 5 P3 - Captivating Construction Challenge


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Tzak

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: \mathcal{O}((HV)^3) or \mathcal{O}((HV)^4)

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 S, the number of times that it can be translated in the grid. The answer is then the sum of all such S.

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 L_0. Next, iterate over all L_1, L_2, \dots, L_N, which are all translations of L_0 in the direction orthogonal to L_0 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 (x, y).

To find L_{i+1}, apply the translation (dx,dy) to L_i, where dx = \frac{y}{\gcd(x,y)} and dy = \frac{x}{\gcd(x,y)}. It can be shown that applying this translation is the smallest translation such that L_{i+1} is different from L_i and is in the directional orthogonal to L_i.

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: \mathcal{O}(HV \log^2(\min(H,V)))


Comments