I come to a fun problem, and after I tried hard to solve it, I curiously to find better algorithm, but I cant.
The problem is:
There are $$$N$$$ buildings with $$$a_1, a_2, \dots, a_n$$$ metters height. Because of the bad weather, at day $$$d$$$, every building with height $$$h$$$ only have $$$x_d = \lfloor \frac{h}{d} \rfloor$$$ metters height good space left to use (others are sunk underwater). Every building having the same value $$$x_d$$$ on day $$$d$$$ will group together (no other building with same value $$$x_d$$$ in another group).
The question is:
In each size $$$s$$$ from $$$1$$$ to $$$n$$$, what is the earliest day $$$d$$$ that have at least one group of size $$$s$$$ (if there is no suitable day then output -1)
The constraints are:
- $$$N \leq 300$$$
- $$$a_i \leq 10^9$$$