You are not logged in. Please login at www.codechef.com to post your questions!

×

STRBIT - Editorial

PROBLEM LINK:

Practice
Contest

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.

  1. Order of the updates doesn't matter.
  2. Starting index of any 2 updates will be different, as 2 updates at same starting position will cancel each other.
  3. 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

This question is marked "community wiki".

asked 21 Mar '15, 02:10

amitpandeykgp's gravatar image

4★amitpandeykgp
25911522
accept rate: 0%

edited 11 Feb '16, 18:39

admin's gravatar image

0★admin ♦♦
19.7k350498541


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 $|x-i|\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.

link

answered 23 Mar '15, 00:10

waterfalls's gravatar image

7★waterfalls
1712
accept rate: 66%

I solved it without using BIT or segment tree.
We can solve this problem using this O(N) algorithm:
1. Initialise st[] = -1, st[i] denotes total number of swaps when i index was part of a range 1st time.
2. Iterate over the char array, s[]:
a. If st[i]=-1 then there is no swaps till the current index.
b. Else calculate the number of swaps on current index as (ans-st[i]), here ans=number of swaps till index i.
c. Calculate value of s[i] after catering the swaps.
d. If value of s[i] after catering swaps is 'R' then assign the new elements in range with the current value of ans. Increase the value of ans if s[i]='R'. Code: memset(st,-1,sizeof(st)); for(i=0; i < n ; i++) { if(st[i]!=-1) { j=ans-st[i]; if(j&1 && s[i]=='R') x='G'; else if(j&1 && s[i]=='G') x='R'; else x=s[i]; } else x=s[i]; if(x=='R') { j=min(n-1,i+k-1); while(st[j]==-1 && j>=i) { st[j]=ans; j--; } ans++; } } pi(ans);

link

answered 23 Mar '15, 00:24

atulsehgal's gravatar image

3★atulsehgal
452612
accept rate: 8%

edited 23 Mar '15, 00:30

My solution is a bit simpler:

int n, k;
char s[100010];
int flip_bound[100010];

int main() {
  int t;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    cin >> s;
    int ans = 0;
    CLR(flip_bound, 0);
    int cur_flip = 0;
    REP(i, n) {
      if ((s[i] == 'R') == (cur_flip % 2 == 0)) {
        ans++;
        cur_flip++;
        if (i + k <= n) {
          flip_bound[i + k - 1] = 1;
        }
      }
      if (flip_bound[i]) {
        cur_flip--;
      }
    }
    cout << ans << endl;
  }
  return 0;
}
link

answered 23 Mar '15, 00:41

lxfind's gravatar image

4★lxfind
301147
accept rate: 14%

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 n-1 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 n-1 :

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+k-1 to be flipped

end if

end for

print answer

link

answered 23 Mar '15, 17:57

rajat1603's gravatar image

7★rajat1603
1.0k113
accept rate: 4%

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+k-1).

(24 Dec '15, 04:27) shubham992★

@rajat1603, This problem can be solved by looping from 0 to n-1 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...

link

answered 24 Mar '15, 16:40

khooni_khopri's gravatar image

2★khooni_khopri
127314
accept rate: 0%

@rajat1603 can you please explain the idea behind your algo??

EDIT: Got it. Awesome solution

link

answered 28 Mar '15, 22:46

esemzv's gravatar image

3★esemzv
212
accept rate: 0%

edited 28 Mar '15, 23:15

@amitpandeykgp I am not getting the Sub-problem 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}

     prefix_sum[]= {4,9,16,14,13,14}  //i don't see how prefix array contains correct no. at each index
            sum[]= {4,13,29,43,56,70}

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 2-3 times and still not getting. Please help.

link

answered 30 Mar '15, 01:48

moulin's gravatar image

3★moulin
11
accept rate: 0%

edited 30 Mar '15, 01:50

can some one explain last comment please how we get query result correctly

link

answered 28 May '15, 00:03

raj__0jaiswal's gravatar image

3★raj__0jaiswal
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,741
×1,755
×371
×124
×1

question asked: 21 Mar '15, 02:10

question was seen: 5,087 times

last updated: 11 Feb '16, 18:39