Kneee's blog

Can someone explain why this is happening in Problem A Codeforces Round 855 (Div. 3)
By Kneee, history, 20 months ago, In English

Hi everyone,

Can anyone explain why this code gets Wrong Answer on Test Case 2, Although the same code just deletes the map (didn't use it), it gets Accepted

If you submitted the same code that got wrong with c++20, it will give AC but c++17 gives the wrong answer

Code with map c++17: 195842451 Wrong Answer on Test Case 2

Code with map c++20: 195842466 Accepted

Code without map c++17: 195842512 Accepted

Thanks

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Kneee (previous revision, new revision, compare).

→ Reply
»
20 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Probably due to undefined behavior which is present in your code. You should replace while(s[i] == arr[cur]) with while(i<s.length() && s[i] == arr[cur]). Also, your cur variable can go past 3, so you are accessing index 4 of {'m', 'e', 'o', 'w'} which is undefined. Fixing these undefined behavior lets the code pass in C++ 17. Why it passes when you delete the map? We can't ever know for sure, undefined behavior doesn't guarantee the code will be wrong, it just means it might not work as expected sometimes.

Fixed code with map included that passes in C++ 17: 195846468

→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it -8 Vote: I do not like it

    Thanks for your effort! ❤️

    → Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    can you help me with my code too for the same question. 195883758 this code gives wrong ans on 2nd test, it returns a YES when it should return a NO. thanks

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

      Your second if statement seemed dubious to me. The || s[n-1] == 'w' isn't evaluated in the order you think it is. I recommend using parentheses when using && and || in the same if statement. Fixed solution: 195885580

      → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Array out of bounds:

Line 45: Char 18: runtime error: index 4 out of bounds for type 'char [4]' (solution.cpp) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:50:18

Try changing to use this:

    //char arr[]={'m','e','o','w'};
    vector<char> arr = {'m','e','o','w'};

or experiment with:

    //char arr[]={'m','e','o','w'};
    char arr[]={'m','e','o','w',' '};
→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your effort! ❤️

    What makes me confused when I deleted the map it gets accepted, so weird

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

    char arr[]={'m','e','o','w',' '};

    How can this help? Error is due to the fact that index is becoming >= length of array, independent of what is length

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I assume the original logic is only off-by-one and that the last dummy character read does not affect the logic. Anyways, I just wanted OP to experiment with the code change, not to use the code directly.

      → Reply
»
20 months ago, # |
  Vote: I like it +3 Vote: I do not like it

AC with GNU C++17 195871587

You need to add
→ Reply