ScienceGuy's blog

Codeforces judge giving wrong output for my code
By ScienceGuy, history, 7 years ago, In English

Here is the problem I solved: http://codeforces.com/problemset/problem/765/A). I submitted a code (My code: http://pastebin.com/8FckK356 ). It gives WA on test 11 (test 11: http://pastebin.com/g7MC6YJf ). But in my computer I paste the test and it outputs the correct result. The logic in my code is correct. So why does the CodeForces judge output a different result for my code?

  • Vote: I like it
  • -25
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

airName length is 3, but you read airName[j] for j=5..7

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    5, 6, 7 are three. I chose a different compiler and it worked. I want to know Why GNU G++11 5.1.0 did not work, but worked on GNU G++14 6.2.0

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is an UB and you are stupid. Almost always if solution is ok on local machine and fails in judge the problem is out-of-bound index.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Submit your code with G++ 6.2 c++14 compiler )))))). 24671484

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Thanks for the response. Could you please explain why it works on G++ 6.2 c++14 compiler, but not on GNU G++11 5.1.0?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      My coatch told as: Very bad bug is a bug, where works correct.

      I don't know why this wrong solution passes all tests with G++ 6.2 C++14.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      I found, G++ 6.2 used continues content for string class,

      and do not allocate memory for less than 15 symbols (may less 23, I cannot remember).

      so, access to non-exist element is safe, if index is tiny.

         for(int i= 0; i < n; ++i)
   {
        bool w = true;
        for(int j = 5; j < 8; ++j) 
                           ///  airName[5] , airName[6], airName[7] == 0, on G++6.2 but
                           ///  airName[5], airName[6], airName[7] == garbage value.
                            //  this contion never satisfied only on G++6.2.
           if (nextS[j] == airName[j]){ // this condition never satisfied, so 
                 w = false; break;
           }

       // so, there w - always true
       if (w)count++;
   }

     /// there count = n, and as expected right solution, solution passes.
 //   

   if (count % 2 == 0)cout << "home\n"; else cout << "contest\n";
      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for pointing out the bug.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If you want AC this code for any compiler, it's very simple:

          Declare airName string as global !!.

          airName
          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Why does it work? We want to compare nextS[5..7] to airName[0..2], so why would airName[5..7]==airName[0..2] now?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              ← Rev. 2   Vote: I like it +3 Vote: I do not like it

              Let me explain.

              The algorithm which count number of

              nexts[5..7] == airName[0..2]

              and if this count is even answer is 'home' otherwise 'contest' is WRONG! 

                  bool w = true;
    for(int j= 5; j < 8; ++j) if ( nextS[j] == airName[j]){ w = false; break;}
 
    // this comparasion is wrong, even when fixes: nextS[j] == airName[j-5], for example:
    // airName = 'SPO', and nextS = 'SPO->OPS' ==>  w = false, because nextS[6] == airName[1]
    // airName = 'SPO', and nextS = 'OPS->SPO' ==>  w = false, also.
   
    // need check  :  
    //  w = (nextS[5] == airName[0]) && (nextS[6]==airName[1])&&(nextS[7]==airName[2]);
    //  but , now algorithm is WRONG )).

              But this WRONG algorithm implemented also WRONG way, and resulting implementation is CORRECT !!!

              CORRECT algorithm : if n is even number answer='home' otherwise 'contest'.

              Now, if airName is global, all its content fills with zero by default.

              Note that, GCC c++11 new ABI, and VS++ compilers wouldn't allocate memory from heap for string, if size is small ( ~ 15-23 ), instead of uses its stack memory.

              → Reply