Indigo Codes 2024

It’s been a while since I last posted. I had a few ideas for a post but never had the chance to write them.

Last Saturday, Indigo Codes 2024 happened.

I did not manage to take it due to a conflict, but the problems I managed to solve afterwards were quite interesting.

1. Special Mods#

Pretty standard prefix sum problem. Since $N \leq 5000$, you can iterate over every range and see if the sum is equivalent to $K \bmod M$

2. Array Swapping#

Notice that the way a swap is defined means that you can only change a position to exactly one other position

Thus, you only need to check if each number $i$ is in either the $i$-th position or the $(n + i - 1)$-th position.

If $i$ is in the $(n + i - 1)$-th position, add one to the answer, and swap the $i$-th and $(n + i - 1)$-th position.

3. Beautiful Tree#

Greedily add edges.

4. William’s Garden 1#

Define $f_i$ as the number of ways modulo $10^9 + 7$ to restore a $i \times 2$ grid

The transition is as follows:

$\displaystyle{f_i = (f_{i - 1} + f_{i - 2} + 2 \cdot \sum_{j = 0}^{i - 2} f_j) \bmod 10^9 + 7}$

with $f_0 = 1$ and $f_1 = 1$

This is correct because at each $i$, we can either add a vertical swap, $2$ horizontal swaps, or a cycle of arbitrary length (counter)clockwise

Alternatively, one can notice that $f_i$ is the square of the $i$-th fibonacci number (proof as to why on William’s Garden 2)

5. Favorite Sequences#

Define $f_{i, j}$ as the number of lovable sequences ending on the number $i$ after the $j$-th number is considered modulo $10^9 + 7$ and $g_{i, j}$ as the sum of lovable sequences ending on the number $i$ after the $j$-th number is considered modulo $10^9 + 7$

The transitions are as follows:

$\displaystyle{f_{i, j} = (\sum_{k = i - x}^{i + x} f_{k, j - 1}) \bmod 10^9 + 7}$

$\displaystyle{g_{i, j} = (i \cdot (f_{i, j} - f_{i, j - 1}) \cdot (\sum_{k = i - x}^{i - 1} g_{k, j - 1} + \sum_{k = i + 1}^{i + x} g_{k, j - 1}) + g_{i, j - 1}) \bmod 10^9 + 7}$

At each $a_j$, we only need to update one value of $f$ and $g$, so the runtime is $O(nx)$

6. Cifjump#

I don’t quite know how to utilize the small bound on $v_i$, so I will describe a solution that works for larger $v_i$

We can restate the problem as:

For each position $x$, what is the minimum number of hops to move at least $n$ positions?

Using binary jumping, we can find the distance travelled in $m$ moves in $O(\log m)$. Naively binary searching leads to a time complexity of $O(n \log^2 n)$, which is too slow for $n \leq 10^6$

Notice that if we are doing a lot of recomputation every time we try a value of $m$. If we allow the midpoint of the binary search to split the current interval into powers of 2, then we only need to do $O(1)$ operations per check (This is also the idea behind bitwise binary search).

7. I Like My Trees Drippy#

I haven’t implemented this yet.

8. William’s Garden 2#

I also haven’t implement this yet, but the idea is really nice. Remember how the solution to the easy version was the square of the fibonacci numbers? This is because we can imagine swaps as two domino tilings, where the first one represents where the first tiling represents the way to move a pepper and the second represents the way to move a tomato.

Now comes the problem of calculating domino tilings. One can construct a linear recurrence dp for $m = 2, 3, 4$ and use matrix exponentiation.

9. Work Shifts#

I haven’t read or implemented this yet.

10. Casino Dice Game#

Too hard.

Code#

Code for the first 6 problems can be found in this repository