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

Help with understanding the editorial
Автор Flvx, история, 22 месяца назад, По-английски

For problem this, the editorial suggests a naive way in which we break the chain and linearly kill all the monsters(then they present an optimization based on this), how do we know that this is the optimal way? Why can't I first kill monsters from one segment and then once the cascading effect stops, I jump to another monster which(say) has the highest b[i]/a[i] ratio? I need help in understanding this. Thanks in advance. (You can ask for further clarification from me if required)

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

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

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

→ Ответить
»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Once you kill the first monster, you are left with two segments and the cycle breaks (as described in the tutorial). When the cycle is broken, it makes no sense to shoot at a monster that is in the middle of the segment. This is because the explosion effect does not affect both adjacent monsters, only the next one. when the health of some monster i becomes 0 or less than 0, it dies and explodes, dealing bi damage to the next monster (monster i+1, if i<n, or monster 1, if i=n — this is a quote from the problem statement.

So the monster with lowest index in each segment will not get affected by an explosion no matter what. Therefore it is optimal to shoot it first and kill it.

→ Ответить
  • »
    »
    22 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    So basically what I understood after reading this and the editorial, once the chain is broken at a point, we cannot reach the points in front segment using the points in another segment (since the explosion will not affect them as the monster in between is already dead) and shooting the previous segment is suboptimal as the explosions from the first segment cycle over and reduce the cost of the second segment. Is that correct?

    → Ответить
    • »
      »
      »
      22 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Kind of yes. I actually misunderstood something. When the first monster is killed, only one segment remains, but the cycle is broken. Instead, a line of monsters forms. So say u have 10 monsters labeled 1 to 10. Then, if u kill the 5th monster, u will have a line of monsters in the following order: 6 7 8 9 10 1 2 3 4. Now notice that the 6th monster (the monster which is first in the line) can never be affected by an explosion since the monster before it (5th monster) has already died. Therefore it is optimal to kill the 6th monster first. Using a similar logic, u can decipher that the order in which u kill the monsters is the order of the line. In this case (6 7 8 9 10 1 2 3 4). So the only thing that matters is the first monster that u kill. Then just greedily kill all the monsters in the order of the cycle.

      → Ответить