abcsumits's blog

hash function of dictionary has different complexity for int and string
By abcsumits, history, 2 years ago, In English

(huge difference refer to the following submission)

160762368 — accepted (str)

160761953 — tle (int)

both solution are same the only difference is the key in first is string and in 2nd the key is int which is causing tle .....

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

This is because some of the test cases are made to mess with the python hashing function.

Wrap your ints in this class before hashing to fix it:

from random import getrandbits
class Wrp(int):
    RANDOM = getrandbits(32)
    def __init__(self, x):
        int.__init__(x)
    def __hash__(self):
        return super(Wrp, self).__hash__() ^ self.RANDOM

If you want to learn more read this article: https://codeforces.me/blog/entry/101817

→ Reply