CHARGES - Editorial

ayushtiwari20 · June 1, 2021, 2:43pm

My code is always giving RUNTIME ERROR, i tried many times…

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

int main()
{
int t;
cin>>t;

while(t--)
{
    int n,k;
    cin>>n>>k;
    
    string s;
    cin>>s;
    
    
    
    
    
    int d = 0;
    
    for(int z=0;z<=s.size()-2;z++)
        {
           if(s[z]==s[z+1])
           d+=2;
           
           else
           d+=1;
        }
        
       int len = 0;
       
       
       
    while(k--)
    {
        int j;
        cin>>j;
        j--;
        
        
        
        if(s[j] =='1')
        s[j] = '0';
        
        else
        s[j] = '1';
        
        
        if(j>0)  //left
        {
        if(s[j-1]==s[j])
        len++;
        
        else 
        len--;
        }
        
        
        if(j<s.size()-1)  //right
        {
        if(s[j+1]==s[j])
        len++;
        
        else
        len--;
        }
        
        d = d + len;
        cout<< d <<"\n";
        
        
        len = 0;
        
    }
    
    
    
}
return 0;

}

anon38811231 · June 1, 2021, 3:10pm

What is wrong with this solution I tried many test cases!

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

int main()
{
    // your code goes here
    int t = 1;
    cin >> t;
    while (t--)
    {
        ll n, k;
        cin >> n >> k;
        string s;
        cin >> s;
        int a[k];
        for (int i = 0; i < k; i++)
        {
            cin >> a[i];
        }
        ll intans = 0;
        for (int i = 0; i < n - 1; i++)
        {
            if ((s[i] == '0' && s[i + 1] == '0') || (s[i] == '1' && s[i + 1] == '1'))
            {
                intans += 2;
            }
            else
            {
                intans += 1;
            }
        }
        for (int i = 0; i < k; i++)
        {
            ll ans = 0;

            if(a[i]-1 == 0)
            {
                if(s[a[i]] == s[a[i] - 1]) 
                {
                    ans = intans - 1;
                }
                else
                {
                    ans = intans + 1;
                }
                cout << ans << "\n";
                intans = ans;
                if(s[a[i]-1] == '0') s[a[i]-1] = '1';
                else s[a[i]-1] = '0';
                continue;
            }
            if(a[i]-1 == n-1)
            {
                if(s[a[i]-2] == s[a[i] - 1]) 
                {
                    ans = intans - 1;
                }
                else
                {
                    ans = intans + 1;
                }
                cout << ans << "\n";
                intans = ans;
                if(s[a[i]-1] == '0') s[a[i]-1] = '1';
                else s[a[i]-1] = '0';
                continue;
            }

            if ((s[a[i] - 2] == s[a[i] - 1]) && (s[a[i]] == s[a[i] - 1]))
            {
                ans = intans - 2;
            }
            else if ((s[a[i] - 2] != s[a[i] - 1]) && (s[a[i]] == s[a[i] - 1]))
            {
                ans = intans;
            }
            else if ((s[a[i] - 2] == s[a[i] - 1]) && (s[a[i]] != s[a[i] - 1]))
            {
                ans = intans;
            }
            else
            {
                ans = intans + 2;
            }
            cout << ans << "\n";
            intans = ans;
            if(s[a[i]-1] == '0') s[a[i]-1] = '1';
            else s[a[i]-1] = '0';
        }
    }
    return 0;
}

darshancool25 · June 1, 2021, 3:12pm

Type cast s.size() to int OR just define a variable int sz = s.size() and use sz everywhere. You were getting runtime error as generally .size() returns an unsigned int value

ayushtiwari20 · June 1, 2021, 3:51pm

@darshancool25 Thankyou so so much it finally worked…I am happy because after a lot of attempts i got it and also I watched your video before the code part so that I can attempt from myself.
It feels really nice if we did from ourselves.

anoushka3110 · June 1, 2021, 4:00pm

Can someone explain why there is a Time Limit Exceeded error here? View Solution
@daanish_adm @cherry0697 @monogon

saiyan_god · June 1, 2021, 5:19pm

@henrychen222
Thanks a lot sir . I have one doubt .
if string in c++ is immutable objects the how can
s[index] ^= 1;
this line is valid ?

ssjgz · June 1, 2021, 5:28pm

One thing that’s bad for performance: IsSame and Score both take strings by value instead of by reference, causing the passed string to be copied each time they are called.

tanjiro23 · June 1, 2021, 6:54pm

Yaa, I realized later that I didn’t consider the edge case of string of 1 unit length. Thanks for pointing it out.

sabertooth_69 · June 1, 2021, 7:02pm

although this code passes all the test cases still gives WA please help…
/*
first of all as stated in the question calculate the distance between the first and last
particle. denote the change in the given position by the variable “change”
so to check for the change in the string we just haveto check in the vicinity that is left and the right
THIS PROBLEM IS MEDIUM FOR ME
so after making a change if the particle in vicinity is opposite then len–
and if they are of the same chare then len++

/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ll t;
cin>>t;
while(t–)
{
ll n,k;
cin>>n>>k;
string s;
cin>>s;//since we only need a single string therefore not creating a loop
ll length=n-1;//distance between first and last
//calculating the initial length
for(ll i=1;i<n;i++)
{
length+=s[i]==s[i-1];//**
}
while(k–)//executing till changes become zero
{
ll queries;
cin>>queries;
queries–;
if(s[queries]==‘1’)
{
s[queries]=‘0’;
}
else
{
s[queries]=‘1’;
}
if(queries<n-1) //charge is flipped and now checking vicinity
{
if(s[queries]==s[queries+1])
{
length++;
}
else
{
length–;
}
}
// now checking if the previous configuration was same or different
if(queries>0)
{
if(s[queries]==s[queries-1])
{
length++;
}
else
{
length–;
}
}
cout<<length<<endl;
//woah!! this was a nasty one…xd

}
return 0;
    }

}

ssjgz · June 1, 2021, 7:07pm

Please either format your code or (better!) link to your submission - the forum software has mangled it and it won’t compile!

Edit:

Deciphered it. Obvious one:

This is something people should try whenever they have a WA.

Edit2:

Second one of these today, interestingly Running testcases with array - #2 by ssjgz

ssjgz · June 1, 2021, 8:18pm

strings in C++ are not immutable.

ssjgz · June 1, 2021, 8:19pm

Your solution fails for the following test input:

@sarcastic_yogi Yours too

@aadarshsinha Yours has an out-of-bounds access with this testcase.

henrychen222 · June 1, 2021, 8:26pm

s[index] ^= 1, means index char switch. xor 1 change ‘0’ → ‘1’, ‘1’ → ‘0’ easily, I think c++ string chars can be changed.

example s= ‘abc’, s[1] = ‘d’. the s = ‘adc’

saiyan_god · June 2, 2021, 6:45am

@ssjgz
Understood sir.

saiyan_god · June 2, 2021, 6:46am

@henrychen222
thanks sir , now i understand.

makasam · June 2, 2021, 7:23am

#include
using namespace std;

int main() {
int x,a,b,c,d,y,z;
string s;
cin >> x;
for(int i=0;i<x;i++)
{
cin>>a>>b;
char arr[a-1];
char k;
int jar[a-1];
cin>>s;
for(int j=0;j<a;j++){
arr[j]=s[j];
k=arr[j];
jar[j] = (int)k;
}
for(int lo=0;lo<b;lo++){
cin>>d;
if(jar[d-1]==0)
{
jar[d-1]=1;
}
else
{
jar[d-1]=0;
}
int dis=0;
for(int ll=1;ll<a;ll++){
if(jar[ll]-jar[ll-1]==0){
dis=dis+1;
}
else{
dis=dis+2;
}
}
cout<<dis<<endl;
}
}

return 0;

}
@darshancool25 can you tell me what is the problem if I code it this way
and why the submission has errors
It will be very kind of you.Thank you.

ssjgz · June 2, 2021, 7:43am

This has out-of-bounds accesses with the sample test input:

[simon@simon-laptop][08:42:22]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling makasam-CHARGES.cpp
+ g++ -std=c++14 makasam-CHARGES.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv
makasam-CHARGES.cpp: In function ‘int main()’:
makasam-CHARGES.cpp:5:15: warning: unused variable ‘c’ [-Wunused-variable]
     int x,a,b,c,d,y,z;
               ^
makasam-CHARGES.cpp:5:19: warning: unused variable ‘y’ [-Wunused-variable]
     int x,a,b,c,d,y,z;
                   ^
makasam-CHARGES.cpp:5:21: warning: unused variable ‘z’ [-Wunused-variable]
     int x,a,b,c,d,y,z;
                     ^
+ set +x
Successful
[simon@simon-laptop][08:42:28]
[~/devel/hackerrank/otherpeoples]>echo "1
3 3
010
2 1 3" | ./a.out
makasam-CHARGES.cpp:16:18: runtime error: index 2 out of bounds for type 'char [*]'
makasam-CHARGES.cpp:17:20: runtime error: index 2 out of bounds for type 'char [*]'
makasam-CHARGES.cpp:18:18: runtime error: index 2 out of bounds for type 'int [*]'
makasam-CHARGES.cpp:32:26: runtime error: index 2 out of bounds for type 'int [*]'
4
3
makasam-CHARGES.cpp:22:23: runtime error: index 2 out of bounds for type 'int [*]'
makasam-CHARGES.cpp:28:24: runtime error: index 2 out of bounds for type 'int [*]'
2

darshancool25 · June 2, 2021, 7:54am

Everything ssjgz has written is true. I would just like to add few points :

If you ever need to convert a single character (my_char) to its corresponding int value, heres an example : int int_val = my_char - '0';
Note that type casting int_val = (int)(my_char) wont work !!
In your code after each of the k changes, you are recalculating the answer from scratch again (which is quite unnecessary and slow). I suggest have a look at the video editorial for understanding a better approach.

anon38811231 · June 2, 2021, 8:48am

Woah thanks this corner case just didn’t come to my mind , how do you find such corner cases?
Edit: I changed the case when n==1 to output it 0 and continue then too it is giving WA

ssjgz · June 2, 2021, 8:57am

The usual way - simple brute-force solution plus randomised testcase generator

Please link to your most recent WA solution.