Same Solutions but different results

Hello Everyone, I came across the problem named CHOCPAIR. I tried to solve it but failed. I look at @tciitb’s solution. My idea is the same as his. Still, my solution wasn’t accepted. So I followed his code. But still, my code produces the wrong answer. Someone, Please help.

Problem Link : https://www.codechef.com/problems/CHOCPAIR

My solution : https://www.codechef.com/viewsolution/19853908

@tciitb’s solution: https://www.codechef.com/viewsolution/19844048

I don’t have much knowledge about C++, but you didn’t check if the value ‘b’ is present in the set.
Checking it yields TLE (which can be removed by using ‘printf’ and ‘scanf’). Most probably, ‘getitem’ returns a dump value if the key is not present in the set.

ACed solution: https://www.codechef.com/viewsolution/19854328
WA solution: https://www.codechef.com/viewsolution/19854334 (same code without the ‘contains’ check)

You are not using reserve() function which is giving you wrong answer. Don’t know much about performance of unordered map. But this might help
http://codeforces.com/blog/entry/21853
https://en.cppreference.com/w/cpp/container/unordered_map/reserve
your solution gives A/C with reserve()-
https://www.codechef.com/viewsolution/19854409

Thank you for help :slight_smile: but the use of reserve and max_load_factor seems just optimization. Can you tell me What part did they play here?

Thank you for help :slight_smile: but whenever an element is not present in the map, it returns zero so answer shouldn’t have been affected by checking the presence of element at all.

@vijju123 please help with this issue…really confused about working of unordered_map in STL.

Okay, looking at it.

When you are accessing m[b] when b doesn’t exist in the unordered map, it inserts that key with a value of 0. This insertion could cause iterator invalidation, and hence your loop goes for a toss.

Have a look at the “Iterator invalidation” section of https://en.cppreference.com/w/cpp/container/unordered_map

“insert, emplace, emplace_hint, operator[] - Only if causes rehash”

This is probably the issue.

1 Like