Why is the answer to this problem always ( N + K — 3) / (K — 1).
Can anyone please help me. editorial is not clear.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Why is the answer to this problem always ( N + K — 3) / (K — 1).
Can anyone please help me. editorial is not clear.
Название |
---|
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)
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