SPyofgame's blog

By SPyofgame, history, 4 years ago, In English

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 ?

  • Vote: I like it
  • +18
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it -28 Vote: I do not like it

This is proof that ratism is real !

»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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 -_-

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      :< 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 problem
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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