spirited_away_'s blog

How to derive this formula for this atcoder problem.
By spirited_away_, history, 6 years ago, In English

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

Can anyone please help me. editorial is not clear.

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

Comments Comments (2)
| Write comment?
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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)

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    → Reply