CHARGES - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester: Riley Borgard
Editorialist: Aman Dwivedi

DIFFICULTY

Cakewalk

PREREQUISITES

Observation

PROBLEM

Given a string S consisting of characters '0' and '1' with the first character fixed at position 0. Given K queries of the form Q_1, Q_2,…, Q_K where Q_i denotes reverse the parity of Q_ith character and print the location of Nth particle.
Assume that the same adjacent characters are 2 units apart and different adjacent characters are 1 unit apart.

QUICK EXPLANATION

Case 1: N=1. Location of N^{th} characters remains same for all quries.

Case 2: N>1

  • Reversing the parity of 1^{st} and N^{th} character, either increment the location of N^{th} character by 1 or decrement it by 1.
  • Reversing the parity of character at position P where 1< P <N.
    • If the adjacent characters have different parity ( i.e S[P-1]!=S[P+1]), the location of the N^{th} character doesn’t change.
    • If after changing the parity of S[P], if the adjacent character have same parity ( i.e S[P-1]=S[P+1]).
      • If S[P]=S[P-1], means if S[P] has the same parity as its adjacent characters then the location of the N^{th} character will increment by 2.
      • If S[P]!=S[P-1], means if S[P] has different parity compared to it’s adjacent characters then the location of the N^{th} character will decrement by 2.

But why this is true?

EXPLANATION

Firstly we need to calculate the location of N^{th} character before performing the queries. Let L store the location of N^{th} character in the string. If the next character is the same as the previous add 2 to L else add 1 to L.

Case 1: Proof - When the string length equals 1, changing the parity doesn’t change the N^{th} location as they are no other characters in the string to cause any change.

Case 2: Proof - N>1

  • Reversing parity of character at position 1^{st} and N^{th}. Lets suppose we have S="10" and Q_1=1,Q_2=1. Initially, L=1. After performing Q_1 string S="00", and now we can see that the next character is same as the previous character ( i.e S[1]=S[2]) and that makes both the characters 2 units apart. Therefore, L is increment by 1 ( i.e L+1=2). Now after performing Q_2 string S=“01”, and now the character S[0] and S[1] are 1 unit apart. Therefore, L is decremented by 1 ( i.e L-1=1).
  • Reversing the parity of character at position P where 1< P < N.
    • Let’s take an example S="110" and Q_1=2. Initially L=3. Performing query Q_1 changes string S=“100”, now we can see that previously S[1]==S[2] and now S[2]==S[3], meaning before the character at position S[2] was 2 units apart from S[1] and $1$unit apart from S[3] and now after the query is performed S[2] is 2 units apart from S[3] and 1 unit apart from S[1]. Hence, the location of N^{th} doesn’t change. So we can say that when the adjacent characters have different parity the answer remains the same.
    • Let’s take an example S="010" and $Q1=2. Initially L=3. Performng query Q_1 changes string S="000". Intitally S[2] was 1 unit apart from both S[1] and S[3]. Now after the query is performed it is 2 units apart from both S[1] and S[3]. Hence, L =L+2. Now, after the query if S[P-1]==S[P]==S[P+1], then it will increment the L by 2. Similarly, after the query if S[P-1]==S[P+1] and S[P] has different parity then it will decrement the L by 2

TIME COMPLEXITY

The time complexity is O(N) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
 
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
 
using namespace std;
 
const int maxtq = 2e5, maxt = 5, maxn = 1e5, maxq = 1e5;
 
int main()
{   
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    int tq = 0;
    while(t--){
        int n, q; cin >> n >> q; tq += q;
        string s; cin >> s;
        int len = 0; assert(s[0] == '0' || s[0] == '1');
        for(int i = 1; i < n; i++){
            assert(s[i] == '0' || s[i] == '1');
            if(s[i] == s[i - 1])len += 2;
            else len++;
        }       
        int x;
        for(int i = 0; i < q; i++){
            cin >> x;
            x--;
            s[x] = s[x] == '0' ? '1' : '0';
            if(x > 0){
                if(s[x - 1] == s[x]){
                    len++;
                }else{
                    len--;
                }
            }
            if(x < n - 1){
                if(s[x + 1] == s[x]){
                    len++;
                }else{
                    len--;
                }   
            }
            cout << len << endl;
        }
    }
    assert(tq <= maxtq);
} 
Tester's Solution
#include <bits/stdc++.h>
 
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
 
