Randomized strategies

Some problems are too hard to solve deterministically within the time limit. A randomized algorithm makes random choices and succeeds with high probability. If you run it many times and take the best answer, or use enough trials that failure is very unlikely, randomization becomes a practical tool.

Shuffling and trying random permutations

Suppose a problem asks for any valid permutation satisfying some constraints. If most permutations are valid, you can shuffle randomly until you find one.

1import random2
3
4def is_derangement(perm):5    """Check if no element is in its original position."""6    for i, val in enumerate(perm):7        if val == i:8            return False9    return True10
11arr = [0, 1, 2, 3, 4]12random.seed(42)13
14for trial in range(10):15    random.shuffle(arr)16    if is_derangement(arr):17        print(f"Trial {trial}: Found derangement: {arr}")18        break

Trial 1: Found derangement: [4, 2, 3, 0, 1]

This code creates a random permutation by shuffling a list. It checks a condition (here, that no element is in its original position, a derangement). If the condition fails, it shuffles again. With high probability, a random permutation satisfies the condition after a small number of tries.

Random guesses with fixed seed

In contests, you want reproducible results for debugging. The random module has a seed: set it before generating random numbers and you get the same sequence every time.

1import random2
3random.seed(42)4
5print("First run with seed 42:")6for _ in range(5):7    print(random.randint(1, 100), end=" ")8print()9
10random.seed(42)11print("Second run with seed 42:")12for _ in range(5):13    print(random.randint(1, 100), end=" ")14print()

First run with seed 42:
82 15 4 95 36 
Second run with seed 42:
82 15 4 95 36 

With random.seed(42), every run of this code produces the same "random" output. You can test your solution locally and then submit it knowing that the random trials will be the same.

Probability and number of trials

If each trial succeeds with probability p, the probability of failure after k trials is (1 - p)^k. To keep this small, you can solve for k.

Say p = 0.5 (a coin flip succeeds half the time). To get failure probability below 1 / 1,000,000, you need (1 - 0.5)^k < 0.000001. That is, 2^k > 1,000,000, so k > 20. Twenty trials suffice.

1import math2
3
4def trials_needed(success_prob, target_failure_prob):5    """Calculate trials needed for a given failure probability."""6    if success_prob <= 0 or success_prob >= 1:7        return None8    # (1 - p)^k < target_failure_prob9    # k > log(target) / log(1 - p)10    k = math.log(target_failure_prob) / math.log(1 - success_prob)11    return int(k) + 112
13print("Trials needed for different probabilities:")14for p in [0.5, 0.3, 0.1]:15    trials = trials_needed(p, 1e-6)16    print(f"p={p}: {trials} trials for failure prob < 10^-6")

Trials needed for different probabilities:
p=0.5: 20 trials for failure prob < 10^-6
p=0.3: 39 trials for failure prob < 10^-6
p=0.1: 132 trials for failure prob < 10^-6

The function computes the required trials given a success probability and a target failure probability. You can use this to decide whether randomization is viable.

Randomized quick-select

A practical example is finding the median or any order statistic. The deterministic algorithm (quickselect) has worst-case O(N^2) time on bad inputs. A randomized version picks a random pivot instead of a deterministic one. With high probability, the pivot is good and the algorithm is fast.

1import random2
3
4def partition(arr, left, right, pivot_idx):5    """Partition around a pivot; return the pivot's final position."""6    pivot = arr[pivot_idx]7    arr[pivot_idx], arr[right] = arr[right], arr[pivot_idx]8    store_idx = left9    for i in range(left, right):10        if arr[i] < pivot:11            arr[i], arr[store_idx] = arr[store_idx], arr[i]12            store_idx += 113    arr[right], arr[store_idx] = arr[store_idx], arr[right]14    return store_idx15
16def select(arr, k):17    """Find the k-th smallest element (0-indexed)."""18    left, right = 0, len(arr) - 119    while left <= right:20        pivot_idx = random.randint(left, right)21        pivot_idx = partition(arr, left, right, pivot_idx)22        if pivot_idx == k:23            return arr[k]24        elif pivot_idx < k:25            left = pivot_idx + 126        else:27            right = pivot_idx - 128    return None29
30random.seed(42)31arr = [3, 1, 4, 1, 5, 9, 2, 6]32print(f"Array: {arr}")33print(f"3rd smallest: {select(arr, 2)}")

Array: [3, 1, 4, 1, 5, 9, 2, 6]
3rd smallest: 2

The function picks a random pivot and partitions the array. Recursively search in the part containing the target rank. With a good pivot, the depth is O(log N) and the total time is O(N). Bad pivots are unlikely, so the algorithm is fast in practice.

Why randomization helps

Randomization breaks worst-case input structures. A deterministic algorithm that always picks the first element as pivot falls apart on sorted input: you get O(N^2) time. A randomized pivot is unlikely to be bad on the same input twice, so adversarial inputs do not hurt.

The tradeoff is simplicity. A randomized algorithm is often easier to code than a deterministic one. Quickselect with random pivots is easier than median-of-medians (which is deterministic but complex). When the time limit allows it, randomization is a reasonable choice.

The key is predicting the failure probability. If you shuffle a permutation and check a property, and most permutations satisfy the property, then a few shuffles will find one. If only 0.1% of permutations are valid, you need hundreds of shuffles. Calculate this beforehand and verify that your time budget allows it.

A second example: guessing hidden values

Imagine a problem where you must guess one of K hidden values. Each guess has a 1/K chance of being right. After N guesses, your failure probability is (1 - 1/K)^N. For K=100 and N=460, the failure probability is below 10^-2. For N=4600, it is below 10^-20.

If the cost per guess is fast (e.g., checking an invariant in O(1) time), then 4600 guesses with fast checks is practical. But if each guess requires an O(N^2) simulation, then 4600 guesses is too slow.

You must estimate the cost of each guess and the failure probability target. If the solution cost is 4600 * (cost per guess), and your time limit is 1 second, work backwards to find a feasible cost per guess. If it is too high, randomization is not viable and you need a deterministic approach.

Common mistakes

A common error is testing only with an unseeded run. Without a seed, each run of your solution produces a different sequence of random numbers, so a bug that only shows up on some sequences is hard to reproduce. Set the seed explicitly while testing, so a failure you find once stays reproducible: random.seed(42).

Another mistake is under-estimating how many trials you need. If your success probability per trial is low (say 0.1), the mathematics is harsh. To reach failure probability 10^-6, you need about 140 trials. To reach 10^-12, you need 400 trials. Before you rely on randomization, calculate the number of trials explicitly using logarithms, not intuition.

A third error is not testing your randomized solution thoroughly. Randomized algorithms can pass the sample test by luck and fail on the real test. Run your solution many times on the same input and verify that it produces consistent answers (or at least that the failure rate is negligible).

Also, avoid using randomization when a deterministic algorithm is fast enough. Randomization adds complexity and makes debugging harder. A deterministic O(N^2) solution that passes is better than a randomized solution that might fail on unlucky random numbers.