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

hash function of dictionary has different complexity for int and string
Автор abcsumits, история, 23 месяца назад, По-английски

(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 .....

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

»
23 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.com/blog/entry/101817

→ Ответить