mango_lassi's blog

By mango_lassi, 5 months ago, In English

Boring backstory of this blog

In 300IQ contest 3, there was a problem where you had to count the number of permutations with two disjoint longest increasing subsequences. We VCd this contest while practising for ICPC, and didn't solve this problem during the contest, so I was very interested to see how it could be solved. Turns out the solution uses something called Young diagrams, and unless you already know what they are, the editorial is impossible to understand.

I asked if someone knew about Young diagrams on the competitive programming discord, and got linked a paper from the Chinese IOI selection camp, written by yfzcsc. If you can speak chinese, you should just read the paper, it covers a lot more than I do here. With the help of my teammate YaoBIG I believe I understand enough to write a English-language blog on this topic for the rest of us :)

Definitions

We call a sequence $$$\lambda$$$ of positive integers a partition of $$$n$$$, if $$$\lambda_i \geq \lambda_{i + 1}$$$ and $$$\sum_{i = 1}^{|\lambda|} \lambda_i = n$$$. We denote by $$$P_n$$$ the set of partitions of $$$n$$$.

For a partition $$$\lambda$$$, we define the Young diagram $$$Y(\lambda)$$$ as the set of pairs $$$(i, j)$$$ of positive integers such that $$$i \leq |\lambda|$$$ and $$$j \leq \lambda_i$$$. We call the pairs $$$s = (i, j) \in Y(\lambda)$$$ the squares of the diagram.

A normalised Young Tableau $$$P$$$ of size $$$n$$$ is a pair $$$(\lambda, p)$$$ of a partition $$$\lambda$$$ of $$$n$$$, and a permutation $$$p$$$ indexed by $$$Y(\lambda)$$$, such that $$$p_{i, j} < min(p_{i + 1, j}, p_{i, j + 1})$$$.

We use natural definitions of a transpose: we denote by $$$\lambda^T$$$ the transpose partition, that is $$$\lambda^T_j = |\{i : \lambda_i \geq j\}|$$$, let $$$Y^T(\lambda) = Y(\lambda^T)$$$, and define the transpose $$$P^T = (\lambda^T, p^T)$$$ of a normalised Young diagram such that $$$p_{i, j} = p^T_{j, i}$$$.

What is a Young tableau and why are they interesting

