Randomness

Sometimes, we can use randomized algorithms to solve tasks quite difficult for deterministic algorithms.

Example - Ghd

Let the answer be $k$. The key observation for this problem is that a randomly selected integer in $a$ has at least a $\frac{1}{2}$ chance to be divisible by $k$.

Thus, we can repeat the following procedure $S$ times to find the optimal answer with probability $1-\frac{1}{2^S}$:

• Let $x$ be a randomly selected value in $a$.
• For each divisor $d \mid x$, determine how many numbers $d$ divides into in $a$.
• Take our answer to be the minimum of all $d$ such that $\geq \frac{n}{2}$ numbers in $a$ are divisible by $d$

If we take $S = 15$, and estimate the number of testcases in Codeforces to be $500$, our probability of success is $(1-\frac{1}{2^{15}})^{500} \approx .984$, which is acceptable.

Implementation

Our approach has a time complexity of $\mathcal{O}\left(S \cdot \left(N\log A + d(A)^2 + \sqrt{A}\right)\right)$ , with the log factor occurring due to GCD computation, and the sqrt due to factoring.

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e6 + 5;
const int S = 15;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
long long a[MAX_N], dv[MAX_N], cnt[MAX_N];

int main() {

Example - Count on a Tree II Striking Back

Trying to solve this problem directly - explicitly finding values for $f(a,b)$ and $f(c,d)$ - is quite difficult. Supporting online queries of range count distinct along with updates is quite difficult to achieve on an array in reasonable complexity, and the fact that this problem occurs on a tree, with relative large bound for $n \leq 500$ $000$ makes it clear that solving for the value of $f$ is not intended.

Instead, we can attempt to use the property given in the statement that either $f(a,b) \geq 2f(c,d)$ or $f(c,d) \geq 2f(a,b)$. This inspires the following thought - if we map each color to a random number, the path minimum along the path with more distinct colors will probably be a smaller value.

We attempt to formalize this approach, and push the probability to an acceptable bound. Notably, the probability of failure is too high when we do the aforementioned random process once. To remedy this, we proceed as follows:

• First we fix $S$ to be the number of "simulations" that we run.
• Next, for each possible color $1 \leq c \leq n$, we define $v_{cj}$ as an independent random value within $[0,1]$, for each $1 \leq j \leq S$.
• Then, we construct $S$ trees $T_i$, of the same structure as the initial tree, but with $v_{c_u i}$ marked on a node $u$.
• For each query comparing $a,b,c,d$, we output $\texttt{Yes}$ if

and $\texttt{No}$ otherwise.

This approach should "combine" the probabilities in a way that makes the more likely event (the path with more distinct values achieving a smaller value) exponentially more likely. For some intuition on this, if we flip a coin weighted with $\frac{2}{3}$ probability to be heads once, there is a $\frac{1}{3}$ probability it comes up tails more than heads. However, if we flip it $99$ times, the probability it comes up more tails more than heads becomes

Calculating the exact probability that our approach works is more difficult than the coin toss example, but follows the same principle of failure becoming exponentially more unlikely across several trials. We can use some assumptions (notably the central limit theorem) to calculate a rough approximation of the probability of success. Here is a graph of the probability of passing the problem given a certain value of $S$. Note that the probability of success remains is largely the same across different counts of distinct colors along the path.

The graph was generated for the probability of answering $4\cdot10^4$ queries correctly in a row. This assumption is reasonable because the test data consists of only 1 large test case.

The python code used to generate the estimates is shown below:

Copy
import math
from scipy.stats import norm


def clt_probability(k, S):
	"""
	Computes the probability that the sum of S minima from 2k random draws
	is less than the sum of S minima from k random draws, as approximated by the CLT.

	The CLT approximation is given by:

Implementation

By supporting path queries with HLD, we can solve this problem in $\mathcal{O}(S\cdot(n + m\log^2n))$.

Copy
#include "bits/stdc++.h"
using namespace std;

using us = unsigned short;

const int MAX_N = 5e5 + 1;
const int S = 150;
const us INF = 65535;

us va[MAX_N][S];

Problems

Some of the listed problems do not require random algorithms as a solution, but can be made significantly easier through using random algorithms.