timur_jalgasbaev's blog

map VS unordered_map.
By timur_jalgasbaev, history, 3 hours ago, translation, In English

In yesterday's Div 3 contest in problem D, I used unordered_map to store elements, thinking it would be faster, but someone cracked my code, and my friend who had almost the same code, but used map instead of unordered_map, could not be cracked. Why was my code hacked, because unordered_map is faster than map, right? I have not been able to reach a clear answer to this question. So I ask from the respected Codeforces community, why did this happen? Thanks in advance for your answer.

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

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by timur_jalgasbaev (original revision, translated revision, compare)

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

unordered_map is basically O(1) for "random" inputs, but since the problemsetters/(people who make hacks) know that people will try using it, they can basically make an input that will "break" the unordered map and make it O(n) per access. Map on the other hand is always O(logn), and so its alot more safe to use.

→ Reply
»
117 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

I did the exact same thing. This article explains very well why the unordered_map fails and also discuss the solution to avoid such hacks in the future.

→ Reply
»
99 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
41 minute(s) ago, # |
← Rev. 4   Vote: I like it +2 Vote: I do not like it

Using gp_hash_table<int,int>mp works better than unordered_map because in the worst case, gp_hash_table operates in O(1), while unordered_map can degrade to O(n).Therefore, gp_hash_table is a better choise than unordered_map. If you use gp_hash_table, you need to include the following headers:

#include<ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
→ Reply
  • »
    »
    19 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The article referenced above says it is even easier to hack than unordered_map.

    → Reply