Contest Duration: - (local time) (100 minutes) Back to Home

D - Stamp Editorial by en_translator

Assume that there are $$n$$ clusters of white squares overall, each of which contains $$x_1, x_2, x_3, \dots x_n$$ white squares.
When you make a stamp with width $$k$$, we can see the following facts:

• If $$x$$ has an element less than $$k$$, then you cannot achieve the goal.
• Otherwise, you can achieve the goal.

Also, if feasible, the minimum number of times required is $$\sum_i \lceil \frac{x_i}{k} \rceil$$. ($$\lceil y \rceil$$ denotes the minimum integer more than or equal to $$y$$)
Since this equation is monotonically increasing by $$k$$, so it is optimal to use as large $$k$$ as possible.
Therefore, the problem can be solved by calculating the formula above with $$k$$ set to $$\min A_i$$, which is the maximum feasible value.
We can find $$x$$ by sorting $$A$$, and the number of elements in $$x$$ is $$O(M)$$. The total time complexity is $$O(M \log(M)$$, where the sort is the bottleneck.

posted:
last update: