The set only needs to contain elements from the range $$$0, \ldots, n$$$. We maintain an array telling us whether each element is in the set. Now, we divide the array into blocks of length $$$\sqrt n$$$. For each block, we maintain the number of elements present in the set in this block. Inserting and deleting an element can be done in $$$O(1)$$$ time — update the array and the block. To find the minimum element, we iterate over the blocks to find the first one that isn't empty, then iterate over the elements of that block to find the minimum one that's present. The time complexity of doing that in $$$O(\sqrt n)$$$.

This problem is from Baltic Olympiad in Informatics 2021, practice round. Link to the problem.

You are given a dictionary of $$$m$$$ different words over an alphabet of $$$n$$$ letters. You want to color the letters in two colors such that in every word the letters alternate between the colors (the problem statement mentions building an ergonomic keyboard with a "left" half and a "right" half). Minimize the difference between the number of red letters and the number of blue letters.

The idea is to view the whole thing as a bipartite graph. The input generates some number of connected components and we can "flip" some of the components to make the sides as equal as possible. Initially, flip all the components so that the left side is smaller. Now we have to flip some components again: for the $$$i$$$-th component, flipping it would increase the size of the left half by some $$$a_i$$$, and we have to choose some of the components to flip such that their sum is as close to a certain integer as possible. Since $$$\sum a_i \le n$$$, we can use this trick to solve the problem in time $$$O(n \sqrt n)$$$.

I believe that to get full points, you have to combine this with bitsets.

Take out the distinct values, sort them, let them be $$$b_0, b_1, \ldots, b_{k - 1}$$$. Because the values $$$b_i$$$ are nonnegative sorted integers, we must have $$$b_i \ge i$$$. Therefore

On the other hand, $$$b_0 + b_1 + \cdots + b_{k - 1} \le m$$$, so we obtain $$$\frac{k(k - 1)}{2} \le m$$$. Now it is easy to see that $$$k$$$ is $$$O(\sqrt{m})$$$.

Let's draw a bar chart: a bar with height $$$\frac11$$$ on the interval $$$[0, 1)$$$, a bar with height $$$\frac12$$$ on the interval $$$[1, 2)$$$, a bar with height $$$\frac13$$$ on the interval $$$[2, 3)$$$ and so on. Fix $$$n$$$, clearly the area of the first $$$n$$$ bars is exactly $$$H_n$$$. The bar chart is the green area in the graph.

On the image, the area under the red curve (the function $$$f(x) = \min\left(1, \frac1x\right)$$$) entirely covers the bar chart, so we must have

On the other hand, the bar chart completely covers the area under the blue curve (the function $$$g(x) = \frac1{x + 1}$$$), so we must have

In total

so indeed $$$H_n = \Theta(\log n)$$$.

This problem is from Codeforces round #757. Link to the problem: 1614D1 - Divan and Kostomuksha (easy version), we are only solving the easy version here.

Given an array $$$A$$$ consisting of positive integers, you want to reorder its elements such that the following value is maximized:

Lets think about the sequence formed by $$$\gcd(A[1], \ldots, A[i])$$$. It is a decreasing sequence of numbers, with each element being a divisor of the previous one. Define $$$\mathrm{dp}[k]$$$ as the maximum sum of a prefix whose gcd is $$$k$$$. To calculate it, we should start the prefix with the optimal prefix for some multiple of $$$k$$$ and then add append all remaining elements that are multiples of $$$k$$$. We are left with an algorithm that looks roughly like this:

1 for k in 1..MAX_A:
2     # cnt_multiples[k] is the number of multiples of k in the array
3     # it is possible that there is no larger multiple of k to be the previous gcd
4     dp[k] = k * cnt_multiples[k]
5     for (j = 2 * k; j <= MAX_A; j += k):
6         # we subtract k * cnt_multiples[j] because these elements already have larger 
7         # contribution to the gcd sum.
8         dp[k] = max(dp[k], dp[j] + k * cnt_multiples[k] - k * cnt_multiples[j])  

The algorithm has exactly the form as seen above, thus its complexity is $$$O(C \log C)$$$, where $$$C$$$ is the maximum value in the array $$$A$$$.

By induction. Let $$$u$$$ be a vertex with $$$m_u$$$ descendants. Let $$$v_1, \ldots, v_k$$$ be the children of $$$u$$$, with $$$m_{v_1}, \ldots, m_{v_k}$$$ descendants respectively. Assume that for each $$$i$$$, in a call to calc_dp(v_i) there are no more than $$$m_{v_i}^2$$$ hits to line 8 (including the recursive hits). We will prove that if calc_dp(u) is called, line 8 will be hit no more than $$$m_u^2$$$ times.

The number of times line 8 will be hit is no more than

The first sum comes from the recursive calls (by the induction hypothesis), the second is just directly translated from lines 4 to 7. Now notice that

We now apply this result to the root, which of course has $$$n$$$ descendants, therefore the total complexity comes to $$$O(n^2)$$$.

Consider the algorithm for a fixed $$$u$$$. For each child $$$v$$$ of $$$u$$$, we associate every position in the array $$$\mathrm{dp}[v]$$$ with a descendant of $$$v$$$. The array $$$\mathrm{dp}[v]$$$ is no longer than the number of descendants of $$$v$$$, so we can make sure no two elements in the subtree are associated with the same elements in the array.

Now, we iterate over all pairs $$$\left< v, i \right>$$$ and $$$\left< w, j \right>$$$, where $$$v$$$ and $$$w$$$ are different children of $$$u$$$. Instead of iterating over all pairs, let's think about iterating over the corresponding vertices $$$a$$$ and $$$b$$$. For a fixed $$$u$$$, we never visit the same pair of vertices twice. But in fact, the lowest common ancestor of $$$a$$$ and $$$b$$$ must be $$$u$$$, because $$$v$$$ and $$$w$$$ are different children of $$$u$$$. So in fact, we never visit the same pair of vertices during the course of the whole algorithm!

The number of times line 8 is hit must therefore be no larger than the number of different pairs of vertices in the tree, which is of course $$$O(n^2)$$$.

This problem is from ICPC Manila 2019 and also Codeforces round #607. Link to the problem: 1280D - Miss Punyverse.

You are given a tree on $$$n$$$ nodes; every node has an integer written on it. You want to partition the tree into $$$m$$$ connected regions such that the number of regions with a positive sum is maximized. $$$m \le n \le 3000$$$.

For any $$$u$$$, let $$$\mathrm{dp}[u][k]$$$ be the maximum pair $$$\left< t, s \right>$$$, such that

• the subtree of $$$u$$$ is partitioned into $$$k$$$ regions;
• the number of positive regions among them is $$$t$$$;
• the sum of the region $$$u$$$ is located in — the one we can possibly enlarge — is $$$s$$$.

An exercise to the reader: why is it sufficient to consider the maximum pair $$$\left< t, s \right>$$$?

The transitions to this DP can be calculated in a way similar as discussed above. For a given $$$u$$$, we start "building" the array $$$\mathrm{dp}[u]$$$ by iteratively considering new children of $$$u$$$ and "merging" them into the array $$$\mathrm{dp}[u]$$$. For each child $$$v$$$, we consider all pairs $$$\mathrm{dp}[u][i]$$$ and $$$\mathrm{dp}[v][j]$$$, and we put the calculated result into $$$\mathrm{dp}[u][i + j]$$$. With ideas similar as above, we can show that this has the complexity $$$O(n^2)$$$ as well.

This problem is from Topcoder Open 2020 Round 1B. Link to the problem. I chose an example from Topcoder because it is very common to see this idea there.

A prime is called different if all of its digits are different. Given an integer $$$n$$$, find the different prime closest to $$$n$$$. We have $$$1 \le n \le 5 \cdot 10^7$$$.

The solution is to simply iterate over numbers slightly below and above $$$n$$$ and check if they are prime. There is really no need to do anything cleverer here. Prime numbers are plentiful, so you will reach your target very quickly: it is probably even fast enough to check whether a number is prime completely naively by trial division.

This problem is from Moscow Workshops Discover Riga/Singapore 2019, 300iq contest. I don't know if you can submit it anywhere.

Given a prime $$$p$$$. For any $$$x$$$, we can decompose it as follows: $$$x \equiv a^2 + b^2 \pmod{p}$$$ for some $$$a, b$$$. This is always possible, but we are interested in the "best" way — the one with the smallest $$$a$$$. Let $$$f(x)$$$ be the smallest $$$a$$$ such that this is possible. You want to find the maximum of $$$f(0), f(1), \ldots, f(p - 1)$$$. $$$p \le 10^5$$$.

Consider a fixed $$$x$$$. How to check if a particular $$$a$$$ is suitable? A simple rearrangement gives $$$x - a^2 \equiv b^2 \pmod{p}$$$, so all we need to do is check if $$$x - a^2$$$ is a quadratic residue. This can be done by precomputing all quadratic residues modulo $$$p$$$.

The completely naive solution then would be to iterate over all $$$a$$$, starting from 0, and stopping once we find an $$$a$$$ such that $$$x - a^2$$$ is a quadratic residue. And that turns out to be good enough because at every step we have $$$\frac{1}{2}$$$ probability of encountering a quadratic residue. Repeat this for each $$$x$$$ and you have an unproven expected $$$O(n)$$$ complexity.

1111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111
1111888888888888881111888888888888881111888888888888881111
1111888888888888881111888888888888881111888888888888881111
1111888811111111111111888811111111111111111118888111111111
1111888811111111111111888811111111111111111118888111111111
1111888888888881111111888888888881111111111118888111111111
1111888888888881111111888888888881111111111118888111111111
1111888811111111111111888811111111111111111118888111111111
1111888811111111111111888811111111111111111118888111111111
1111888811111111211111888811111111111111111118888111111111
1111888811111111111111888811111111111111111118888111111111
1111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111           

Pick some $$$v_i$$$ and $$$v_j$$$ and assume $$$i < j$$$. Let $$$\mathrm{lca}(v_i, v_j) = u$$$. If $$$u = v_i$$$, then we can use $$$v_i$$$ and the first descendant of $$$v_i$$$ that appears in the subset; they must be adjacent. Otherwise, let $$$w$$$ be the child of $$$u$$$ whose subtree contains $$$v_i$$$. Because the vertices are in the DFS order, the vertices in the subtree of $$$u$$$ must form a contiguous range among $$$v_1, \ldots, v_m$$$. Similarly, the vertices in the subtree of $$$w$$$ must form a contiguous range, contained in the range for $$$u$$$. We can use the last vertex in the subtree of $$$w$$$ and the first vertex in the $$$u$$$-range that is not contained in $$$w$$$. Neither of them is an empty set, because they contain $$$v_i$$$ and $$$v_j$$$ respectively.

This fact is useful for calculating the so-called "virtual trees". In some problem, such as 613D - Kingdom and its Cities, you are given many queries, each query consists of a subset of vertices. To answer these queries, it is not necessary to consider the whole tree. It is sufficient to consider the given subset of vertices, as well as some additional vertices where paths from the given vertices to one another "join up". They form a smaller tree with much fewer vertices, called the virtual tree:

In this picture, the given subset of vertices is in dark red. To join them up while preserving the structure (it's hard to formally explain what the actual requirement is, but hopefully the idea is clear) we need to add the pink vertices. The dark red and pink vertices together form the vertices of the virtual tree. The edges of the virtual tree are shown in red.

Notice that the vertices making up the virtual tree are exactly those of the form $$$\mathrm{lca}(u, v)$$$, where $$$u$$$ and $$$v$$$ are part of the given subset of vertices. Using the fact that we just learned, we can find the vertices that form the virtual tree by sorting the given subset by DFS order, taking the LCAs of all adjacent pairs of vertices, and removing the duplicates. To find the edges of the virtual tree, you can again sort all the vertices of the virtual tree, and use a stack-like idea to connect them up.

It can be proven directly, but I like to think of it as a special case of Dilworth's theorem.

To formulate it as a case of Dilworth's theorem, we define a partial order: $$$i \preceq j$$$ if and only if $$$i \le j$$$ and $$$p_i \le p_j$$$. An "antichain" is then a decreasing subsequence. A "chain" is an increasing subsequence. Dilworth's theorem states:

Consider splitting the permutation into increasing subsequences. The length of the longest decreasing subsequence is exactly the minimum number of increasing subsequences needed.

Suppose that the length of the longest decreasing subsequence $$$\ell$$$ and $$$\ell < \sqrt{n}$$$. Then we can split the permutation into $$$\ell$$$ increasing subsequences; as the sum of their lengths is $$$n$$$, at least one of them will be at least $$$\sqrt{n}$$$.

This proves that if the longest decreasing subsequence is shorter than $$$\sqrt{n}$$$, then there exists an increasing subsequence with length at least $$$\sqrt{n}$$$. A similar argument shows that if the longest increasing subsequence is shorter than $$$\sqrt{n}$$$, then there exists a decreasing subsequence with length at least $$$\sqrt{n}$$$.

This problem is from Algorithmic Engagements. I know this problem from "best problem in 2019" discussion, I'd be grateful if someone sent a link.

Given $$$n = 3 \cdot 10^5$$$ points on a plane, you get to pick a subset of 500 points and need to solve the Traveling Salesman problem on the chosen subset.

You can use a variant of this idea: we can either find a path with length at least $$$\sqrt{n}$$$, where $$$x$$$ and $$$y$$$ are both increasing; or a path with length at least $$$\sqrt{n}$$$, where $$$x$$$ is increasing and $$$y$$$ is decreasing. Solving the Traveling Salesman problem on such subsets is trivial. $$$500 \le \sqrt{n}$$$, so no worries there.