void solve() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    int cnt[2] = {0, 0};
    rep(i, 1, n) {
        cnt[s[i] == s[i - 1]]++;
    }
    rep(q, 0, k) {
        int i;
        cin >> i;
        i--;
        if(i > 0) cnt[s[i] == s[i - 1]]--, cnt[s[i] != s[i - 1]]++;
        if(i < n - 1) cnt[s[i] == s[i + 1]]--, cnt[s[i] != s[i + 1]]++;
        s[i] ^= '0' ^ '1';
        cout << 2 * cnt[1] + cnt[0] << '\n';
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int te;
    cin >> te;
    while(te--) solve();
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
 
#define int long long int
 
void solve()
{
  int n, q;
  cin >> n >> q;
  string s;
  cin >> s;
  int location = 0;
  for (int i = 0; i < n - 1; i++)
  {
    if (s[i] == s[i + 1])
    {
      location += 2;
    }
    else {
      location++;
    }
  }
 
  while (q--)
  {
    int pos;
    cin >> pos;
    pos--;
    s[pos] = (s[pos] == '0' ? '1' : '0');
 
    if (pos == 0)
    {
      if (pos + 1 < n)
      {
        if (s[pos] == s[pos + 1])
          location++;
        else
          location--;
      }
 
    }
    else if (pos == n - 1)
    {
      if (pos - 1 >= 0)
      {
        if (s[pos] == s[pos - 1])
          location++;
        else {
          location--;
        }
      }
 
    }
    else {
      if (s[pos - 1] == s[pos + 1])
      {
        if (s[pos] == s[pos - 1])
          location += 2;
        else
          location -= 2;
 
      }
 
    }
    cout << location << endl;
 
  }
}
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  int t;
  cin >> t;
 
  while (t--)
    solve();
 
  return 0;
}
4 Likes

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
  int n,k;
  cin>>n>>k;
  string s;
  cin>>s;
  vector<int> arr(k);
  for(int i=0;i<k;i++){
      cin>>arr[i];
  }
  long long dis = 0;
  for(int i=0;i<n-1;i++){
    if(s[i]==s[i+1])    dis+=2;
    else if(s[i]!=s[i+1]) dis+=1;
  }
  if(n==1){
      for(int i=0;i<k;i++){
          cout<<"0"<<endl;
      }
      return 0;
  }
  for(int i=0;i<k;i++){
      int kk =arr[i]-1;
      if(kk>=0 && kk<=n-1){
      if(s[kk]=='0')
      s[kk] = '1';
      else
      s[kk] = '0';
    //   cout<<s<<endl;
      if(kk==0){
          if(s[kk]==s[kk+1])  dis+=1;
          else dis-=1;
          cout<<dis<<endl;
          continue;
      }
      if(kk==n-1){
          if(s[kk]==s[kk-1])  dis+=1;
          else dis-=1;
          cout<<dis<<endl;
          continue;
      }
      if(s[kk]==s[kk-1]){
          dis+=1;
      }else{
          dis-=1;
      }
      if(s[kk]==s[kk+1]){
          dis+=1;
      }else{
          dis-=1;
      }
      cout<<dis<<"\n";
      }
  }
  	
  }
  return 0;
}

Can somebody help me with this. What can be the issue with my code. I have already tried with lots of test cases .The logic is exactly same as this editorial.
Thanks.

Solution: 47237011 | CodeChef

2 Likes

#include <bits/stdc++.h>
using namespace std;
long long int check(vector str, long long int n)
{
long long int res;
res=0;
for(long long int i=1;i<n;i++)
{
if(((str[i]==‘1’)&&(str[i-1]==‘1’))||((str[i]==‘0’)&&(str[i-1]==‘0’)))
{
res=res+2;
}
else
{
res++;
}
}
return res;
}
int main() {
// your code goes here
long long int t,n,k,res,a,v[100001];
char before,after;
vector str1;
string str;

cin>>t;
while(t--)
{
    cin>>n;
    cin>>k;
    cin>>str;
   
    res=0;
     for(long long int i=0;i<k;i++)
    {
        v[i]=0;
    }
    for(long long int i=0;i<k;i++)
    {
        cin>>a;
        a=a-1;
        v[i]=a;
    }
    str1.clear();
     for(int i=0;i<n;i++)
    {
    	str1.push_back(str[i]);
	}
	res=check(str1,n);
    for(long long int i=0;i<k;i++)
    {
    	
        if((str1[v[i]])=='0')
        {
      
        if(v[i]==0)
        {
        	if(str1[v[i]+1]=='0')
			{
				res=res-1;
				
			}
			else
			{
				res=res+1;
			}
		}
		else if(v[i]==(n-1))
		{
		if(str1[v[i]-1]=='0')
			{
				res=res-1;
		
			}
			else
			{
			
			
		
				res=res+1;
		
			}
		}
		else
		{
			
		
		before=str1[v[i]-1];
		after=str1[v[i]+1];
		if((before=='0')&&(after=='0'))
		{
			res=res-2;
		 }
		else if((before=='1')&&(after=='1'))	
		{
			res=res+2;
		 }
		 	           
			           
        }
         str1[v[i]]='1';
    }
        else
        {
        	if(v[i]==0)
        	{
        			if(str1[v[i]+1]=='1')
			{
				res=res-1;
			}
			else
			{
				res=res+1;
			}
			}
			else if(v[i]==(n-1))
        	{
        		if(str1[v[i]-1]=='1')
			{
				res=res-1;
			}
			else
			{
				res=res+1;
			}
			}
        	else
        	{
        		before=str1[v[i]-1];
		after=str1[v[i]+1];
		if((before=='1')&&(after=='1'))
		{
			res=res-2;
		 }
		else if((before=='0')&&(after=='0'))	
		{
			res=res+2;
		 }
			}
        	
        	
            str1[v[i]]='0';
        }
       
        
       cout<<res<<endl; 
    }
}
return 0;

}

