THERE_IS_NO_RETURN's blog

when i can use unordered_map and when i can't?
By THERE_IS_NO_RETURN, history, 4 years ago, In English

hi i am learning dynamic programming and i wonder what are the cases when i can use unordered_map to store results without fear from TLE ? what is time complexity for inserting and finding out if the result stored or not ? i have searched and find many answers but it was complicated for me because i am totally beginner.

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

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

Usually in dynamic programming problems people directly declare tables of dimensions that can cover all possible states. I haven't yet seen any problem where we would need unordered_map for dp.

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

    Bitmask dp (generally when the search space is big with many unreachable states).

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

      I don't think I have ever actually seen that. Care to give some examples?

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

    In this problem you have to use unordered_map for dp

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Haha , I had actually solved this problem in contest. I had forgotten that I used map to solve it. Yeah, it's a nice example for it.

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

    yeah the typical tutorials i saw use lookup table to hold the results but what we do in such cases where we need to use complex keys or even the numbers is way biggers should i declare an array of size 10^9 to just hold couple of items.

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

      If the problem actually needs memoization of such large-magnitude states then probably you don't have to worry about "using unordered_map to store results without fear from TLE".

      If the intended solution requires map , then undorderd_map/map will pass without TLE most probably.

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

    I sometimes see problems that requires coordinate compression DP though. But, I think a normal map is enough except if timelimit is that tight.

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

      ok but what is the limits when i should use simple array ,map,unordered_map and can't use all this methods i once saw a blog here about that if you used unordered map your solution can be hacked due to its hash implementation this is the only thing i could understood from this blog so.

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

If you can use an array, use an array. If the number of total states is too large to be stored in an array but the amount of states you will visit is small enough then use an unordered map.

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

In my (sad)experience, don't use unordered_map in educational or div3 contests unless you want yourself to be hacked!

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

You may refer to https://codeforces.net/blog/entry/62393

In short unordered_map uses a hash map and it is (averagely) fast if there is no/a few collisions. However the hashing algorithm is well known and we can create a test case making lots of collisions, and the time complexity with grows in $$$O(n^2)$$$. In usual competitive programming contest it will include such test cases to ban the standard unordered_map. (In CF the code are disclosed so writing a deterministic version will also be hacked easily)

Another worth mentioning is C quicksort killer

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

Sometimes you can't use arrays to store your state, like imagine for some problem you have a number and you need to either divide it by two or by three, the number of states is small but the numbers may be too big. Here, the easiest way is using maps or unordered_maps.

The unordered maps uses some hashes to store its values, but sometimes more than one value is stored in the same hash so when you need to access some value the unordered map may need to iterate over all of these values with same hash as the one you want.

For that, some contest authors set some tests for the default unordered maps so that all stored numbers have the same hash and the unordered maps will take $$$O(n)$$$ to find values. So what's the solution? you need to change the default hash so it's impossible for authors to set such a testcase for you.

You can read the following blogs which teaches you how:

Blowing up unordered_map, and how to stop getting hacked on it

[Tutorial] Everything about unordered_map

Please correct me if I said anything wrong.

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

    that was good explanation and the second blog seems to be clear for a beginner like me thanks alot !

    → Reply