Why is it interesting to define Young tableaus? It turns out that there is a one-to-one mapping $$$f$$$ from permutations $$$\pi$$$ of length $$$n$$$ to pairs $$$(P, Q) = ((\lambda, p), (\lambda, q))$$$ of standard Young tableaus of size $$$n$$$ that share the same partition. The mapping has the following properties:

  1. $$$\sum_{i \leq m} \lambda_i$$$ is the maximum total size of $$$m$$$ disjoint increasing subsequences of the permutation
  2. $$$\sum_{j \leq m} \lambda_j^T$$$ is the maximum total size of $$$m$$$ disjoint decreasing subsequences of the permutation
  3. If $$$\pi^{-1}$$$ is the inverse permutation, then $$$f(\pi^{-1}) = (Q, P)$$$
  4. If $$$rev(\pi)$$$ is the reversed permutation, then $$$f(rev(\pi)) = (P^T, ??)$$$ (actually, the second component is the normalised result of applying the Schutzenberger algorithm to $$$Q$$$, but we don't care about that)
  5. The mapping can be computed in $$$\mathcal{O}(n \sqrt{n} \log n)$$$ time. The inverse can be computed in $$$\mathcal{O}(n^2)$$$ time

If $$$c(s)$$$ is the number of valid $$$p$$$ for the partition $$$s$$$, the existence of the mapping shows that $$$n! = \sum_{s \in P_n} c(s)^2$$$. By property 3, the number of permutations $$$\pi$$$ such that $$$\pi = \pi^{-1}$$$ is $$$\sum_{s \in P_n} c(s)$$$. The value we want to compute in the problem presented at the start of the blog is $$$\sum_{s \in P_n : s_1 = s_2} c(s)^2$$$.

The number of partitions of $$$75$$$ is small, so we can loop over all of them. It remains to compute $$$c(s)$$$ fast. For this, we can use the hook-length formula, which we can compute in $$$\mathcal{O}(n)$$$ time.

The mapping: Robinson–Schensted–Knuth correspondence

The name is fancy, but the mapping isn't hard (though proofs of its properties are).

Let's first describe how the first tableau $$$P$$$ is computed. We loop over the rows from first to last, and in each row, find the first element that is larger than the value we are inserting. If we found such a value, we swap it with the value we are inserting and proceed to the next row. Otherwise, we add the value we are inserting to the end of the row and are done.

In every step, the length of exactly one row of the tableau $$$P$$$ increases by $$$1$$$. In step $$$i$$$, we insert $$$i$$$ to tableau $$$Q$$$ at the end of the row whose size increased in the first tableau. This way, both tableaus always have the same shape. By a trivial induction proof, the values in the cells of every row and column in both tableaus are strictly increasing. Thus, the mapping is a injection.

The naive way to perform the insertion takes $$$\mathcal{O}(n)$$$ time, thus we can compute the mapping in $$$\mathcal{O}(n^2)$$$ time.

To compute the inverse, we undo the insertions one by one, starting from the last. Let $$$i$$$ be the row s.t. $$$q_{i, s_i} = n$$$. This is the row whose size increased by $$$1$$$ in the insertion of the last value. Let $$$v \leftarrow p_{i, s_i}$$$, then delete cell $$$(i, s_i)$$$ from both tableaus.

Now, if $$$i = 1$$$, we have $$$\pi_n = v$$$ and can recurse to find the rest of $$$\pi$$$. Otherwise, the reason $$$v$$$ entered row $$$i$$$ was because some smaller value replaced it on row $$$i - 1$$$. This value is the largest value smaller than it. Swap that value with $$$v$$$ and subtract $$$1$$$ from $$$i$$$.

O(n^2) code for the mapping and its inverse

For the faster algorithm for computing the mapping, note that computing just the first $$$\lceil \sqrt{n} \rceil$$$ rows of $$$P$$$ can be done in $$$\mathcal{O}(n \sqrt{n} \log n)$$$ time. Using property $$$4$$$, we can compute the first $$$\lceil \sqrt{n} \rceil$$$ columns of $$$P$$$ in the same time. Since there cannot be more than $$$\lceil \sqrt{n} \rceil$$$ rows with at least $$$\lceil \sqrt{n} \rceil$$$ cells, this way we find the entire tableau in $$$\mathcal{O}(n \sqrt{n} \log n)$$$ time. To find $$$Q$$$, we use property $$$3$$$ and then repeat the above.

I am not aware of any way to calculate the inverse mapping in $$$\mathcal{O}(n \sqrt{n} \log n)$$$ time.

O(n sqrt(n) log(n)) code for the mapping

Unfortunately, the proofs for properties $$$1$$$ to $$$4$$$ are long, involved and very hard to understand (at least for my counting-challenged brain), so I won't put them here. The proof for properties $$$1$$$ and $$$2$$$ for $$$m > 1$$$ is due to Greene. Properties $$$3$$$ and $$$4$$$ appear as theorems 3.2.1 and 4.1.1 here.

Hook-Length Formula

For $$$\lambda \in P_n$$$ and $$$(i, j) \in Y(\lambda)$$$, we define $$$h_{\lambda}(i, j)$$$ as the number of squares in the diagram directly below or to the right of square $$$(i, j)$$$. Formally written, $$$h_{\lambda}(i, j) = (\lambda^T_j - i) + (\lambda_i - j) + 1$$$. The hook-length theorem states that $$$t(\lambda) = c(\lambda)$$$ for

\begin{equation} t(\lambda) = \frac{n!}{\prod_{(i, j) \in Y(\lambda)} h_\lambda(i, j)} \end{equation}

Computing $$$t(\lambda)$$$ is indeed easy to implement in $$$\mathcal{O}(n)$$$ time, and unlike many other results stated in this blog, the hook-length formula's proof is not hard and very beautiful. The below proof is from here.

Code for the hook-length formula
Proof of the hook-length formula

The above proof for the hook-length formula also gives an unbiased sampler for $$$p$$$ given $$$\lambda$$$, though I doubt that will ever be useful in competitive programming.

Problems

300IQ contest 3 problem D

GP of southeastern europe 2021 problem D

If you know any more problems where this technique can be applied, please share a link with me. In particular, there probably exists a problem where you have to find for every $$$m$$$ the maximum total size of $$$m$$$ disjoint increasing subsequences.

 
 
 
 
  • Vote: I like it
  • +144
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Not a competitive programming problem, but USAMO 2016 Problem 2 can be solved using the hook-length formula.

Unrelated backstory: there was quite a heated debate about how this problem should be graded if someone just quoted the formula directly, since the solution using it was pretty much a one-liner.

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

There're several on Project Euler.