Блог пользователя SPyofgame

Автор SPyofgame, история, 4 года назад, По-английски

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 ?

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

This is proof that ratism is real !

»
4 года назад, # |
  Проголосовать: нравится +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 -_-

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
      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 problem
  • »
    »
    4 года назад, # ^ |
    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

  • »
    »
    4 года назад, # ^ |
    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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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