Multiples Of The Prime

libstdc++ sizes unordered_map from a fixed table of primes: ..., 92203, 99733, 107897, 116731, 126271, ..., reserve(n) rounds the bucket count up to the first prime at or above n, and std::hash on an integer is the identity function. A solution counts values in an unordered_map<uint64_t,int> and calls reserve(100000) first, for speed, which pins the bucket count at 107897. A Codeforces hacker reads that submitted source and sends this test:

// hack input: 100000 values, all multiples of 107897
for (int i = 1; i <= 100000; i++)
    printf("%llu\n", (unsigned long long)i * 107897);

Every key satisfies hash(k) % 107897 == 0, so all 100000 land in bucket 0 and each insertion scans the whole chain. Measured on GCC 15, the same loop over 100000 ordinary values finishes in under 0.01 s and this one takes 4.9 s, so the solution times out.

More than one option is correct. Which changes actually defend against this?

Drop the reserve call and let the table grow on its own, so the bucket count is no longer pinned to a round number

Multiply the key by a large fixed odd constant chosen once and hard-coded in the source

Wrap the key in a custom hash that mixes it with a per-run random constant read from chrono::steady_clock at startup

Switch to std::map, whose red-black tree gives O(log n) worst case per operation with no dependence on a hash function

Call rehash(1000003) so the bucket count is a large prime you chose rather than one the library chose