When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Wondering if I can optimize my algorithm

Revision en7, by SPyofgame, 2020-11-08 20:43:41

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


The examples are:

Example 1
Example 2
Example 3


My approach to this problem:

Subtask 1: A[i] <= 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)