Randomization Techniques

Overview

Prerequisites: Random Functions and Probability Basics

This article will provide a simple classification of randomization techniques in OI/ICPC and introduce each category. It will also cover some methods rarely used in OI/ICPC but similar in style, marked with (*).

This classification does not represent a broad consensus and certainly cannot cover all possibilities, so it is for reference only.

Notation and Conventions:

• \(\mathrm{Pr}[A]\) denotes the probability of event \(A\).
• \(\mathrm{E}[X]\) denotes the expected value of random variable \(X\).
• The assignment operator \(:=\) introduces a new quantity, e.g., \(Y:=1926\) means introducing a quantity \(Y\) with value \(1926\).

Covering Target Elements with Random Sets

There is one (or more) solution we want in a vast solution space. We can attempt multiple "net casts"; as long as one cast catches the target solution, we succeed.

Example: Tripartite Graph Decision

Problem

Given a simple undirected graph with \(n\) vertices and \(m\) edges, color each vertex with one of RGB such that any pair of neighbors have different colors, or report that it is impossible.

For each vertex \(v\), independently and uniformly randomly choose a color \(C_v\) from \(\{R,G,B\}\), and stipulate that \(v\) is not colored with \(C_v\). The probability that the optimal solution exactly satisfies these constraints is clearly \(\big(\frac 23\big)^n\).

Under these constraints, for a pair of neighbors \((u,v)\), the requirement "colors of \(u\) and \(v\) are different" is equivalent to the following implication:

• For any color \(X\) different from \(C_u\) and \(C_v\), if \(u\) is colored \(X\), then \(v\) is colored \(\{R,G,B\}\setminus\{X,C_v\}\).

Thus, we can set a Boolean variable \(B_v\) for each \(v\), whose value indicates which of the two remaining colors \(v\) is colored with. Using a 2-SAT model, we can solve this problem in \(O(n+m)\) time.

The success probability per run is \(\big(\frac 23\big)^n\). Running the algorithm \(-\big(\frac 32\big)^n\log \epsilon\) times and outputting the solution if any run succeeds ensures a correctness probability of \(1-\epsilon\). (See "Probability Upper Bound Analysis" later.)

---

Review: In this problem, the "solution space" is the set \(\{R,G,B\}^n\). Each time, we randomly impose constraints to search for the "target solution"—a valid coloring—within a reduced range.

Example: CodeChef SELEDGE

Brief Description

Given an undirected graph with non-negative weights on vertices and edges, find an edge set \(S\) of size \(\leq K\) that maximizes the sum of weights of vertices incident to \(S\) minus the sum of edge weights in \(S\). A vertex's weight is counted only once.

Observation: If three selected edges form a chain, deleting the middle one is never worse; if selected edges form a cycle, deleting any edge is never worse.

Corollary: The optimal edge set must form several disjoint star graphs (i.e., trees with diameter at most 2).

Corollary: The optimal edge set must form a bipartite graph.

We independently and uniformly randomly color each vertex black or white, and require that this coloring exactly matches the bipartite coloring corresponding to the optimal solution.

Compute the probability that the optimal solution satisfies this requirement:

• Consider a star graph with \(n\) vertices. It clearly has 2 valid colorings, so the probability it is correctly colored is \(\dfrac 2{2^n}=2^{1-n}\).
• Suppose the optimal solution consists of stars with vertex counts \(a_1,\cdots,a_l\). Then \((a_1-1)+\cdots+(a_l-1)\leq K\), where \(K\) is the maximum number of edges we can select.
• Thus, the probability that all stars are correctly colored is \(2^{1-a_1}\cdots 2^{1-a_l}\geq 2^{-K}\).

Under this requirement, attempt to compute the optimal answer via a min-cost flow model:

• Construct a bipartite graph: white vertices on the left connected to \(S\), black vertices on the right connected to \(T\).
  • For each white vertex \(v\), add an edge from \(S\) to \(v\) with capacity 1 and cost \(-A_v\), and an edge with capacity \(\infty\) and cost 0.
  • For each black vertex \(v\), add an edge from \(v\) to \(T\) with capacity 1 and cost \(-A_v\), and an edge with capacity \(\infty\) and cost 0.
• For each original edge \((u,v,B)\) where \(u\) is white and \(v\) is black, add an edge from \(u\) to \(v\) with capacity 1 and cost \(B\).
• Limit the total flow to at most \(K\) in this graph. The negative of the minimum cost is the answer.

Using SPFA for min-cost flow, the complexity is \(O\big(K^2(n+m)\big)\), justified as follows:

• First, clearly the number of SPFA runs \(\leq K\).
• In one SPFA run, any vertex is enqueued at most \(O(K)\) times because:
  • At any moment, there are at most \(3K\) edges with flow; otherwise, it would imply selecting more than \(K\) edges in the original graph.
  • For any augmenting path of length \(L\), at least \(\dfrac L2-2\) edges are reverse edges of some edge with flow, since forward edges go from left to right, and only reverse edges go from right to left.
  • Combining these, any augmenting path length is at most \(6K+4\).
• Thus, the complexity is \(O\big(K^2(n+m)\big)\).

Similar to the previous problem, we need to repeat the process \(-2^K \log\epsilon\) times to achieve \(1-\epsilon\) correctness probability. Total complexity: \(O\big(2^KK^2(n+m)\cdot -\log\epsilon\big)\).

Hitting Target Sets with Random Elements

We need to determine any element of a set. We randomly select elements, hoping to hit this set exactly.

Example: Gym 101550I

Brief Description

The graph consists of two parallel chains connected by two parallel edges. Given several simple paths (each representing a call) on this graph, select the minimum number of edges to place eavesdroppers such that every given path contains at least one eavesdropper.

The graph can be decomposed into a cycle plus four chains extending from it. For any chain \(C\), consider placing eavesdroppers on it. A greedy algorithm yields a scheme satisfying:

• Minimizes the number of eavesdroppers while intercepting all calls entirely within \(C\).
• Under the above condition, minimizes the distance from eavesdroppers on \(C\) to the cycle.
  • This aims to intercept calls with exactly one endpoint inside \(C\) as much as possible.

Next, consider the four edges connecting chains to the cycle. We brute-force enumerate whether eavesdroppers are placed on these edges. Clearly, placing eavesdroppers on these four edges is optimal for intercepting calls crossing chains and the cycle. Now, calls can be categorized:

1. Calls entirely within a chain. These are already intercepted and can be ignored.
2. Calls crossing chain and cycle, already intercepted. They can be ignored.
3. Calls crossing chain and cycle, not intercepted. We can truncate their chain portion (since eavesdropper placement on chains is fixed), keeping only the cycle portion.
4. Calls entirely on the cycle.

Now the problem reduces to a cycle problem.

Let \(S\) be the set of edges on the cycle where eavesdroppers are placed in the optimal solution. If we determine any element \(e \in S\), we can:

• Break the cycle into a chain at \(e\).
• Starting from \(e\), greedily find the next edge to place an eavesdropper. With suitable preprocessing, each greedy step can be done in \(O(1)\).
• Solve the problem in \(O(|S|)\) time.

We randomly select an edge \(e'\) on the cycle, stipulate \(e'\in S\), and run the above process. Repeat multiple times and take the best result.

Analyze single-run complexity:

• Observation: Let \(S'\) be the optimal solution among schemes that select \(e'\). Then \(|S'|\leq |S|+1\).
• Thus, single-run complexity is \(O(|S'|)=O(|S|)\).

Analyze success probability:

• Clearly, single-run success probability is \(\dfrac {|S|}n\), where \(n\) is the cycle length.
• So we need to repeat \(-\dfrac n{|S|}\log\epsilon\) times to achieve \(1-\epsilon\) correctness probability.

Overall complexity: \(O\big(|S|\cdot -\dfrac n{|S|}\log\epsilon\big)=O(-n\log\epsilon)\).

Example: CSES 1685 New Flight Routes

Brief Description

Given a directed graph, add the minimum number of edges to make it strongly connected, and output the scheme.

First, perform strongly connected component (SCC) condensation. Our goal is clearly to make every sink reachable from every source.

It can be proven that we only need to add edges from sinks to sources, because any other edge can be replaced by a no-worse edge from a sink to a source.

A core operation: take a sink \(t\) and a source \(s\) (they need not be in the same weakly connected component), add edge \(t\to s\) to make both \(s\) and \(t\) cease to be sources or sinks (call this Goal I). Ideally, each such operation reduces one sink and one source. We repeat until only one sink or one source remains, which is trivial. Thus, we conjecture the answer is the maximum of the number of sources and sinks.

It can be shown that such an operation achieves Goal I iff: \(t\) has a predecessor other than \(s\), and \(s\) has a successor other than \(t\). It can be proven (proof given later) that for any DAG with at least two sources and two sinks, such \((s,t)\) exists. However, existence does not help construct a scheme; further analysis is needed.

• This condition alone is insufficient for an algorithm because adding edge \(t\to s\) may affect the validity of other \((s',t')\) pairs, which is hard to handle.

Note we know little about source-sink relationships (even checking reachability between a source-sink pair requires dfs + bitset preprocessing, which time limits may not allow). This suggests we need some general and powerful property.

Observation: The number of \((s,t)\) pairs not satisfying Goal I is at most \(n+m-1\), where \(n\) is the number of sources and \(m\) is the number of sinks.

• Reason: For each such \((s,t)\), treat it as an edge between \(s\) and \(t\). All such edges form several disjoint chains, so the number of edges is at most the number of vertices minus one.
• Motivation: To apply existence results in algorithms, we often need to strengthen qualitative results into quantitative ones.

Corollary: Uniformly randomly selecting \((s,t)\), the probability it satisfies the requirement is \(\geq \dfrac {(n-1)(m-1)}{nm}\).

• Note this conclusion is strictly stronger than the earlier existence result.

Corollary: Independently and uniformly randomly selecting \(\dfrac {\min(n,m)}2\) pairs \((s,t)\) without common elements, and sequentially operating on them (i.e., adding edge \(t\to s\)), the probability that all operations satisfy Goal I is \(\geq \dfrac 14\).

• Reason:

\[ \begin{aligned} &\phantom{=\ }\dfrac {(n-1)(m-1)}{nm}\cdot\dfrac{(n-2)(m-2)}{(n-1)(m-1)}\cdots\dfrac{(n-k)(m-k)}{(n-k+1)(m-k+1)}\\ &=\dfrac{(n-k)(m-k)}{nm}\\ &\geq \dfrac 14 \end{aligned} \]

After selecting \(k\) pairs \((s,t)\), checking if all satisfy Goal I is easy: run SCC condensation again and see if both \(n\) and \(m\) decrease by \(k\). Note if we reduce by \(k=\dfrac{\min(n,m)}2\) each time, \(\min(n,m)\) will become 1 within \(O\big(\log(n+m)\big)\) rounds, reducing to the trivial case.

Algorithm Pseudocode

while(n>1 and m>1):
    randomly choose k=min(n,m)/2 pairs (s,t)
    add edge t->s for all these pairs
    if new_n>n-k or new_m>m-k:
        roll_back()
solve_trivial()

Complexity: \(O\big((|V|+|E|) \log |V|\big)\).

---

Review: We need to determine any pair \((s,t)\) that achieves Goal I. We randomly select \((s,t)\).

Using Randomization to Obtain Properties of Random Data

If a problem's data is randomly generated, we might exploit properties of random data. Sometimes, even when data is not random, we can use randomization to endow it with certain characteristics of random data to help solve the problem.

Example: Randomized Incremental Method

Randomly generated element sequences may have properties like "expected number of prefix optimal solution changes is small." The randomized incremental method randomizes the input sequence to gain such properties.

See Randomized Incremental Method.

Example: TopCoder MagicMolecule Randomized Solution

Brief Description

Given an undirected graph with \(n\) vertices and vertex weights, find the clique of size at least \(\dfrac {2n}3\) with maximum total weight.

\(n\leq 50\)

A natural idea is meet-in-the-middle. Partition vertices evenly into left and right halves \(V_L,V_R\) (each of size \(\dfrac n2\)). Compute array \(f_{L,k}\) representing the maximum total weight of all cliques of size \(\geq k\) within subset \(L\subseteq V_L\). Then for each clique \(C_R\) in the right half, compute which left vertices are adjacent to all vertices in \(C_R\) (call this set \(N_L\)), and update answer with \(f_{N_L,\frac 23 n-|C_R|}+\textit{value}(C_R)\).

• Note \(f_{L,k}\) can be updated in \(O(1)\). Specifically, take \(d\) as any element in \(L\), then:
  • If \(d\) is not in the optimal clique, transition from \(f_{L\setminus \{d\},k}\).
  • If \(d\) is in the optimal clique, transition from \(f_{L\cap N(d),k}+\textit{value}(d)\), where \(N(d)\) is \(d\)'s neighbor set.
  • Also update \(f_{L,k}\) with \(f_{L,k+1}\).

This solution times out. Attempt optimization:

• Partition vertices randomly and uniformly. Then with significant probability, the optimal clique \(C_{res}\) is also evenly split (i.e., \(|C_{res}\cap V_L|=|C_{res}\cap V_R|\)).
  • Of course, \(|C_{res}|\) might be odd. For simplicity, assume it's even; odd case doesn't change essence.
  • Experiments show about 20 random attempts yield high probability of at least one success. So if our algorithm relies on "\(C_{res}\) is evenly split," repeating 20 times and taking the best also ensures high probability correctness.
• With this property, we can directly require left clique \(L\) and right clique \(C_R\) sizes \(\geq \dfrac n3\). This improves complexity in two ways:
  • \(f\) can omit the size dimension.
  • Since only cliques of size \(\geq \dfrac n3\) are considered, the number of left cliques \(L\) and right cliques \(C_R\) reduces to about \(1.8\cdot 10^6\).
• Now bottleneck becomes computing weight sum of a subset in one half, requiring \(O\big(2^{|V_L|}+2^{|V_R|}\big)\) preprocessing.
  • Solution: Further split \(V_L,V_R\) internally; when querying subset weight sum, split subset into left and right halves, query separately, and sum answers.
• This passes the problem.

---

Review: A random set has the property "the split into two halves is not too unbalanced," and we obtain this property via random partitioning.

Randomization for Hashing

Example: UOJ #207 GongJianDaYe Travels in Changsha

Brief Description

Maintain a dynamically changing tree and a dynamically changing set of vertex pairs. Support:

• Delete/add edges. Guarantee the result is still a tree.
• Add/delete a vertex pair.
• Given an edge \(e\), determine whether for every vertex pair \((s,t)\) in the set, \(e\) lies on the simple path between \(s\) and \(t\).

For each edge \(e\), define set \(S_e\) as the set of key paths (i.e., \((a,b)\) in the problem) passing through \(e\). Dynamically maintain a hash value for \(S_e\), making it easy to check if \(S_e\) equals the full set (i.e., whether \(e\) is a "necessary path").

Hash method: Assign each \((a,b)\) a random non-negative integer \(H_{(a,b)}\) within \(2^{64}\). The hash of a set is the XOR sum of its elements' \(H\) values.

Thus, the hash value of any fixed set follows uniform distribution over \(R:=\left\{0,1,\cdots,2^{64}-1\right\}\) (i.e., hash values range over \(R\), each with equal probability). Because:

1. A single \(H_{(a,b)}\) clearly follows uniform distribution.
2. The XOR sum of two independent random variables uniformly distributed over \(R\) also follows uniform distribution over \(R\). Self-proof is straightforward.

Thus the algorithm's correctness is guaranteed.

To maintain hash values, use LCT.

Example: CodeChef PANIC and Its Error Rate Analysis

Main steps of this problem:

1. It can be proven³ that \(S(N)\) follows a linear recurrence of order \(O(K)\) in \(N\).
2. Use Berlekamp–Massey (BM) algorithm to find the recurrence.
3. Using Cayley–Hamilton theorem, compute \(S(N)\) from the recurrence.

Here we focus on part 2: how to find a recurrence for a matrix sequence. So consider:

Problem

Given a matrix sequence modulo \(P:=998244353\) satisfying a homogeneous linear recurrence (with scalar multiplication and addition defined as matrix operations), find the shortest recurrence.

If a sequence of matrices satisfies recurrence \(F\), then each entry also satisfies \(F\). However, finding the shortest recurrence \(F'\) for a specific entry might yield \(F'\) shorter than \(F\), causing issues.

Solution: Assign each matrix entry \((i,j)\) a random weight \(x_{i,j} < P\). For each matrix in the sequence, compute the weighted sum modulo \(P\) of all entries, forming a number sequence. Run BM on this sequence.

Error rate analysis:

• Suppose the above method finds an \(l\)-order recurrence \(F'\) different from \(F\) (and obviously no longer than \(F\)).
• Since the matrix sequence does not satisfy \(F'\), there exists some entry \((i,j)\) such that its corresponding sequence \(S_{i,j}\) violates \(F'\) at some \(N\). That is:

\[ S(N)_{i,j}-F'_1S(N-1)_{i,j}-\cdots-F'_lS(N-l)_{i,j}\not\equiv 0\pmod {P} \]

• Assuming \((i,j)\) is the only violating position, then:

\[ T_{i,j}:=\Big(x_{i,j}\cdot\big(S(N)_{i,j}-F'_1S(N-1)_{i,j}-\cdots-F'_lS(N-l)_{i,j}\big)\bmod P\Big)=0 \]

• This holds only if \(x_{i,j}=0\), probability \(P^{-1}\).
• What if multiple positions violate?
  • For each such \((i,j)\), \(T_{i,j}\) follows uniform distribution over \(R:=\{0,1,\cdots,P-1\}\).
  • Several independent random variables uniformly distributed over \(R\), summed modulo \(P\), still follow uniform distribution over \(R\). Self-proof straightforward.
  • Thus error probability remains \(P^{-1}\).

Example: UOJ #552 Isomorphism Duck and Its Error Rate Analysis

Brief Description

Given two directed graphs \(G_0,G_1\) with edge labels as lowercase letters, compute for each graph "the multiset of strings corresponding to all paths" (possibly infinite), and check if these multisets are equal. If not, output the shortest string whose counts differ.

Let \(f_{K,i,j}\) denote the hash value of the multiset of all strings corresponding to length-\(j\) paths starting from vertex \(i\) in \(G_K\). Process states in increasing \(j\), enumerating outgoing edges from \(i\) as the first edge.

To check if a bad string of length \(=L\) exists, "integrate" \(\{f_{0,*,L}\}\) and \(\{f_{1,*,L}\}\) and compare (wildcard * means over all vertices). The official solution¹ proves the shortest bad string (if exists) length \(\leq n_1+n_2\), so complexity is reliable.

Now consider hash method. Conventional hashing—mapping string \(a_1a_2\cdots a_k\) to \(\big(a_1+Pa_2+P^2a_3+\cdots+P^{k-1}a_k\big)\bmod Q\), and multiset hash as sum modulo \(Q\)—fails here. Counterexample: sets {"ab","cd"} and {"cb","ad"} have same hash regardless of \(P,Q\).

The issue is that a string's hash is a sum, whose terms can be separated and recombined. To avoid this, use a product hash. Also, multiplication commutativity makes different positions indistinguishable, so assign different weights to different positions.

For each pair \((c,j)\) (character \(c\), position \(j\)), pre-generate random \(x_{c,j}\). Map string \(a_1a_2\cdots a_k\) to \(x_{a_1,1}x_{a_2,2}\cdots x_{a_k,k}\bmod Q\) (where \(Q\) is a randomly chosen prime). Multiset hash is sum modulo \(Q\). Analyze error rate.

(*)Schwartz–Zippel Lemma

Let \(f\in F[z_1,\cdots,z_k]\) be a non-zero \(k\)-variate polynomial of degree \(d\) over field \(F\), and \(S\) a finite subset of \(F\). Then at most \(d\cdot |S|^{k-1}\) tuples \((z_1,\cdots,z_k)\in S^k\) satisfy \(f(z_1,\cdots,z_k)=0\).

If you don't know what a field is

You only need to know these are fields:

1. Residue system modulo prime, with its operations.
2. Real numbers, with its operations.

Corollary: If \(z_1,\cdots,z_k\) are chosen independently uniformly at random from \(S\), then \(\mathrm{Pr}\big[f(z_1,\cdots,z_k)=0\big]\leq \dfrac d{|S|}\).

Let \(F\) be the field corresponding to residues modulo \(Q\). For \(L\leq n_1+n_2\), \(\sum\limits_i f_{0,i,L}\) and \(\sum\limits_i f_{1,i,L}\) correspond to \(L\)-degree multivariate polynomials over \(F\) in variables \(\{x_{*,*}\}\), denote them \(P_0,P_1\).

If two different string multisets have same hash, two possibilities:

1. \(P_0\equiv P_1\pmod {Q}\), i.e., every coefficient of \(P_0,P_1\) matches modulo \(Q\).
2. \(P_0\not\equiv P_1\pmod {Q}, P_0(x_{*,*})\equiv P_1(x_{*,*})\pmod {Q}\), i.e., \(P_0,P_1\) are not identical, but our chosen \(\{x_{*,*}\}\) makes them equal at this point.

Analyze probability of first case:

• Observation: For any \(A\neq B; A,B\leq N\) and random prime \(Q\leq Q_{\max}\):

\[ \mathrm{Pr}\big[A\equiv B\pmod {Q}\big]=O\Big(\dfrac{\log N \log Q_{max}}{Q_{max}}\Big) \]

• Reason: \(Q\) satisfying \(A\equiv B\) must divide \(A-B\), there are \(\omega(A-B)\leq \log_2 N\) such \(Q\); by prime number theorem, there are \(\Theta\Big(\dfrac {Q_{\max}}{\log Q_{\max}}\Big)\) distinct primes \(\leq Q_{\max}\). Divide to get above.
• In this observation, take \(A,B\) (with \(A\neq B\)) as coefficients of a specific term in \(P_0,P_1\) (equal to occurrence count of corresponding string in \(G_0,G_1\)). Then \(A,B\leq (m_1+m_2)^{L}\), yielding:

\[ \mathrm{Pr}\big[A\equiv B\pmod {Q}\big]=O\Big(\dfrac{L\log (m_1+m_2) \log Q_{max}}{Q_{max}}\Big) \]

• So \(Q_{\max}\approx 10^{12}\) suffices. If machine cannot handle such large integers, use double hashing.

Analyze probability of second case:

• In Schwartz–Zippel lemma:
  • Take field \(F\) as residue field modulo \(Q\).
  • Take \(f(x_{*,*})=P_0(x_{*,*})-P_1(x_{*,*})\) as non-zero degree-\(L\) polynomial.
  • Take \(S=F\).
• Get: probability \(\leq \dfrac LQ\).

Since we need correctness for each \(L\), rigorous proof requires Union Bound (see later).

In practice, we don't need random modulus; e.g., using birthday as modulus is effectively random.

Example: (*) Number of Distinct Elements in Submatrix

Problem

Given \(n\times m\) matrix, \(q\) queries asking number of distinct elements in a contiguous submatrix, requiring online algorithm.

Allow \(\epsilon\) relative error and \(\delta\) error rate, i.e., answer at least \((1-\delta)q\) queries with relative error \(\leq \epsilon\).

\(n\cdot m\leq 2\cdot10^5;q\leq 10^6;\epsilon=0.5,\delta=0.2\)

Lemma: Let \(X_{1\cdots k}\) be independent random variables uniformly distributed in \([0,1]\). Then \(\mathrm{E}\big[\min\limits_i X_i\big]=\dfrac 1{k+1}\).

• Proof: Consider a unit circle with \(k+1\) points uniformly randomly placed at positions \(0,X_1,X_2,\cdots,X_k\). Then \(\min\limits_i X_i\) equals length of a specific gap among \(k+1\) gaps. By symmetry, expected length of any specific gap is \(\dfrac 1{k+1}\).

Take \(k\) as number of distinct elements, use lemma to infer \(k\) from \(\min\limits_i X_i\).

Consider a hash function mapping each matrix element uniformly and independently to a real in \([0,1]\), with equal elements mapping to same real. Then the reals corresponding to elements of a submatrix, after deduplication, form an instance of \(\{X_1,\cdots,X_k\}\), where \(k\) is number of distinct elements in submatrix.

Algorithm:

1. Assign each matrix element a hash value in \([0,1]\). For randomness, hash function can be implemented via map and random generator: assign random hash to each new distinct value.
2. Answer query by computing minimum hash value \(M\) in submatrix, output \(\dfrac 1M-1\).

However, this algorithm is unsatisfactory. Its output expectation is \(\mathrm{E}\Big[\dfrac 1{\min\limits_i X_i}-1\Big]\), which actually equals \(\infty\), not \(\dfrac 1{\mathrm{E}\big[\min\limits_i X_i\big]}-1=k\).

We cannot put single \(\min\limits_i X_i\) in denominator; compute its expectation first.

How to compute expectation? Average over multiple random trials.

Use \(C\) different hash functions, compute \(C\) different \(M\) values per query, average to \(\overline M\), output \(\big(\overline M\big)^{-1}-1\).

Experiments show \(C\approx 80\) suffices. Rigorous proof omitted.

Finally, how to compute submatrix minimum? Use 2D Sparse Table, preprocessing \(O(nm\log n\log m)\), query \(O(1)\).

Other Applications of Randomization in Algorithms

Other roles of randomization include:

• Preventing adversarial data. E.g., randomizing neighbor order in search.
• Ensuring operations during algorithm are (in some sense) uniform. E.g., Simulated Annealing.

In these scenarios, randomization often (but not always) relates to heuristic or cheating approaches.

Example: 「TJOI2015」Linear Algebra

Standard solution is network flow, but here we use heuristic:

• Randomly flip a position each time, evaluate and update answer.

Code

#include <algorithm>
#include <cstdlib>
#include <iostream>

int n;

int a[510], b[510], c[510][510], d[510];
int p[510], q[510];

int maxans = 0;

void check() {
  memset(d, 0, sizeof d);
  int nowans = 0;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) d[i] += a[j] * c[i][j];
  for (int i = 1; i <= n; i++) nowans += (d[i] - b[i]) * a[i];
  maxans = std::max(maxans, nowans);
}

int main() {
  srand(19260817);
  std::cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) std::cin >> c[i][j];
  for (int i = 1; i <= n; i++) std::cin >> b[i];
  for (int i = 1; i <= n; i++) a[i] = 1;
  check();
  for (int T = 1000; T; T--) {
    int tmp = rand() % n + 1;
    a[tmp] ^= 1;
    check();
  }
  std::cout << maxans << '\n';
}

Example: (*) Randomized Heap²

The most common mergeable heap is leftist tree, maintaining tree height to ensure merge complexity. Maintaining height is troublesome; we want to avoid.

Consider randomized heap: swap children randomly instead of by height.

Code

struct Node {
  int child[2];
  long long val;
} nd[100010];

int root[100010];

int merge(int u, int v) {
  if (!(u && v)) return u | v;
  int x = rand() & 1, p = nd[u].val > nd[v].val ? u : v;
  nd[p].child[x] = merge(nd[p].child[x], u + v - p);
  return p;
}

void pop(int &now) { now = merge(nd[now].child[0], nd[now].child[1]); }

Randomized heap imposes no hard/soft requirements on heap shape. Expected merge complexity holds for any two heaps (as merge arguments). Proof below.

Proof of Expected Complexity

Claim: For any heap \(A\), starting from root and randomly choosing left or right until no path (i.e., leaf), expected path length (number of nodes) \(h(A)\leq\log_2 (|A|+1)\).

• Note expected merge complexity for heaps \(A,B\) is \(O\big(h(A)+h(B)\big)\), so above ensures randomized heap's expected complexity.

Proof by induction. Base case \(A\) empty, trivial. Assume \(A\) non-empty.

Let \(L,R\) be \(A\)'s subtrees:

\[ \begin{align} h(A) &=1+\frac{h(L)+h(R)}2 \\&\leq1+\frac{\log_2(|L|+1)+\log_2(|R|+1)}2 \\&=\log_2{2\sqrt{(|L|+1)(|R|+1)}} \\&\leq\log_2{\frac{2\big((|L|+1)+(|R|+1)\big)}2} \\&=\log_2{(|A|+1)} \end{align} \]

QED.

Proof Techniques Related to Randomness

Listed below are some useful techniques.

Naturally, these few cannot be exhaustive; if you know an unlisted technique, contributions are welcome.

Probability Upper Bound Analysis

See Probability Inequalities.

Besides inequalities mentioned there, derivations often use:

Use of natural constant: \(\Big(1-\dfrac{1}{n}\Big)^n\leq \dfrac{1}{\mathrm{e}},\forall n\geq1\)

• Left side increases with \(n\geq 1\) and limit at \(+\infty\) is \(\dfrac{1}{\mathrm{e}}\), hence the conclusion.
• This tells: If \(n\) independent events each occur with probability \(1-\dfrac 1n\), probability all occur is at most \(\dfrac{1}{\mathrm{e}}\).

"Coupling" Idea

"Coupling" is often used when handling multiple random objects simultaneously, or handling random and deterministic objects together.

Warm-up: Connectivity of Random Graphs

Problem

For \(n \in \mathbf{N}^*; p,q\in [0,1]\) with \(q\leq p\), prove: Expected number of connected components in random graph \(G_1(n,p)\) is at most that in \(G_2(n,q)\). Here \(G(n,\alpha)\) denotes simple undirected graph \(G\) on \(n\) vertices where each of \(\dfrac {n(n-1)}2\) possible edges appears with probability \(\alpha\), independently.

This seems natural but rigorous proof is nontrivial.

Proof Sketch

Imagine both graphs use a 01 random generator to determine edge existence: \(G_1\)'s generator \(T_1\) outputs 1 with probability \(p\), \(G_2\)'s \(T_2\) outputs 1 with probability \(q\). To construct a graph, run corresponding generator \(\dfrac {n(n-1)}2\) times.

Now combine generators. Consider generator \(T\): outputs 0 with probability \(q\), 1 with probability \(p-q\), 2 with probability \(1-p\). Running \(T\) \(\dfrac {n(n-1)}2\) times constructs both \(G_1\) and \(G_2\). Specifically: if output 0, neither graph has current edge; if 1, only \(G_1\) has it; if 2, both have it.

Easy to verify generated \(G_1,G_2\) satisfy definitions, and in each instance, \(G_2\)'s edge set is subset of \(G_1\)'s. Thus in each instance, \(G_2\)'s number of connected components \(\geq\) \(G_1\)'s; same for expectations.

This proof uses "coupling," literally combining two independent random processes into one.

Application: NERC 2019 Problem G: Game Relics

Brief Description

There are several items, each with price \(c_i\). You want all items. You can perform two operations arbitrarily:

1. Choose an unowned item \(i\), pay \(c_i\) to buy it.
2. Pay \(x\) to randomly draw one item from all items (including owned). If not owned, obtain it; otherwise get nothing but refund \(\dfrac x2\). \(x\) is input constant.

Find expected cost under optimal strategy.

Observation: If choose to draw, keep drawing until obtaining new item.

• Reason: If draw yields no new item, new situation identical to before drawing. If optimal action before was "draw once," optimal action now is "draw again."

Compute \(f_k\): expected cost to draw a new item given currently owning \(k\) distinct items. By observation, treat \(f_k\) as fixed cost: "pay \(f_k\) to randomly get a new item."

Expected Cost Calculation

Clearly \(f_k=\dfrac x2 \cdot (R-1)+x\), where \(R\) is expected draws to get new item.

Lemma: If coin shows heads with probability \(p\), expected draws until first head is \(\dfrac 1p\).

• Intuition: \(\dfrac 1p \cdot p = 1\), so expected number of heads after that many draws is 1.
• Can be formalized via Law of Large Numbers, considering \(n\to \infty\) experiments of "toss until head." Details omitted.
• Alternative: brute-force using expectation definition. Details omitted.

Probability to draw new item is \(\dfrac {n-k}n\), so \(R=\dfrac n{n-k}\).

Conclusion: Optimal strategy is to draw some times, then buy all remaining items.

This matches intuition because \(f_k\) increases with \(k\), so drawing early seems better.

Proof

First prove a special case:

• Process \(A\): Buy item \(x\), then draw until all items obtained.
• ... is no better than ...
• Process \(B\): Draw until all items except \(x\) obtained, then buy \(x\) if not owned.

Let \(A\) and \(B\) share same random generator. I.e., \(A\)'s first draw and \(B\)'s first draw yield same element, same for second, third...

Clearly, \(A\) and \(B\) have same number of draws. For item \(y\neq x\) drawn by \(A\):

• Number of owned items when \(A\) draws \(y\) \(\geq\) number when \(B\) draws \(y\).

Thus \(B\)'s per-draw cost \(\leq\) \(A\)'s, so total draw cost \(\leq\) \(A\)'s.

Clearly \(B\)'s purchase cost \(\leq\) \(A\)'s. So \(B\) no worse than \(A\).

Generalize via induction: find last purchase in current strategy, move it to end without worsening. Details omitted.

Based on conclusion, equivalently transform problem: change "choose an item and pay price" to "randomly choose an unowned item and pay price." Equivalence because purchase only for cleanup, choice irrelevant.

Now "draw" and "buy" become same operation, differing only in cost. Choice doesn't affect order of obtaining items, each order equally likely.

Observation: At any moment, should buy iff next draw cost (determined by number of owned items) > average price of remaining items (if equal, arbitrary).

• Can prove draw cost increases at least as fast as average remaining price. So only one "critical point" from draw to buy, further verifying earlier conclusion.

Finally, enumerate all possible states (set of owned items), compute probability (arrangements of owned items divided by total arrangements), multiply by optimal cost for state (determined by number owned and total remaining price), sum. This can be optimized via knapsack-like DP, passes problem.

---

Review: Coupling used twice here. First in proof, letting two processes share random source; second in transforming purchase to random purchase (introducing random source), making draw and purchase essentially "coupled" as same operation.

References

---

1. UOJ NOI Round #4 Day2 Editorial ↩

2. Anna Gambin and Adam Malinowski, Randomized Meldable Priority Queues ↩

3. PANIC - Editorial ↩

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用