omggg's blog

How to make hash_table for < vector< int >,int> type?
By omggg, 4 years ago, In English

I want to use hash table of key : vector and value : int How can i use that ? Map<vector< int >,int> uses extra logn factor which many a times doesn't suite me and gives TLE. I just want to store frequency of a kind of vector.

Any help is appreciated. Thanks.

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

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

You are taking vector as a key value. There is whole extra factor of n where n is the size of the vector everytime you do operations with map.

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

    That would be okay to me. Just need to make unordered_map instead of map

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

Can you give link to the problem?

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

https://codeforces.com/blog/entry/62393?#comment-606294

You can do it by hashing the vector, but if you do that then the complexity will be $$$O(n^2/log$$$ $$$n)$$$, which is still too slow.

→ Reply