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

How to derive this formula for this atcoder problem.
Автор spirited_away_, история, 5 лет назад, По-английски

Why is the answer to this problem always ( N + K — 3) / (K — 1).

Can anyone please help me. editorial is not clear.

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

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

In each operation, you will select K numbers. Among them one number must be 1, so the remaining K-1 elements will be replaced by 1. That's why after each operation, you will replace K-1 more numbers by 1.

Among N numbers there is already a 1, so you need to replace remaining N-1 numbers by 1.

So, total required operations = (N-1)/(K-1) But if (N-1) is not divisible by (K-1) you need one more operation.

So, answer is ceil((N-1)/(K-1)). Now calculating ceil of a division X/Y is equivalent to (X+Y-1)/Y

That's why you can write ceil((N-1)/(K-1)) = (N-1 + K-2)/(K-1) = (N+K-3)/(K-1)

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Could you please explain how in every step you turn k-1 more numbers into 1. My doubt is that if you reach the start or the end of the array you may not be able to change k-1 as you would actually be considering elements which have already turned 1

    Upd: i understood

    → Ответить