AbhayChandna's blog

By AbhayChandna, history, 4 years ago, In English

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?

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

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).