Wondering if I can optimize my algorithm

Revision en10, by SPyofgame, 2020-11-09 18:33:31

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:

Example 1
Example 2
Example 3


My approach to this problem:

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en17 English SPyofgame 2020-11-28 11:53:17 1 Tiny change: '----------\n\n------' -> '---------- \n\n------'
en16 English SPyofgame 2020-11-28 11:52:43 587
en15 English SPyofgame 2020-11-23 08:27:18 1 Tiny change: 'nificantly\n\n```cpp' -> 'nificantly.\n\n```cpp'
en14 English SPyofgame 2020-11-12 20:11:18 4
en13 English SPyofgame 2020-11-10 17:15:42 71
en12 English SPyofgame 2020-11-10 10:12:24 28 Tiny change: ' cant.\n\n### **' -> ' cant.\n\n----------\n\n----------\n\n### **'
en11 English SPyofgame 2020-11-09 18:34:14 43
en10 English SPyofgame 2020-11-09 18:33:31 106
en9 English SPyofgame 2020-11-09 18:23:14 222
en8 English 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 English 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 English SPyofgame 2020-11-08 20:13:13 249
en5 English 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 English SPyofgame 2020-11-08 19:44:15 4420
en3 English SPyofgame 2020-11-08 18:42:32 3161 Tiny change: ': $x[d] = {\lfloor \' -> ': $x[d] = \{\lfloor \'
en2 English SPyofgame 2020-11-02 19:58:26 186
en1 English SPyofgame 2020-10-28 15:51:50 865 Initial revision (saved to drafts)