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 0 Vote: I do not like it

    This is my Submission 77023902 , its easy to understand. Problem : 1225D - Power Products

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

      Hey, I solved this problem recently. Hashing the vector won't make a big difference. Try to come with another approach :)

      But if you still want to try, polynomial hashing in Robin Karp might be useful here but it will don't give correct answer in every case.

      → 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