rranaut07's blog

Why? Why? Why?
By rranaut07, history, 12 months ago, In English

There is something interesting I notice in Codeforces Round 909(Div 3). In D question I got TLE in 20th test case because I took Unordered Map instead of Map because as the number of enteries increase unordered map start experiencing collision Right. But I seen some code who take unordered_map<double, int> that run absolutely fine. I have 2 doubts.

  1. why unordered_map<double, int> work but unordered_map<int, int> didn't work. Is There some another hash function algorithm work in double?

  2. As number of entries are low then both map and unordered map work. But as the entries are high unordered map gives TLE. So, is it okay if I use every time map in every question and not use unordered map or there is some case where unordered map is preferred over map.

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

Comments Comments (4)
| Write comment?
»
12 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Refer to the following blog,
Blowing up unordered_map, and how to stop getting hacked on it

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

    The best guess I have is that the hash function to map to doubles is not used by people who hack your solutions. (similar to how if you custom hash, they don't exactly know about collisions of your hash function). that is why your std::unordered_map<double, int> stuff works against hacking.

    I thought it was trivial after reading the blog. Seems like it wasn't (since I got downvoted).
    I didn't mean to be rude, I was just stating that the blog has a complete answer which can help you out with your query. It seems like the other answers till now also just say "use custom hash" or "it's worth using std::map despite the associated logarithmic factor for most problems".

    The blog linked above also supports these answers and kind of answers the query much better than the other 2 comments here do (at the time of writing there were 2 comments), seemingly people don't read that or think it's cool to put some query that the blog doesn't directly answer (but points to the answer) and are not pleased when someone refers to an existing blog.

    I understand the OP wants a definitive answer to their query, and I probably don't qualify enough to answer it (which is why I was hesitant to write the first part of this comment). But it is also incorrect to assume the OP has read the above mentioned blog. So I did what I could, i.e., shared the blog which has related information and let the OP decide for themselves.

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

usually classic map is enough in CF problems.

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

Use a custom hash function or simply use map it would always work.

→ Reply