Run time Error in Google Kick Start Round G 2020

help
1

Yesterday, I had participated in Google Kick Start and submitted my solution, but it show RE while sample cases are passed successfully.

I have also try my code on "ideone " for sample cases.

Anyone who find some error or bug in my code please make me it noted.

Problem Statement: Kick Start - Google’s Coding Competitions

My solution:

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

int main(){
    int tc,m,n,fs;
    cin>>tc;
    string s;
    string s1="KICK",s2="START";
    for(int i=0;i<tc;i++){
        cin>>s;
        m=0,n=0,fs=0;
        for(int j=0;j<s.size()-3;j++)
        {
            
            if(s1.compare(s.substr(j,4)) == 0){
                //cout<<s.substr(j,4)<<endl;
                m++;  
            }
            if(s2.compare(s.substr(j,5)) == 0 && j<s.size()-4){
                //cout<<s.substr(j,5)<<endl;
                n+=m;
                
            }
            
        }
        
        cout<<"Case #"<<i+1<<": "<<n<<endl;
    }
    
}
2

s.substr is getting out of bound
j<s.size()-4 should come before s2.compare… because for ex cond1&&cond2&&cond3 the order is from cond1 to cond2

3

can someone check my code for problem no. 3, Combination Locks, no idea where it is failing. I have used Binary Search+Prefix Sum, help would be appreciated.Thanks!
Code : 0jY4Ko - Online C++ Compiler & Debugging Tool - Ideone.com

4

@baljot
can you please tell me where i am going wrong?
my sample test cases are passing but i am getting run time error
my code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin >> t;

ll tc = 0;

while (t--)
{
    string s;
    cin >> s;
    vector<string> v1;
    string s1 = "KICK";
    string s2 = "START";
    for (ll i = 0; i < s.size() - 3; i++)
    {
        if (s1.compare(s.substr(i, 4)) == 0)
            v1.push_back("KICK");
        if (i == s.size() - 4)
            break;
        else if (s2.compare(s.substr(i, 5)) == 0)
            v1.push_back("START");
    }
    bool lock = 0;
    ll kick_count = 0;
    ll res = 0;
    for (ll i = 0; i < v1.size(); i++)
    {
    
        if (v1[i] == "KICK" || lock == 1)
        {
            lock = 1;
            if (v1[i] == "KICK")
                kick_count++;
            else if (v1[i] == "START")
                res = res + kick_count;
        }
    }

    tc++;
    cout << "Case #" << tc << ": " << res << endl;
}
return 0;

}

5

What if size of string s is less than equal to 3 ? Your code will give RTE their , Moreover if you want any other help then either format your code or provide link.

6

@dhruv788
thank you soo much for replying
but if the string is less than or equal to 3 it wont enter for loops and hence it will print 0 because i initialized ‘int res=0’ and i believe its a correct ans.
correct me if i am wrong
here is my modified(logic remains the same) and formated code

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    int tc = 0;

    while (t--)
    {
        string s;
        cin >> s;

        vector<string> v1;
        string s1 = "KICK";
        string s2 = "START";

        for (int i = 0; i < s.size() - 3; i++)
        {
            if (s1.compare(s.substr(i, 4)) == 0)
                v1.push_back(s1);
            else
            {
                if ((s2.compare(s.substr(i, 5)) == 0) && (i < s.size() - 4))
                    v1.push_back(s2);
            }
        }

        bool lock = 0;
        int kick_count = 0;
        int res = 0;

        for (int i = 0; i < v1.size(); i++)
        {
            if (v1[i] == s1 || lock == 1)
            {
                lock = 1;
                if (v1[i] == s1)
                    kick_count++;
                else
                    res = res + kick_count;
            }
        }

        tc++;
        cout << "Case #" << tc << ": " << res << endl;
    }
    return 0;
}
7

your s.substr is getting out of range.
and moreover cond1&&cond2 checked sequentially and your i<s.size-4 will never work it will throw error in first cond1 itself if it is out of index or bound.

8

@baljot
thank you soo much for replying
as you said if it is a index out of range error then it has to print some gibberish values once it goes out of the range, which will result in failing sample test cases as well, but my sample test cases are passing.

to check i just ran this code by trying to print all the substrings

for (int i = 0; i < s.size() - 3; i++)
    {
                if (s1.compare(s.substr(i, 4)) == 0)
                {
                    v1.push_back(s1);
                    cout << s.substr(i, 4) << endl;
                }
                else
                {
                    if ((s2.compare(s.substr(i, 5)) == 0) && (i < s.size() - 4))
                    {
                        v1.push_back(s2);
                        cout << s.substr(i, 5) << endl;
                    }
                }
            }

Test Case 1:AKICKSTARTPROBLEMNAMEDKICKSTART
Output :
KICK
START
KICK
START

as you can see it just prints fine and exact words without printing any gibberish values

small explanation about my logic:
A[0] K[1] I[2] C[3] K[4] S[5] T[6] A[7] R[8] T[9] P[10] R[11] O[12] B[13] L[14] E[15] M[16] N[17] A[18] M[19] E[20] D[21] K[22] I[23] C[24] K[25] S[26] T[27] A[28] R[29] T[30]

as you can see in this test case my for loop for (int i = 0; i < s.size() - 3; i++) runs from
0 to < s.size-3
0 to < 31-3
0 to < 28
0 to 27

this for loop will run fine without giving index out of range while checking for substr “KICK”

problem is when we are checking for substr “START”, this will give index out of range error and hence i put this if statement if ((s2.compare(s.substr(i, 5)) == 0) && (i < s.size() - 4))

which will check
if(“START” && i < 31-4)
if(“START” && i < 27)
if(“START” && i = 0 to 26)

so this will not throw any index out of range error as per my understanding
please correct me if i am wrong,

9

Quiz: What will be the output from:

#include <iostream>
  
using namespace std;

int main()
{
    string s = "ab";
    cout << (s.size() - 3) << endl;
}

?

1 Like
11

@ssjgz
string s = “ab”;
cout << (s.size() - 3) << endl;

s.size()-3
2-3
-1
for (int i = 0; i < s.size() - 3; i++)
0<-1 false
THIS IS WHAT I THOUGHT

but indeed ide gave me some long gibberish positive number wowww , i have no idea why but yes now my code got accepted what i did is just
int n=s.size() and used n instead of directly using s.size() in for loops

thank you everybody @baljot @dhruv788 @ssjgz for helping me

1 Like
12

It’s not exactly gibberish: string::size is an unsigned value, typically (on most modern hardware/ software platforms ) a 64-bit unsigned integer with range 0 to 2^{64} which cannot represent negative numbers. Such numbers cause it to “wrap around”.

The value of -1 in a 64-bit integer is thus 2^{64}-1=18446744073709551615.

1 Like
13

@ssjgz
Got it. Today i learnt something new, thank you soo much. :smiley:

1 Like