### PROBLEM LINK:

Author: Vitaliy Herasymiv

Tester: Istvan Nagy

Editorialist: Amit Pandey

### 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,N-1)] in one minute.

### QUICK EXPLANATION:

Consider the index where first red is occurring as T, flip the colors in range [T,\min(N,T+K-1)]. 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+K-1)]. 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.

- Order of the updates doesn’t matter.
- Starting index of any 2 updates will be different, as 2 updates at same starting position will cancel each other.
- If we sort the minimum update sequence and suppose first update happens at index i, then at each index in range [0,i-1] color must be green and at index i, color must be red.

### Solution:

Setter’s solution can be found here

Tester’s solution can be found here