Блог пользователя THERE_IS_NO_RETURN

when i can use unordered_map and when i can't?
Автор THERE_IS_NO_RETURN, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    In this problem you have to use unordered_map for dp

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      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.

      → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      → Ответить
»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить