# A: Three Friends

Just brute force. Try $-1$, $0$ and $+1$ for each of $a$, $b$ and $c$, and output the smallest $\lvert a' - b'\rvert + \lvert a' - c'\rvert + \lvert b' + c'\rvert$.

Don't waste time like me trying to write a greedy solution when a brute force solution works, especially in Codeforces where penalty is really important.

# B: Snow Walking Robot

To go back to $(0, 0)$, the number of $U$ and $D$ must be the same and the number of $L$ and $R$ must be the same. Take minimum of $U$ and $D$, and minimum of $L$ and $R$, and output a rectangle.

Note that when there is no $U$ and $D$, the output can only be LR or RL, as LLRR is against the rules. Same for when there is no $L$ and $R$.

# C: Yet Another Broken Keyboard

Break the string into parts with no non-broken keyboard, then calculate the sum of $\frac{n(n+1)}{2}$ for each block.

Note that the formula is given in the problem. Don't waste time trying to calculate it yourself.

# D: Remove One Element

Two solutions:

1. Apply dynamic programming directly. Let $dp_{i,0}$ be the length of longest subsequence without skipping and $dp_{i,1}$ be the length of longest subsequence with skipping. Then we have

1. $dp_{i,0} = dp_{i-1,0} + 1$ if $a_i > a_{i-1}$, $1$ otherwise
2. $dp_{i,1} = \max(dp_{i-1,1} + 1 \text{ if } a_i > a_{i-1}, dp_{i-2,0} + 1 \text{ if } a_i > a_{i-2})$, $1$ otherwise
2. Calculate $L_i$, length of longest strictly increasing sequence from the left ending at $i$, and $R_i$, length of longest strictly decreasing subsequence from the right ending at $i$. The answer is then the max of $L_i$ and $\\{L_{i-1} + R_{i+1} : a_{i-1} < a_{i+1}\\}$.

Wasted too much time fixing a stupid bug, where I wrote ans = max(dp[i][0], dp[i][1]) instead of ans = max(ans, max(dp[i][0], dp[i][1])).

# E: Nearest Opposite Party

This is an interesting question.

Assume that you can move from $i$ to $j$. Build a graph containing all edges $j \to i$. Then perform two multi-source BFS: (a) one where $dist_i = 0$ for all $i$ where $a_i$ is odd, and (b) one where $dist_i = 0$ for all $i$ where $a_i$ is even.

For each $i$, output shortest distance to node $i$ in (a) if $a_i$ is even, and shortest distance to node $i$ in (b) if $a_i$ is odd.

# F: Two Bracket Sequences

Cannot solve during contest time.

Derived a $O(N^4)$ DP solution, where $dp_{i,j,k,l}$ is whether string of length $i$, already matching $j$ characters of $S$ and $k$ characters of $T$, with $l$ unclosed open brackets can be reached. This solution barely fits within the memory limit (400 MB), but is nearly impossible to backtrack without extra information and there is no memory left.

Note that we do not need to store the results for all $i$, but only the smallest $i$ for each $\\{j, k, l\\}$. So we can calculate $dp_{j,k,l}$, storing the shortest length only, and we now have enough memory to store the backtrack information.

# Result

Rank 71, 5 Solved, Total Penalty 163 (taken during open hacking phase)