← All solutions

Shortest judge solution: 1201 bytes. Shortest team solution (during contest): 1478 bytes.

This problem, despite the pictures, is not about geometry, but rather about number theory.

Consider a particular way to get a tile according to the rules. We have a rectangular tile of size x × y. Let the cut on the lower edge be a from the left and b from the right (so that a + b = x). To make a parallelogram, the cut on the upper edge has to be b away from the left edge. Similarly, if the cut on the left edge is c away from the bottom, and d away from the top (with c + d = y), then the cut on the right edge has to be d away from the bottom and c away from the top.

The area of the whole rectangle is (a + b)(c + d), while the area of the triangles we cut away is ac/2, bd/2, ac/2 and bd/2, and the area of the tile is ac + bd. A set of a, b, c, d uniquely determines a way of cutting a tile. So, to get a way to cut a tile of area A, we need to represent A as the sum of two numbers, and then represent each of those two as a product of two numbers.

The number of ways to represent a number as a product of two numbers is simply the number of divisors of the number, which we’ll denote d(n). Calculating d(n) for all n up to 500 000 is easy. So the number of ways to get a tile of size A is N(A) := ∑_x=1^A−1 d(x)d(A − x), and we need to calculate the maximum of this function over the input range.

There are two approaches that you can take here. The standard one, that most (all but one?) teams used, is to use the Fast Fourier Transform. This allows you to compute the convolution (a function like the one above) in O(B log B) time for all A up to B.

However, there is also another approach that you can take if you don’t know the FFT algorithm (although you really should learn it, if you don’t know it!). You can obviously calculate all the N(A) values in quadratic time by just applying the formula directly. This is too slow to pass within the two-second time limit, but it’s enough to do it locally on the contestants computer. This allows for a precomputation-based solution.

The limit for the source code size is 128 KB. The N(A) values go up to some 170 million in the range we care about, so even storing them as decimal representations we can fit one value in 9 bytes. So you can easily fit 12 500 numbers into your source code. So, divide the whole range [1, 500 000] into intervals of size 40 each. Precompute and store in your code the maximum value in each of these intervals. Using these values, you can easily answer queries quickly, and the precomputation should easily run within a few minutes.