SPyofgame's blog

By SPyofgame, history, 8 months ago,

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$

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 ?

• +18

 » 8 months ago, # |   -28 This is proof that ratism is real !
 » 8 months ago, # |   +28 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 -_-
•  » » 8 months ago, # ^ |   +16 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.
•  » » » 8 months ago, # ^ | ← Rev. 3 →   0 :< 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 problemI solved this problem in two days with hours of observation, submission attempting and finally optimized enough to get this problem Accepted. When I asked my teacher he told me that my approach is the same as the solution but there is maybe a way of using some Combinatorics or Euclidean to solve it more effecient that I think worth to learn it or try harder. Which in some problems I dont find it wasting my time but also learn something new and tricks. And learning from your advice, not for every problems I pass I try to do so like a year ago. 
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Yes 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
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 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
 » 7 months ago, # |   0 Auto comment: topic has been updated by SPyofgame (previous revision, new revision, compare).