omggg's blog

By omggg, 5 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

| Write comment?
»
5 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.

  • »
    »
    5 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

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

Can you give link to the problem?

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

https://codeforces.net/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.