In this blog I will write up solutions for some IOI tasks I solved recently because I have too much energy and not enough things to do. ↵
↵
Also I noticed a disturbing trend in CF blogs where grays publish AI generated solutions for problems. So this blog is in part an attack against that.↵
↵
# IOI 2011 Tropical Garden↵
↵
[Here is the statement](https://dmoj.ca/problem/ioi11p1)↵
↵
<spoiler summary="Part 1">↵
↵
We need to simplify the input. Let's define a graph on $2n$ vertices $V_1, V_2, ..., V_n, W_1, W_2, ..., W_n$. $V_i$ and $W_i$ represent the state of being in vertex $i$, but $W_i$ imposes the additional restriction that you just came from the largest edge.↵
↵
For a vertex $i$ let $ij$ be the largest edge connected with $i$, and let $ik$ to be the second largest, or $j$ if it's the only neighbor. We will add the following edges:↵
↵
- $V_i \rightarrow V_j$ or $W_j$ depending on whether $ij$ is the biggest edge for $j$ or not.↵
↵
- $W_i \rightarrow V_k$ or $W_k$ depending on whether $ik$ is the biggest edge for $k$ or not.↵
↵
The task now simply to count the number of vertices among $V_1, V_2, ..., V_n$ that end up at $V_p$ or $W_p$ after taking $k$ steps in this state graph. Now we have a bruteforce $\operatorname{O}(nk)$ solution per query. You can also achieve this complexity by simple brute force.↵
↵
</spoiler>↵
↵
<spoiler summary="Part 1.5">↵
↵
It's possible to solve this task in $\operatorname{O}(n \log k)$ per query by going through each vertex and finding where it ends up in $k$ steps using binary lifting. This gets the first 2 subtasks and 69 points.↵
↵
</spoiler>↵
↵
<spoiler summary="Part 2">↵
↵
Full points may or may not be easier than getting just 69. ↵
↵
We need to understand the structure of the graph we have built. Each component looks a bunch of rooted trees, where some of the roots have been connected in a cycle. This means that if $t$ is in a cycle of length $3$, and min number of steps for some vertex $s$ to reach $t$ is $4$ for example, then it will visit $t$ after $7, 10, 13, ..., 67, ...$ steps as well. ↵
↵
Let's focus on $V_p$ for now, as all these checks can be done for $W_p$ just as well. We will reverse all the edges and calculate the distance from $V_p$ to all other vertices. Let these distances be called $d_i$. Also let $c$ be the length of the cycle $V_p$ is in or $93858158317519$ if it's not in a cycle. Then all we have to do to check if $V_i$ reaches $V_p$ in $k$ steps is:↵
↵
- $d_{V_i} \ge k$↵
- $d_{V_i} - k$ is a multiple of $c$↵
↵
So we can answer a query in $\operatorname{O}(n)$ per query.↵
↵
</spoiler>↵
↵
# IOI 2019 Vision Program↵
↵
[Statement](https://dmoj.ca/problem/ioi19p5)↵
↵
<spoiler summary="Part 1">↵
↵
Looking at the manhattan distance is hard and annoying. An easier and more straightforward calculation would be to find the number of diagonals and antidiagonals that seperate the two cells, and check that the bigger of them is $k$. The name of the game is to collapse down the diagonals and antidiagonals into a single cell and do some calculations on them.↵
↵
For each diagonal and antidiagonal, check if it contains exactly 1 black cell. We can do this by $\operatorname{OR}$-ing and $\operatorname{XOR}$-ing the whole diagonal/antidiagonal and $\operatorname{AND}$-ing them together. This takes roughly $2(n + m)$ instructions and their total length is $2nm$.↵
↵
</spoiler>↵
↵
<spoiler summary="Part 2">↵
↵
Given an array of $L$ boolean variables $a_1, a_2, ..., a_L$, two of which are True. Determine if they are at a distance of $k$. This will be useful for determining if the black cells are exactly $k$ diagonals or antidiagonals away from each other.↵
↵
This can be done by going through $1, 2, ..., n-k$, computing $a_i \operatorname{AND} a_{i+k}$, and $\operatorname{OR}$-ing them together. This is roughly $2(N + M)$ with total length $4(n + m)$.↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Part 3">↵
↵
Given an array of $L$ boolean variables $a_1, a_2, ..., a_L$, two of which are True. Determine if they are at a distance of $k$ or less. It will actually be easier to check if they are *further* than $k$ apart.↵
↵
We will calculate "suffix $\operatorname{OR}$." Let this array be called $s_1, s_2, ..., s_L$. Now it's simple, we just need to take $\operatorname{AND}$ of $a_i$ and $s_{i+k+1}$ and take $\operatorname{OR}$ of those. This needs about $4(n + m)$ instructions and total length $8(n + m)$.↵
↵
Let $a$ be the diagonal distance and $b$ be the antidiagonal distance. Using the algorithms from parts 2 and 3, we have found whether:↵
↵
- $a = k$↵
↵
- $a ≤ k$↵
↵
- $b = k$↵
↵
- $b ≤ k$↵
↵
So we just need take $\operatorname{AND}$ of first and fourth, $\operatorname{AND}$ of second and third, and $\operatorname{OR}$ those together.↵
↵
</spoiler>↵
↵
<spoiler summary="Comment">↵
↵
This is one of my favorite IOI tasks. I love tasks like this and 2021's Registers that give you an esoteric set of instructions that have you compute something. Comparing these tasks with Tropical Garden is like night and day. I wish tasks like this were more common, IOI and elsewhere. It really exemplifies why informatics is special and very different from olympiad math and such.↵
↵
</spoiler>↵
↵
↵
Wow it's already 2 AM, it's almost been 3 hours. I feel very tired so mission accomplished.↵
↵
Also I noticed a disturbing trend in CF blogs where grays publish AI generated solutions for problems. So this blog is in part an attack against that.↵
↵
# IOI 2011 Tropical Garden↵
↵
[Here is the statement](https://dmoj.ca/problem/ioi11p1)↵
↵
<spoiler summary="Part 1">↵
↵
We need to simplify the input. Let's define a graph on $2n$ vertices $V_1, V_2, ..., V_n, W_1, W_2, ..., W_n$. $V_i$ and $W_i$ represent the state of being in vertex $i$, but $W_i$ imposes the additional restriction that you just came from the largest edge.↵
↵
For a vertex $i$ let $ij$ be the largest edge connected with $i$, and let $ik$ to be the second largest, or $j$ if it's the only neighbor. We will add the following edges:↵
↵
- $V_i \rightarrow V_j$ or $W_j$ depending on whether $ij$ is the biggest edge for $j$ or not.↵
↵
- $W_i \rightarrow V_k$ or $W_k$ depending on whether $ik$ is the biggest edge for $k$ or not.↵
↵
The task now simply to count the number of vertices among $V_1, V_2, ..., V_n$ that end up at $V_p$ or $W_p$ after taking $k$ steps in this state graph. Now we have a bruteforce $\operatorname{O}(nk)$ solution per query. You can also achieve this complexity by simple brute force.↵
↵
</spoiler>↵
↵
<spoiler summary="Part 1.5">↵
↵
It's possible to solve this task in $\operatorname{O}(n \log k)$ per query by going through each vertex and finding where it ends up in $k$ steps using binary lifting. This gets the first 2 subtasks and 69 points.↵
↵
</spoiler>↵
↵
<spoiler summary="Part 2">↵
↵
Full points may or may not be easier than getting just 69. ↵
↵
We need to understand the structure of the graph we have built. Each component looks a bunch of rooted trees, where some of the roots have been connected in a cycle. This means that if $t$ is in a cycle of length $3$, and min number of steps for some vertex $s$ to reach $t$ is $4$ for example, then it will visit $t$ after $7, 10, 13, ..., 67, ...$ steps as well. ↵
↵
Let's focus on $V_p$ for now, as all these checks can be done for $W_p$ just as well. We will reverse all the edges and calculate the distance from $V_p$ to all other vertices. Let these distances be called $d_i$. Also let $c$ be the length of the cycle $V_p$ is in or $93858158317519$ if it's not in a cycle. Then all we have to do to check if $V_i$ reaches $V_p$ in $k$ steps is:↵
↵
- $d_{V_i} \ge k$↵
- $d_{V_i} - k$ is a multiple of $c$↵
↵
So we can answer a query in $\operatorname{O}(n)$ per query.↵
↵
</spoiler>↵
↵
# IOI 2019 Vision Program↵
↵
[Statement](https://dmoj.ca/problem/ioi19p5)↵
↵
<spoiler summary="Part 1">↵
↵
Looking at the manhattan distance is hard and annoying. An easier and more straightforward calculation would be to find the number of diagonals and antidiagonals that seperate the two cells, and check that the bigger of them is $k$. The name of the game is to collapse down the diagonals and antidiagonals into a single cell and do some calculations on them.↵
↵
For each diagonal and antidiagonal, check if it contains exactly 1 black cell. We can do this by $\operatorname{OR}$-ing and $\operatorname{XOR}$-ing the whole diagonal/antidiagonal and $\operatorname{AND}$-ing them together. This takes roughly $2(n + m)$ instructions and their total length is $2nm$.↵
↵
</spoiler>↵
↵
<spoiler summary="Part 2">↵
↵
Given an array of $L$ boolean variables $a_1, a_2, ..., a_L$, two of which are True. Determine if they are at a distance of $k$. This will be useful for determining if the black cells are exactly $k$ diagonals or antidiagonals away from each other.↵
↵
This can be done by going through $1, 2, ..., n-k$, computing $a_i \operatorname{AND} a_{i+k}$, and $\operatorname{OR}$-ing them together. This is roughly $2(N + M)$ with total length $4(n + m)$.↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Part 3">↵
↵
Given an array of $L$ boolean variables $a_1, a_2, ..., a_L$, two of which are True. Determine if they are at a distance of $k$ or less. It will actually be easier to check if they are *further* than $k$ apart.↵
↵
We will calculate "suffix $\operatorname{OR}$." Let this array be called $s_1, s_2, ..., s_L$. Now it's simple, we just need to take $\operatorname{AND}$ of $a_i$ and $s_{i+k+1}$ and take $\operatorname{OR}$ of those. This needs about $4(n + m)$ instructions and total length $8(n + m)$.↵
↵
Let $a$ be the diagonal distance and $b$ be the antidiagonal distance. Using the algorithms from parts 2 and 3, we have found whether:↵
↵
- $a = k$↵
↵
- $a ≤ k$↵
↵
- $b = k$↵
↵
- $b ≤ k$↵
↵
So we just need take $\operatorname{AND}$ of first and fourth, $\operatorname{AND}$ of second and third, and $\operatorname{OR}$ those together.↵
↵
</spoiler>↵
↵
<spoiler summary="Comment">↵
↵
This is one of my favorite IOI tasks. I love tasks like this and 2021's Registers that give you an esoteric set of instructions that have you compute something. Comparing these tasks with Tropical Garden is like night and day. I wish tasks like this were more common, IOI and elsewhere. It really exemplifies why informatics is special and very different from olympiad math and such.↵
↵
</spoiler>↵
↵
↵
Wow it's already 2 AM, it's almost been 3 hours. I feel very tired so mission accomplished.↵
