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. These days are hard, the heavy raining weather still not ended yet. In day $$$d$$$, every building with height $$$h$$$ only have $$$x_d = \lfloor \frac{h}{d} \rfloor$$$ height left of good space to use, while others are sunk underwater. Every building having the same value $$$x_d$$$ on day $$$d$$$ will group together (including $$$x_d = 0$$$ which sunk completely underwater) in a way that no other building with same value $$$x_d$$$ in another group.
The question is:
Output $$$N$$$ lines, 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:
- Subtaks 1: $$$n \leq 100~ and ~a_i \leq 2.10^5$$$
- Subtaks 2: $$$n \leq 300~ and ~a_i \leq 3.10^5$$$
- Subtaks 3: $$$n \leq 300~ and ~a_i \leq 5.10^5$$$
The examples are:
My approach to this problem:
My question
Is there a better algorithm for larger $$$N$$$ ? (upto $$$10^4, 10^6$$$)
Is there a better algorithm for larger $$$a_i$$$ ? (upto $$$10^{12}, 10^{16}, 10^{18}$$$)
Can I use combinatorics or euclidian algorithm for this problem ?