vishudon's blog

Map Solution is working fine, but unordered_map solution is giving wrong answer. Please help me.
By vishudon, history, 3 years ago, In English

Hi there,

I hope you all are doing well. I recently solved this problem: Problem Link

But while solving this problem, I faced a weird issue. Although, I am able to solve this problem using Map STL in C++, but same solution with unordered_map is not getting accepted. Not understanding why is this happening.

I thought to notice the time difference in execution after switching from map to unordered_map. But faced weird WA verdict. My unordered_map solution is giving WA verdict on test case 2 (on test input 3rd), But it is working fine on both my C++ editor and on online editors too on the same test case. This is STRANGE for me.

Solution 1 (using map STL): https://codeforces.net/contest/1598/submission/155784539 (Accepted)

Solution 2 (using unordered_map STL): https://codeforces.net/contest/1598/submission/155784670 (WA verdict)

Note: Solution2 is completely same as Solution1 except I changed map STL to unordered_map STL.

Now, I am not able to understand what is the issue with my code. Why am I getting WA verdict on test case 2 (on test input 3rd)?

Kindly help me in resolving and understanding this issue. Any help will be appreciated. Thanks in advance for your time and efforts. It means a lot to me.

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

Comments Comments (7)
| Write comment?
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Be aware that map is sorted container whereas unordered_map is unsorted. You can find more information about these containers f2f here.

Your unordered_map solution is getting accepted on other editors because of some settings that arent presented here on CF (or vice versa). I honestly cant tell the exact reason, but thats the case 100%. Tho if anybody could provide for my personal knowledge a specific reason why this is happening — I’ll be grateful.

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

Changing language to C++20 makes your solutions pass tests up to 106th (https://codeforces.net/contest/1598/submission/155795183). I thought that the issue was the precision loss or hashing of floating-point type but changing doubles to long doubles seems not to help though.

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

I have not really read through the problem very carefully but from my understanding, we could not rule out the possibility that $$$y$$$ ($$$reqSum - x$$$) may not be presented in the map.

If this is the case, the weird behaviour may have an explanation. This is because $$$[]$$$ operator for map and unordered_map actually has the side effect of creating a new entry when the key is not presented. Insertions to an existing map do not invalidate any iterators or references but insertions to an existing unordered_map invalidate all iterators when a rehash takes place. In this case, the continuation of the loop results in undefined behaviours.

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

    I agree with you, inserting into a map will not invalidate iterators, but inserting into an unordered map will invalidate iterators if it needs to rehash. I tried adding .reserve(3*n+10) to the unordered map solution, and that made it AC 155835249 .

    I would also like to add that keying with floating point numbers is generally a bad idea, and should be avoided (especially if you submit using 32 bit g++, see this blog). That said, I don't think floating point numbers caused the WA here.

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

      Thanks for your explanation, I understand your point, but can you answer one more question?

      Like I said, My unordered_map solution is giving WA verdict on test case 2 (on test input 3rd), Whereas it is working fine on both my C++ IDE/editor and on online IDEs/editors too on the same test case.

      I'm not understanding what is the exact reason/difference here making my same solution wrong on CF, but not on other IDEs/editors. Have you tried running my solution on other IDEs/editors?

      I'm wondering about the reason why my IDE or online IDEs/editors are not giving WA on the same test case. Could you please elaborate bit on this?

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

        You may find this interesting: Undefined Behaviour

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

        UB (undefined behaviour) can behave really weirdly. As long as your setup (your computer, compiler, compiler flags... etc) is slightly different you can get completely different behaviour. The way I look at it is that just having 1 UB in your code could make the compiler go haywire and completely mess up your program. But it could also be the case that you never notice the UB.

        About detecting things like UB, you can use tools like what is mentioned in this blog . The best thing however, is to try to avoid making UB in the first place.

        Finally one last warning again about floating point numbers. Depending on your setup you can different results. Even the exact same floating point calculation done twice in a row does not have to match. So unless you really know what you are doing, do not do things like hashing floating point numbers.

        → Reply