Блог пользователя ScienceGuy

Codeforces judge giving wrong output for my code
Автор ScienceGuy, история, 8 лет назад, По-английски

Here is the problem I solved: http://codeforces.me/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?

  • Проголосовать: нравится
  • -25
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

      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";
      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thanks for pointing out the bug.

        → Ответить
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          Declare airName string as global !!.

          airName
          → Ответить
          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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?

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              8 лет назад, # ^ |
              ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

              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.

              → Ответить