I have done with the same logic,can anybody help me to find the error

Solution Link - Click Here

Can anyone point out the test case, where it’s throwing a WA.I have personally tried many test cases, but it’s still throwing a WA.

Thanks in advance!

Can someone explain what I’m doing wrong?
I’m certain my solution is correct.

Solution: 47275361 | CodeChef

Solution Link: https://www.codechef.com/viewsolution/47257308
Can someone explain what’s wrong with my code. I have used the same logic as editorial and have also tried many test cases. But its still giving WA.

My code is working correctly for the given test cases but it is showing WA. what’s missing in it.

#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
string s;
cin>>s;
int q[k];
for(int i=0;i<k;i++)
cin>>q[i];
long long int sm=0;
for(int j=0;j<n-1;j++){
if(s[j]==s[j+1])
sm+=2;
else
sm+=1;
}
for(int i=0;i<k;i++){
//long long int sm=0;

        if(s[q[i]-1]=='1')
        s[q[i]-1]='0';
        else
        s[q[i]-1]='1';
        if(q[i]-1==0){
            if(s[q[i]]==s[q[i]-1])
            sm+=1;
            else
            sm-=1;
        }
        else if(q[i]-1==n-1){
            if(s[q[i]-1]==s[q[i]-2])
            sm+=1;
            else
            sm-=1;
        }
        else if(q[i]-1>0&&q[i]-1<n-1){
            if(s[q[i]-2]==s[q[i]]){
                if(s[q[i]]==s[q[i]-1])
                sm+=2;
                else
                sm-=2;
            }
        }
        cout<<sm<<endl;
    }
    
}
return 0;

}

Link to my submission: Solution: 47258014 | CodeChef
Can someone please tell me what did I miss out? It gives correct result for sample test cases, and my logic is also nearly same , but got WA.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main() {
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);

ll t;cin>>t;while(t--)    
{

ll n,k,sum=0;cin>>n>>k;
string s;cin>>s;
for(ll i=0 ; i<n-1 ; i++)  sum+=(s[i]==s[i+1]) ? 2 : 1; 


for(ll i=0;i<k;i++)
{
    ll q ; cin>>q;
    
    if(q==1)
    {
    s[q-1]= (s[q-1]=='1') ? '0' : '1' ;
    sum+=( s[q-1]==s[q] ) ? 1 : -1 ; 
    }
    
    else if(q==n)
    {
    s[q-1]=(s[q-1]=='1') ? '0' : '1' ;
    sum+=( s[q-1]==s[q-2] ) ?  1 : -1 ; 
    }
    
    else
    {
    ll s1=0,s2=0;
    for(int j=q-2 ; j<q ; j++) s1+=(s[j]==s[j+1]) ? 2 : 1;
    sum-=s1;
    s[q-1]=(s[q-1]=='1') ? '0' : '1' ;
    for(int j=q-2 ; j<q ; j++) s2+=(s[j]==s[j+1]) ? 2 : 1;
    sum+=s2;
    }
    
    cout<<sum<<endl;
}
}
return 0;

}

Didn’t get why my code also failing !! can anyone plzz find out why !!

Where have you taken the input?

 int kk =arr[i]-1;

This line of your code is wrong. You haven’t taken the input.

https://www.codechef.com/viewsolution/47206713
Can someone point what am I doing incorrect in this solution. I tried many test cases, but still cant find the mistake
Thank you.

Can anyone help i am getting NZEC… Don’t know why
https://www.codechef.com/viewsolution/47278275
Thanks in advance …Please do help me finding the problem in the code.

https://www.codechef.com/viewsolution/47278102

@darshancool25 Hey man! I used a similar logic, but instead of comparing after replacing, I compared the initial stages and incremented/decremented the distance accordingly. Can you check and point out the possible error(s)? Also, thank you for the video editorial too. :slight_smile:

This part of your code is wrong. Work out both the cases separately

In your code there is a big flaw
if(s[Q]==‘0’) s[Q] = ‘1’;
if(s[Q]==‘1’) s[Q] = ‘0’;
These two lines firstly change the character in the upper line and then again lower line will revert back to previous character
basically no change !!

3 Likes

I have taken input of array on line 16

I think your solution fails for N = 1 .The way you are handling different scenarios, its for sure changing the answer each time. But if you think the answer should always be 0 for N = 1 :slight_smile:

Can someone give me the wrong test cases for my given submission?

https://www.codechef.com/viewsolution/47230294

What’s wrong with my code?
It works for test cases and other corner cases also
@darshancool25 https://www.codechef.com/viewsolution/47276454

You handled in a very complex way, hard to debug !! :grimacing: