[CSES](https://cses.fi/) is a well-known resource. It has many problems from a variety of topics. Solutions to almost every problem can be found online. But for some hard problems there are no editorials yet. Getting stuck on these difficult problems can lead to frustration, which is why I decided to write solutions for them.↵
↵
### [Inversion Probability](https://cses.fi/problemset/task/1728)↵
↵
<spoiler summary="Hint 1">↵
The intended solution is not difficult. The tricky part is rounding off the number.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
long double doesn't work. Find out why.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Use long arithmetic.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
For each pair $(i, j)$, the probability of it being an inversion is: ↵
\begin{cases} ↵
\displaystyle \frac{r_i — 1}{2 r_j} & \text{if } r_i \leq r_j, \\ ↵
\displaystyle \frac{2 r_i — r_j — 1}{2 r_i} & \text{if } r_i > r_j.↵
\end{cases}↵
↵
The answer is the sum of probabilities for all pairs. However, rounding the result is nontrivial because the decimal part of the expected value can be extremely close to $0.0000005$. Consider next test case:↵
↵
~~~~~↵
22↵
8 10 12 13 15 18 19 20 21 22 23 26 27 28 29 79 82 86 87 88 91 95↵
~~~~~↵
The exact answer is $53.4183365000000000000943313030608574746003...\dots$ A naive solution gives 53.4183365 due to precision error. So we should use long arithmetic. Let's take the denominator as twice the product of the given numbers. Compute the numerator using basic arithmetic operations. After that we should round off $\frac{\text{numerator}}{\text{denominator}}$. There are many ways to do it. I did it by using large powers of 10. ↵
[Code](https://github.com/ssevR/cses/blob/main/Mathematics/Inversion_Probability/main.py)↵
↵
</spoiler>↵
↵
### [Letter Pair Move Game](https://cses.fi/problemset/task/2427)↵
↵
<spoiler summary="Hint 1">↵
Solve the problem for $n \leq 4$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Did you notice anything when $n = 4$?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
A solution always exists when $n \geq 4$↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
Try to solve the problem for $n > 4$ using heuristic algorithm.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
At the end, you need to apply your solution for n = 4(only a couple of times).↵
</spoiler>↵
↵
<spoiler summary="Similar problem">↵
[IOI1989P1](https://ioinformatics.org/files/ioi1989problem1.pdf)↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
If $n \leq 4$ just brute-force the problem using bfs. ↵
If $n > 4$: ↵
- Let $\text{b\_pos}$ be the index of the leftmost **B** in the current string. ↵
- Let $\text{a\_pos}$ be the index of the leftmost **A** in the substring starting from $\text{b\_pos} + 2$ to $2n$. ↵
- Swap $s[\text{b\_pos}, \text{b\_pos} + 1]$ with $s[\text{a\_pos}, \text{a\_pos} + 1]$ using 3 operations. ↵
↵
If $\text{a\_pos}$ cannot be found, apply $n=4$ solution. Don't forget to handle the edge case when $\text{a_pos} = 2 n$ ↵
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Letter_Pair_Move_Game/main.cpp)↵
</spoiler>↵
↵
### [Removing Digits II](https://cses.fi/problemset/task/2174)↵
↵
<spoiler summary="Hint 1">↵
Choose the largest available digit at each step.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
dp↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Think about powers of 10. ↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
Let's say that you know the answer for $10^i$. How can you find the answer for $10^{i + 1}$? What about $2 \cdot 10^i, 3 \cdot 10^i \dots 9 \cdot 10^i$?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
What additional information should you store to calculate the answer for these numbers?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 6">↵
3d dp↵
</spoiler>↵
↵
<spoiler summary="Original problem">↵
[331C3](https://codeforces.net/contest/331/problem/C3)↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Let's define $\text{pair<long long, int>} \text{dp}[i][j][k]$ where $i < 18, j < 10, k < 10$. ↵
$\text{dp}[i][j][k].\text{first}$ represents the number of operations needed to reduce $10^{i + 1} - j$ to $-\text{dp}[i][j][k].\text{second}$($0 \leq \text{dp}[i][j][k].\text{second} \leq 9$). ↵
$0 \leq k \leq 9$ is the maximum digit allowed in the suffix. ↵
Using this dp we can easily calculate the answer in $\mathcal{O} (\log^2{n})$ ↵
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Removing_Digits_II/main.cpp)↵
</spoiler>↵
↵
### [Counting Reorders](https://cses.fi/problemset/task/2421)↵
↵
<spoiler summary="Hint 1">↵
Solve the problem in $\mathcal{O}(n^3)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Try to optimize solution using inclusion–exclusion principle.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
$\mathcal{O} (|\Sigma| \cdot n^2)$ solution is short and simple, but it's hard to guess it.↵
</spoiler>↵
↵
<spoiler summary="Similar problem">↵
[CSP-J2019](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P5684#author=GPT_en)↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Let us define $\text{cnt}[i]$ as the number of occurrences of the $i$-th character.The DP state $\text{dp}[i][j]$ represents the number of strings that can be formed using the first $i$ characters and partitioned into $j$ blocks (a block is a sequence of consecutive identical characters). Note that a single string may be counted multiple times in this formulation. Compute $\text{dp}[i]$ in $\mathcal{O}(n^2)$ using binomial coefficients. After computing $\text{dp}[|\Sigma|]$ it's possible to find the total number of strings using inclusion-exclusion formula. For implementation details, refer to the provided [code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Counting_Reorders/main.cpp).↵
</spoiler>↵
↵
↵
### [Filling Trominos](https://cses.fi/problemset/task/2423)↵
↵
<spoiler summary="Hint 1">↵
What is necessary requirement?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
$3 \mid n \cdot m$ ↵
Without loss of generality let's assume that $3 \mid n$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Construct a solution if $6 \mid n \cdot m$↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
Consider a case $n = 3$. What can you say about $m$?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
What if $n \cdot m$ is odd, $n \geq 9$ and $m \geq 5$? Does solution exist for this case? Can you prove it?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 6">↵
Try to construct solution for $9 \times 5$↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 7">↵
Use it to construct a solution for the last case.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
It's very clear that $3 \mid n \cdot m$ and $\text{min}(n, m) \geq 2$. Without loss of generality let's assume that $3 \mid n$ (otherwise, transpose the grid). ↵
1. For $n = 3$ and $m \geq 2$, a solution exists if and only if $m$ is even. It can be proved by induction. ↵
2. If $n$ or $m$ is even, use a tiling pattern with $3 \times 2$ or $2 \times 3$ blocks. ↵
3. $n \cdot m$ is odd, $n \geq 9$ $m \geq 5$. There exists a solution for $9 \times 5$. You can construct it on paper or by using profile dp. Now if you put $9 \times 5$ in the upper left corner the grid splits into two rectangles: $(n - 9) \times 5$ and $n \times (m - 5)$. Solve these using construction of previous case. ↵
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Filling_Trominos/main.cpp)↵
</spoiler>↵
↵
### [Functional Graph Distribution](https://cses.fi/problemset/task/2415)↵
↵
<spoiler summary="Hint 1">↵
[Stirling numbers of the first kind](https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind)↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
[Cayley's formula](https://en.wikipedia.org/wiki/Cayley%27s_formula)↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
The problem is [OEIS-able](https://oeis.org/A060281). ↵
The formula is obtained by combining the two given ideas. ↵
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Functional_Graph_Distribution/main.cpp)↵
</spoiler>↵
↵
### [Grid Completion](https://cses.fi/problemset/task/2429)↵
↵
<spoiler summary="Hint 1">↵
Try to think about the problem in terms of graph↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Solve the problem when grid is empty.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Try to get rid of cycles of length 2.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
Use inclusion–exclusion principle.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
For each $i$, find the number of completion with at least $i$ cycles of length 2. ↵
</spoiler>↵
↵
↵
<spoiler summary="Key observation">↵
Consider a component with $>1$ edges. It's impossible to form a cycle of length 2 with vertices of this component.↵
</spoiler>↵
↵
↵
<spoiler summary="Similar problem">↵
[ARC186A](https://atcoder.jp/contests/arc186/tasks/arc186_a)↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
For an $N \times N$ grid $G$, construct a directed bipartite graph with partitions $\{R_1, \dots, R_N\}$ (rows) and $\{C_1, \dots, C_N\}$ (columns): ↵
- If $G[i][j] = A$, direct an edge from $R_i$ to $C_j$. ↵
- If $G[i][j] = B$, direct an edge from $C_j$ to $R_i$. ↵
↵
The goal is to count the number of ways to complete this graph into non-intersecting cycles covering all vertices, with no 2-cycles It's easy to see that such cycles can only be formed from isolated vertices or 1-edge components. The answer can be calculated by inclusion–exclusion principle iterating over the number of 2-length cycles formed by isolated vertices, the number of 1-edge components from left part and 1-edge components from right part. The time complexity is $\mathcal{O}(N^3)$. ↵
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Grid_Completion/main.cpp)↵
</spoiler>↵
↵
### [Two Stacks Sorting](https://cses.fi/problemset/task/2402)↵
↵
↵
<spoiler summary="Hint 1">↵
How long $i$-th number has to be be in stack?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Try to represent the problem in terms of sets of segments(endpoints of segments must be unique).↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
This [problem](https://codeforces.net/edu/course/2/lesson/7/2/practice/contest/289391/problem/I) may be useful.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
Add only essential edges.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
Iterate through the endpoints from left to right↵
</spoiler>↵
↵
↵
<spoiler summary="Similar problems">↵
[1691E](https://codeforces.net/problemset/problem/1691/e) ↵
[JOISC2017B](https://qoj.ac/problem/361)↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
$p_1, \dots, p_n$ is a given permutation. ↵
For each $i$ let's consider $j = \max k \colon p[k]_k \leq p[i]_i $. At the $j$-th iteration we should be able to get $p[i]_i$. Otherwise, solution doesn't exist. Using that observation we can represent the problem in terms of segments with unique endpoints. Let the segment of the $i$-th number be equal to $[l_i, r_i]$. If 2 segments $[l_i, r_i]$ and $[l_j, r_j]$ intersect and neither is contained in the other, we can not move $i$-th and $j$-th numbers to the same stack. In that case, let's add an edge between $i$-th and $j$-th numbervertices. If resulting graph is bipartite, a solution exist. The goal is to find a bipartition of the graph. The main idea is to consider only the necessary edges. Let's store components of the graph in [DSU](https://codeforces.net/edu/course/2/lesson/7/2/practice/contest/289391/problem/I). Every leader of a component has all segments of its elements stored in the set. We can merge 2 sets using small-to-large trick. Overall time complexity is $\mathcal{O}(n \log^2 n)$. Let's iterate through the endpoints from left to right. Assume we are at position $x$. For each component, store the segment $[l_i, r_i]$ such that $l_i < x < r_i$ and $r_i$ is minimal. Let's call this segment the **representative** of the component. All representatives are stored in the set(segments in the set sorted by $r_i$). There are two cases: ↵
1. $x = l_i$ for some $i$. Add edges between the $i$-th vertex and all representatives $[l_j, r_j]$ in the set where $r_j < r_i$. Delete these segments and insert the representative of the new merged component. ↵
2. $x = r_i$ for some $i$. If $[l_i, r_i]$ is the representative, erase it from the set and insert a new one from the leader’s set of segments(if possible). ↵
Finally, verify thesolutionresult by simulating the algorithm described in the problem statement. ↵
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Two_Stacks_Sorting/main.cpp)↵
</spoiler>↵
↵
### [Grid Path Construction](https://cses.fi/problemset/task/2418)↵
↵
<spoiler summary="Solution">↵
[Hamilton Paths in Grid Graphs](https://www.researchgate.net/publication/220616693_Hamilton_Paths_in_Grid_Graphs) ↵
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Grid_Path_Construction/main.cpp)↵
</spoiler>↵
↵
↵
### [Inversion Probability](https://cses.fi/problemset/task/1728)↵
↵
<spoiler summary="Hint 1">↵
The intended solution is not difficult. The tricky part is rounding off the number.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
long double doesn't work. Find out why.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Use long arithmetic.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
For each pair $(i, j)$, the probability of it being an inversion is: ↵
\begin{cases} ↵
\displaystyle \frac{r_i — 1}{2 r_j} & \text{if } r_i \leq r_j, \\ ↵
\displaystyle \frac{2 r_i — r_j — 1}{2 r_i} & \text{if } r_i > r_j.↵
\end{cases}↵
↵
The answer is the sum of probabilities for all pairs. However, rounding the result is nontrivial because the decimal part of the expected value can be extremely close to $0.0000005$. Consider next test case:↵
↵
~~~~~↵
22↵
8 10 12 13 15 18 19 20 21 22 23 26 27 28 29 79 82 86 87 88 91 95↵
~~~~~↵
The exact answer is $53.418336500000000000094
[Code](https://github.com/ssevR/cses/blob/main/Mathematics/Inversion_Probability/main.py)↵
↵
</spoiler>↵
↵
### [Letter Pair Move Game](https://cses.fi/problemset/task/2427)↵
↵
<spoiler summary="Hint 1">↵
Solve the problem for $n \leq 4$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Did you notice anything when $n = 4$?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
A solution always exists when $n \geq 4$↵
</spoiler>↵
↵
Try to solve the problem for $n > 4$ using heuristic algorithm.↵
</spoiler>↵
↵
At the end, you need to apply your solution for n = 4(only a couple of times).↵
</spoiler>↵
↵
<spoiler summary="Similar problem">↵
[IOI1989P1](https://ioinformatics.org/files/ioi1989problem1.pdf)↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
If $n \leq 4$ just brute-force the problem using bfs. ↵
If $n > 4$: ↵
- Let $\text{b\_pos}$ be the index of the leftmost **B** in the current string. ↵
- Let $\text{a\_pos}$ be the index of the leftmost **A** in the substring starting from $\text{b\_pos} + 2$ to $2n$. ↵
- Swap $s[\text{b\_pos}, \text{b\_pos} + 1]$ with $s[\text{a\_pos}, \text{a\_pos} + 1]$ using 3 operations. ↵
↵
If $\text{a\_pos}$ cannot be found, apply $n=4$ solution. Don't forget to handle the edge case when $\text{a_pos} = 2 n$ ↵
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Letter_Pair_Move_Game/main.cpp)↵
</spoiler>↵
↵
### [Removing Digits II](https://cses.fi/problemset/task/2174)↵
↵
<spoiler summary="Hint 1">↵
Choose the largest available digit at each step.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
dp↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Think about powers of 10. ↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
Let's say that you know the answer for $10^i$. How can you find the answer for $10^{i + 1}$? What about $2 \cdot 10^i, 3 \cdot 10^i \dots 9 \cdot 10^i$?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
What additional information should you store to calculate the answer for these numbers?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 6">↵
3d dp↵
</spoiler>↵
↵
<spoiler summary="Original problem">↵
[331C3](https://codeforces.net/contest/331/problem/C3)↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Let's define $\text{pair<long long, int>} \text{dp}[i][j][k]$ where $i < 18, j < 10, k < 10$. ↵
$\text{dp}[i][j][k].\text{first}$ represents the number of operations needed to reduce $10^{i + 1} - j$ to $-\text{dp}[i][j][k].\text{second}$($0 \leq \text{dp}[i][j][k].\text{second} \leq 9$). ↵
$0 \leq k \leq 9$ is the maximum digit allowed in the suffix. ↵
Using this dp we can easily calculate the answer in $\mathcal{O} (\log
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Removing_Digits_II/main.cpp)↵
</spoiler>↵
↵
### [Counting Reorders](https://cses.fi/problemset/task/2421)↵
↵
<spoiler summary="Hint 1">↵
Solve the problem in $\mathcal{O}(n^3)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Try to optimize solution using inclusion–exclusion principle.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
$\mathcal{O} (|\Sigma| \cdot n^2)$ solution is short and simple, but it's hard to guess it.↵
</spoiler>↵
↵
<spoiler summary="Similar problem">↵
[CSP-J2019](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P5684#author=GPT_en)↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Let us define $\text{cnt}[i]$ as the number of occurrences of the $i$-th character.The DP state $\text{dp}[i][j]$ represents the number of strings that can be formed using the first $i$ characters and partitioned into $j$ blocks (a block is a sequence of consecutive identical characters). Note that a single string may be counted multiple times in this formulation. Compute $\text{dp}[i]$ in $\mathcal{O}(n^2)$ using binomial coefficients. After computing $\text{dp}[|\Sigma|]$ it's possible to find the total number of strings using inclusion-exclusion formula. For implementation details, refer to the provided [code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Counting_Reorders/main.cpp).↵
</spoiler>↵
↵
↵
### [Filling Trominos](https://cses.fi/problemset/task/2423)↵
↵
<spoiler summary="Hint 1">↵
What is necessary requirement?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
$3 \mid n \cdot m$ ↵
Without loss of generality let's assume that $3 \mid n$.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Construct a solution if $6 \mid n \cdot m$↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
Consider a case $n = 3$. What can you say about $m$?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
What if $n \cdot m$ is odd, $n \geq 9$ and $m \geq 5$? Does solution exist for this case? Can you prove it?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 6">↵
Try to construct solution for $9 \times 5$↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 7">↵
Use it to construct a solution for the last case.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
It's very clear that $3 \mid n \cdot m$ and $\text{min}(n, m) \geq 2$. Without loss of generality let's assume that $3 \mid n$ (otherwise, transpose the grid). ↵
1. For $n = 3$ and $m \geq 2$, a solution exists if and only if $m$ is even. It can be proved by induction. ↵
2. If $n$ or $m$ is even, use a tiling pattern with $3 \times 2$ or $2 \times 3$ blocks. ↵
3. $n \cdot m$ is odd, $n \geq 9$ $m \geq 5$. There exists a solution for $9 \times 5$. You can construct it on paper or by using profile dp. Now if you put $9 \times 5$ in the upper left corner the grid splits into two rectangles: $(n - 9) \times 5$ and $n \times (m - 5)$. Solve these using construction of previous case. ↵
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Filling_Trominos/main.cpp)↵
</spoiler>↵
↵
### [Functional Graph Distribution](https://cses.fi/problemset/task/2415)↵
↵
<spoiler summary="Hint 1">↵
[Stirling numbers of the first kind](https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind)↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
[Cayley's formula](https://en.wikipedia.org/wiki/Cayley%27s_formula)↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
The problem is [OEIS-able](https://oeis.org/A060281). ↵
The formula is obtained by combining the two given ideas. ↵
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Functional_Graph_Distribution/main.cpp)↵
</spoiler>↵
↵
### [Grid Completion](https://cses.fi/problemset/task/2429)↵
↵
<spoiler summary="Hint 1">↵
Try to think about the problem in terms of graph↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Solve the problem when grid is empty.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Try to get rid of cycles of length 2.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
Use inclusion–exclusion principle.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
For each $i$, find the number of completion with at least $i$ cycles of length 2. ↵
</spoiler>↵
↵
↵
<spoiler summary="Key observation">↵
Consider a component with $>1$ edges. It's impossible to form a cycle of length 2 with vertices of this component.↵
</spoiler>↵
↵
↵
<spoiler summary="Similar problem">↵
[ARC186A](https://atcoder.jp/contests/arc186/tasks/arc186_a)↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
For an $N \times N$ grid $G$, construct a directed bipartite graph with partitions $\{R_1, \dots, R_N\}$ (rows) and $\{C_1, \dots, C_N\}$ (columns): ↵
- If $G[i][j] = A$, direct an edge from $R_i$ to $C_j$. ↵
- If $G[i][j] = B$, direct an edge from $C_j$ to $R_i$. ↵
↵
The goal is to count the number of ways to complete this graph into non-intersecting cycles covering all vertices, with no 2-cycles It's easy to see that such cycles can only be formed from isolated vertices or 1-edge components. The answer can be calculated by inclusion–exclusion principle iterating over the number of 2-length cycles formed by isolated vertices, the number of 1-edge components from left part and 1-edge components from right part. The time complexity is $\mathcal{O}(N^3)$. ↵
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Grid_Completion/main.cpp)↵
</spoiler>↵
↵
### [Two Stacks Sorting](https://cses.fi/problemset/task/2402)↵
↵
↵
<spoiler summary="Hint 1">↵
How long $i$-th number has to be be in stack?↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Try to represent the problem in terms of sets of segments(endpoints of segments must be unique).↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
This [problem](https://codeforces.net/edu/course/2/lesson/7/2/practice/contest/289391/problem/I) may be useful.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 4">↵
Add only essential edges.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 5">↵
Iterate through the endpoints from left to right↵
</spoiler>↵
↵
↵
<spoiler summary="Similar problems">↵
[1691E](https://codeforces.net/problemset/problem/1691/e) ↵
[JOISC2017B](https://qoj.ac/problem/361)↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
$p_1, \dots, p_n$ is a given permutation. ↵
For each $i$ let's consider $j = \max k \colon p
1. $x = l_i$ for some $i$. Add edges between the $i$-th vertex and all representatives $[l_j, r_j]$ in the set where $r_j < r_i$. Delete these segments and insert the representative of the new merged component. ↵
2. $x = r_i$ for some $i$. If $[l_i, r_i]$ is the representative, erase it from the set and insert a new one from the leader’s set of segments(if possible). ↵
Finally, verify the
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Two_Stacks_Sorting/main.cpp)↵
</spoiler>↵
↵
### [Grid Path Construction](https://cses.fi/problemset/task/2418)↵
↵
<spoiler summary="Solution">↵
[Hamilton Paths in Grid Graphs](https://www.researchgate.net/publication/220616693_Hamilton_Paths_in_Grid_Graphs) ↵
[Code](https://github.com/ssevR/cses/blob/main/Additional_Problems/Grid_Path_Construction/main.cpp)↵
</spoiler>↵
↵
