pypy’s dict implementation hits TLE while cpython’s could pass

[e-yi]

I find it curious and hope someone with knowledge of Pypy could provide some insights.

The problem is https://codeforces.com/contest/2061/problem/D.

Here is the code snippet that leads to a Time Limit Exceeded (TLE) error when executed with Pypy (not a problem if using CPython):

# author: xiaoxiaobaozi
import sys
from collections import defaultdict
 
 
def main():
    for _ in range(int(input())):
        n, m = map(int, input().split())
        a = [int(i) for i in input().split()]
        b = [int(i) for i in input().split()]
 
        d = defaultdict(int)
        for x in a:
            d[x] += 1
    
        while b and len(b) <= n:
            x = b.pop()
            if d[x] > 0:
                d[x] -= 1
                n -= 1
                if d[x] == 0:
                    del d[x]
            else:
                if x % 2 == 1:
                    b.append(x // 2)
                    b.append(x // 2 + 1)
                else:
                    b.append(x // 2)
                    b.append(x // 2)
    
        print("YES" if n == 0 else "NO")
 
 
if __name__ == "__main__":
    main()

Interestingly, with a slight modification, the code manages to pass the time constraints with Pypy:

import sys
from collections import defaultdict
from random import randint

rd = randint(1, 10 ** 9)  ###########

def main():
    for _ in range(int(input())):
        n, m = map(int, input().split())
        a = [int(i) for i in input().split()]
        b = [int(i) for i in input().split()]

        d = defaultdict(int)
        for x in a:
            d[x ^ rd] += 1  ###########

        while b and len(b) <= n:
            x = b.pop() ^ rd  ###########
            if d[x] > 0:
                d[x] -= 1
                n -= 1
                if d[x] == 0:
                    del d[x]
            else:
                x ^= rd  ###########
                if x % 2 == 1:
                    b.append(x // 2)
                    b.append(x // 2 + 1)
                else:
                    b.append(x // 2)
                    b.append(x // 2)

        print("YES" if n == 0 else "NO")


if __name__ == "__main__":
    main()

cpython version: 3.8.10
pypy version: 3.10 (7.3.15, 64bit)

[cfbolz]

I'm happy to look into this, but I would need an input file that shows the problematic behaviour so I can debug this locally.

[e-yi]

Thanks! Here is the input file.

[BarrensZeppelin]

I think the input is specifically constructed to make your solution time out.
See #3724

[e-yi]

This is evil... :(

[e-yi]

And also a very clever hack. Thanks for sharing this @BarrensZeppelin