https://mirror.codeforces.com/contest/1353/problem/E
On input
6
9 2
010001010
9 3
111100000
7 4
1111111
10 3
1001110101
1 1
1
1 1
0
Output is
1
2
5
4
0
0
In the second testcase, how is the output 2?
if we swithc all off all lamps, 4 moves if we switch on lamps on index 0 3 6 , moves 3 (switch off {1,2} switch on{6})
if we switch on lamps on index 1 4 7 , moves 4 (switch off {0,2,3} switch on{7})
if we switch on lamps on index 2 5 8 , moves 4 (switch off {0,1,3} switch on{8})
So , how is the minimum required moves 2?
Auto comment: topic has been updated by AbhayChandna (previous revision, new revision, compare).
In question it is given that "The garland is called k-periodic if the distance between each pair of adjacent turned on lamps is exactly k"- this means all the adjacent lamps switched ON in the answer should have distance k between them. This doesnot means that all the adjacent lamps at distance k should be switched ON. Answer for 2nd case is to turn off lamp at index 1 & 2(100100000). Switched ON index are 0 and 3 and distance between them is 3.
Ohhhhh... Got it now Thanks a lot.
we need to spend the minimum number of moves to make this string of kind contiguous block of zeros, contiguous block of ones and again contiguous block of zeros
It is not mandatory that all the lamps at a distance of k should be turned on. Instead it means that if there are two "on lamps" they must be at a distance of k from each other. Like for 111100000, turning off lamps at indices 1,2 gives 100100000.(making it as 100100100 is not needed,since it takes 3 moves).