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: