A: Three Friends
Just brute force. Try , and for each of , and , and output the smallest .
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 , the number of and must be the same and the number of and must be the same. Take minimum of and , and minimum of and , and output a rectangle.
Note that when there is no and , the output can only be LR
or RL
, as LLRR
is against the rules. Same for when there is no and .
C: Yet Another Broken Keyboard
Break the string into parts with no non-broken keyboard, then calculate the sum of 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:
-
Apply dynamic programming directly. Let be the length of longest subsequence without skipping and be the length of longest subsequence with skipping. Then we have
- if , otherwise
- , otherwise
- Calculate , length of longest strictly increasing sequence from the left ending at , and , length of longest strictly decreasing subsequence from the right ending at . The answer is then the max of and .
Wasted too much time fixing a stupid bug, where I wrote
ans = max(dp[i][0], dp[i][1])
instead ofans = max(ans, max(dp[i][0], dp[i][1]))
.
E: Nearest Opposite Party
This is an interesting question.
Assume that you can move from to . Build a graph containing all edges . Then perform two multi-source BFS: (a) one where for all where is odd, and (b) one where for all where is even.
For each , output shortest distance to node in (a) if is even, and shortest distance to node in (b) if is odd.
F: Two Bracket Sequences
Cannot solve during contest time.
Derived a DP solution, where is whether string of length , already matching characters of and characters of , with 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 , but only the smallest for each . So we can calculate , 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)