LONG MAY 17 CHEFROUT - Different results for same code?

general
, , , , ,
1

So I was trying this simple problem CHEFROUT. For the two identical programs, code1 (score 0.0) and code2 (score 0.7) I’m getting different results. The only possibility I can think of is different test sets are there but I’m not sure if CodeChef does that.

Also if possible help identify the problem. I know of other solutions though.

TIA

1 Like
2

This means that your code is getting undefined behaviour. If you try accessing an array out of index, then either you will get a RE:SIGSEV error, or your program will go on “undefined behaviour” and then whatever it prints will be random, based on input and print statements.

The error fixed itself when i increased limit of char array b, giving your code a complete AC.

The reason “char b[3]” led to WA because you left no space for it to store “\0” character, which tells the computer that “this is end of string”

Its always suggested to have array limits slightly higher than needed.

Your AC code-

#include<iostream>
#include<cstring>
 
using namespace std;
 
int main(){
    int t,n,i,j=0;
    char a[100005],x;
    char b[300];
    cin>>t;
    while(t--){
        strcpy(b,"CES");
        cin>>a;
        n = strlen(a);
        i=0;
        j=0;
        while(i<n && j<3){
            if(a[i]==b[j]){
                i++;
            }
            else {
                j++;
            }
        }
        if(i==n) cout<<"yes\n";
        else    cout<<"no\n";
    }
}
3

When you run strcpy(b,"CES"), what happens internally is:

b[0] = 'C';
b[1] = 'E';
b[2] = 'S';
b[3] = '\0'; // end of string sentinel

But you only allocated for only three characters for char b[3]. The last statement will result into array out of bounds. Unlike java, C++ allows such things and won’t specifically throw any errors. However, a forbidden access like that will cause undefined behavior. Meaning, sometimes it will fail on you, sometimes it will not. Sometimes it will overwrite another memory address, or sometimes it will write on empty space. It’s out of pure luck that your second code was able to run without causing errors. You can read all about it here and here.

And so, a lesson to remember is to always allocate one more character for end-of-string sentinel if you’re using character arrays. We don’t want such undefined behavior to happen during contests.

4

Thanks. This solves one problem. But your answer does not answer the primary query, same code and different results.

5

Where more do you need clarification? If it runs on undefined behavior, then its pure luck.