Wondering if I can optimize my algorithm

Revision en8, by SPyofgame, 2020-11-08 20:55:42

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:

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 5 * 10^7$

Example 1
Example 2
Example 3

### My approach to this problem:

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}$)

#### History

Revisions

Rev. Lang. By When Δ Comment
en17 SPyofgame 2020-11-28 11:53:17 1 Tiny change: '----------\n\n------' -> '---------- \n\n------'
en16 SPyofgame 2020-11-28 11:52:43 587
en15 SPyofgame 2020-11-23 08:27:18 1 Tiny change: 'nificantly\n\ncpp' -> 'nificantly.\n\ncpp'
en14 SPyofgame 2020-11-12 20:11:18 4
en13 SPyofgame 2020-11-10 17:15:42 71
en12 SPyofgame 2020-11-10 10:12:24 28 Tiny change: ' cant.\n\n### **' -> ' cant.\n\n----------\n\n----------\n\n### **'
en11 SPyofgame 2020-11-09 18:34:14 43
en10 SPyofgame 2020-11-09 18:33:31 106
en9 SPyofgame 2020-11-09 18:23:14 222
en8 SPyofgame 2020-11-08 20:55:42 2 Tiny change: '$a_i \leq 3 * 10^7$\n' -> '$a_i \leq 5 * 10^7$\n'
en7 SPyofgame 2020-11-08 20:43:41 6 Tiny change: '$a_i \leq 10^9$\n\n\n---' -> '$a_i \leq 3 * 10^7$\n\n\n---'
en6 SPyofgame 2020-11-08 20:13:13 249
en5 SPyofgame 2020-11-08 20:10:58 923 Tiny change: 'ty is $O(n log n \times ' -> 'ty is$O(n\ log\ n + n \times ' (published)
en4 SPyofgame 2020-11-08 19:44:15 4420
en3 SPyofgame 2020-11-08 18:42:32 3161 Tiny change: ': $x[d] = {\lfloor \' -> ':$x[d] = \{\lfloor \'
en2 SPyofgame 2020-11-02 19:58:26 186
en1 SPyofgame 2020-10-28 15:51:50 865 Initial revision (saved to drafts)