Random Shuffling and Anti-Hash Defence

Randomness is the standard defence against adversarial test data. A problem setter can construct a killer input for a deterministic algorithm, but cannot predict your coin flips.

Correct shuffling

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(v.begin(), v.end(), rng);

Fisher-Yates, which is what std::shuffle implements:

for (int i = n - 1; i > 0; i--) {
    int j = uniform_int_distribution<int>(0, i)(rng);
    swap(v[i], v[j]);
}

Each permutation is equally likely. The common bug — swap(v[i], v[rand() % n]) with the full range — produces a non-uniform distribution.

Four things not to do

1. rand() — low quality, and rand() % n is biased when n does not divide RAND_MAX+1.
2. random_shuffle — uses rand(), removed in C++17.
3. mt19937 rng(12345) — a fixed seed is predictable and hackable.
4. srand(time(0)) — one-second granularity; multiple submissions in the same second share a seed.

Seed from chrono::steady_clock::now().time_since_epoch().count(), optionally XORed with an address for extra entropy.

What shuffling protects

Algorithm	Killer input without shuffling
Quicksort (first-element pivot)	already sorted → $O(n^2)$
Welzl’s enclosing circle	points ordered so each is outside → $O(n^3)$
Seidel’s LP	adversarial constraint order
Randomised incremental Delaunay	adversarial insertion order
Kuhn’s matching	adversarial adjacency order → $O(VE)$ worst case
Hash tables	colliding keys → $O(n)$ per operation
Binary search trees (unbalanced)	sorted insertion → a linked list

Shuffling the adjacency lists before running Kuhn’s matching is a cheap, real speedup that also defeats anti-Kuhn tests.

Anti-hash defence

The most common place randomness is required rather than merely helpful.

The attacks

• Thue-Morse sequence breaks any polynomial hash modulo $2^{64}$ (unsigned overflow) in $O(\log )$ length, for every base.
• Birthday attack finds a collision for a fixed $(B,M)$ in $O(\sqrt{M})$ offline work — trivial for $M=10^9+7$.
• unordered_map with the default hash<long long> (the identity on GCC) is broken by keys that are multiples of the internal bucket count.

The defences

// string hashing: random base, large Mersenne modulus
const long long MOD = (1LL << 61) - 1;
long long B = uniform_int_distribution<long long>(256, MOD - 2)(rng);

// hash map: randomised splitmix64
struct Hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t SEED = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + SEED);
    }
};
unordered_map<long long,int,Hash> mp;

See Polynomial Hashing for the collision analysis.

Zobrist hashing

Assign each element a random 64-bit value; hash a set as the XOR (or sum) of its members’ values.

uint64_t z[MAXV];
for (int i = 0; i < MAXV; i++) z[i] = rng();
// hash of a set: XOR of z[x] over its elements — updates in O(1)

Uses: board positions in game engines (incremental updates), comparing multisets, tree hashing, and detecting whether two ranges contain the same multiset.

Collision probability for $q$ comparisons is $\approx q/2^{64}$ — negligible.

Randomised checking

Random values verify identities cheaply:

Check	Method
$AB=C$ for matrices	Freivalds: test $A(Br)=Cr$ for random $r$
Two multisets are equal	compare Zobrist hashes
A polynomial is identically zero	evaluate at random points (Schwartz-Zippel)
Two expressions are equal	evaluate both at random values
A perfect matching exists	random Tutte matrix, check the rank

Schwartz-Zippel: a non-zero polynomial of total degree $d$ over a field of size $q$ vanishes at a random point with probability $\le d/q$. This one lemma underlies polynomial identity testing, hashing, and the matching test.

When randomness is not allowed

Some interactive and hacking-format problems require deterministic behaviour, and a few checkers reject non-reproducible output. Read the statement. Otherwise, randomise by default — it costs one line and removes an entire category of failure.

See also: String Hashing · Randomized Algorithms · STL Containers