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^6$$$
- Subtaks 3: $$$n \leq 300~ and ~a_i \leq 5.10^7$$$

**The examples are:**

**Example 1**

**Example 2**

**Example 3**

**My approach to this problem:**

**Observation: Harmonic Sequence**

**Subtask 1: A[i] <= 2 * 10^5**

**Subtask 2: A[i] <= 3 * 10^6**

**Subtask 3: A[i] <= 5 * 10^7**

### 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 ?

This is proof that ratism is real !

Always provide a source. It's so scary nowadays to answer any blog, especially during Codechef Long. People keep asking about problems from ongoing contests -_-

Ad here's maybe not that common opinion: beginners only waste time by modifying problems or trying to solve them for big constraints. There are thousands of problems out there that are for sure solvable.

:< I kept your advice from the last time but sometimes I found some interesting problems yet learning something new when solved it with a higher level & variant of the problems.

About the problemYes sir but it is not possible to do so in this case that I am unable to give the source since it is from a private ongoing training contest whose class is over yet and my teacher move to somewhere out to teach but there is still the problem. And I am asking for permission to public the problem

Here is the source. The author allowed me to clone to a new problem and also wondering whether there is a better solution too ^^. I have also write both Vietnamese/English version of statements

Auto comment: topic has been updated by SPyofgame (previous revision, new revision, compare).