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://mirror.codeforces.com/contest/1598/submission/155784539 (Accepted)
Solution 2 (using unordered_map STL): https://mirror.codeforces.com/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.
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.
Changing language to C++20 makes your solutions pass tests up to 106th (https://mirror.codeforces.com/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.
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
mapandunordered_mapactually has the side effect of creating a new entry when the key is not presented. Insertions to an existingmapdo not invalidate any iterators or references but insertions to an existingunordered_mapinvalidate all iterators when a rehash takes place. In this case, the continuation of the loop results in undefined behaviours.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.
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?
You may find this interesting: Undefined Behaviour
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.