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

×

LONG MAY 17 CHEFROUT - Different results for same code?

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

asked 20 Jun '17, 00:01

saip009's gravatar image

2★saip009
111
accept rate: 0%

edited 20 Jun '17, 00:19


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";
    }
}
link

answered 20 Jun '17, 00:11

vijju123's gravatar image

5★vijju123 ♦
13.6k11036
accept rate: 19%

edited 20 Jun '17, 00:14

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

(20 Jun '17, 00:14) saip0092★

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

(20 Jun '17, 00:18) vijju123 ♦5★

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.

link

answered 20 Jun '17, 09:07

hikarico's gravatar image

5★hikarico
1.8k515
accept rate: 28%

edited 20 Jun '17, 09:10

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:

×401
×220
×176
×12
×5
×4

question asked: 20 Jun '17, 00:01

question was seen: 276 times

last updated: 20 Jun '17, 09:10