PROBLEM LINK:Author: Vitaliy Herasymiv DIFFICULTY:Easy. PREREQUISITES:BIT, segment tree. PROBLEM:Determine minimum amount of minutes required to paint a fence consisting of $N$ parts, in green color. Each part is initially painted either red or green. We can chose an index $X$, and flip colors in range $[X,\min(X+K,N1)]$ in one minute. QUICK EXPLANATION:Consider the index where first red is occurring as $T$, flip the colors in range $[T,\min(N,T+K1)]$. Keep repeating this step until each part is colored green. EXPLANATION:First lets see how to solve the problem, later we can see the proof of correctness. Consider the index at which first red is occurring and call it $T$, flip the colors in range $[T+\min(N,T+K1)]$. Keep repeating the given procedure unless whole array is green. After each iteration value of $T$ will be increasing, so the given algorithm will terminate in less than or equal to $N$ steps. Each iteration may take $O(N)$ amount of time, hence the given algorithm will be taking $O(N^2)$ time. As the $N$ can be $10^5$ in the given problem, we need to optimize our solution. We can solve the problem in $O(N\log N)$ time. Range flip can be seen as adding $1$ to the range and value of color can be obtain using sum at that particular index modulo $2$. If the $\text{sum} \%2$ is $0$, then color at that index will be same as the initial one or flipped otherwise. The range updates and queries can be done in $O(\log N)$ time using BIT or segment tree. O(N) Solution: It can be done in $O(N)$ as well. Adding $1$ to range $[L,R]$ can be seen as adding $1$ to index $L$ and adding $1$ to index $(R+1)$. When we want to retrieve the value at specific index, we need to take the prefix sum upto that index. See sub problem 1 of this editorial for more details. Proof: The given procedure can be proved correct using the following lemmas.
Solution:Setter's solution can be found here
This question is marked "community wiki".
asked 21 Mar '15, 02:10

It can also be solved with a queue in $O(N)$. Scan left to right, and in the queue, keep the locations of all flips in the last $K$ parts. When processing a part $i$, first pop from the front of the queue while the element at the front of the queue $x$ satisfies $xi\ge K$. If a part is green and the queue's size is odd, or if a part is red and the queue's size is even, add $i$ to the queue, and add 1 to the answer. answered 23 Mar '15, 00:10

I solved it without using BIT or segment tree. answered 23 Mar '15, 00:24

My solution is a bit simpler:
answered 23 Mar '15, 00:41

There is no need of segment tree or bit . http://www.codechef.com/viewsolution/6566527 This problem can be solved by looping from 0 to n1 and increment the answer whenever current alphabet is 'R' and number of flips are even or current letter is 'B' and number of flips are odd . Complexity O(n) . Pseudo code : Input : arr , n , k // string , string size , sub string size which can be flipped answer := 0 , flips :=0 , mark[]:={0} for i from 0 to n1 : flips = flips + mark[i] if arr[i] is 'R' and flips is even OR arr[i] is 'G' and flips is odd : increment answer by 1 mark[i+1] = mark[i+1] + 1 mark[i+k] = mark[i+k]  1 // marking the subsegment from i to i+k1 to be flipped end if end for print answer answered 23 Mar '15, 17:57
For those who don't understand what he did , I am giving some clues. Actually he maintained a mark array corresponding to the input string.When we encounter 'R' , we check if corresponding flips at that position is even. If it's even we have to flip it so we add +1 to our answer. Similarly for Green we add +1 to answer if corresponding number of flips are odd. Now , we have to maintain the array if we do the flip and add +1 to our resulting minutes. For this , we are marking the array at points (i , i+k1).
(24 Dec '15, 04:27)

@rajat1603, This problem can be solved by looping from 0 to n1 and increment the answer whenever current alphabet is 'R' and number of flips are even or current letter is 'B' and number of flips are odd . Complexity O(n) . Hey,I am not able to feel your conclusion. Please help... answered 24 Mar '15, 16:40

@rajat1603 can you please explain the idea behind your algo?? EDIT: Got it. Awesome solution answered 28 Mar '15, 22:46

@amitpandeykgp I am not getting the Subproblem 1 of the editorial you mentioned here. Let the array be: a[]= {1,2,4,1,2,1}, X=3 and b[] be the updated array a[] at each step update[1,3]=> a[]= {4,2,4,2,2,1} //a[1]+=3 n a[4]=3 while b[]= {4,5,7,1,2,1} update[2,4]=> a[]= {4,5,4,2,1,1} //a[2]+=3 n a[5]=3 while b[]= {4,8,10,4,2,1} update[3,6]=> a[]= {4,5,7,2,1,1} //a[3]+=3 n a[7]=3 while b[]= {4,8,13,7,5,4}
query[1,4]= sum[4]sum[0]=43 while from b[1,4] we get 32 query[2,5]= sum[5]sum[1]=52 while from b[2,5] we get 33 I have read it 23 times and still not getting. Please help. answered 30 Mar '15, 01:48

can some one explain last comment please how we get query result correctly answered 28 May '15, 00:03
