Codeforces Round 605 (Div 3) Solution & Reflection

December 12, 2019


A: Three Friends

Just brute force. Try 1-1, 00 and +1+1 for each of aa, bb and cc, and output the smallest ab+ac+b+c\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)(0, 0), the number of UU and DD must be the same and the number of LL and RR must be the same. Take minimum of UU and DD, and minimum of LL and RR, and output a rectangle.

Note that when there is no UU and DD, the output can only be LR or RL, as LLRR is against the rules. Same for when there is no LL and RR.

C: Yet Another Broken Keyboard

Break the string into parts with no non-broken keyboard, then calculate the sum of n(n+1)2\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 dpi,0dp_{i,0} be the length of longest subsequence without skipping and dpi,1dp_{i,1} be the length of longest subsequence with skipping. Then we have

    1. dpi,0=dpi1,0+1dp_{i,0} = dp_{i-1,0} + 1 if ai>ai1a_i > a_{i-1}, 11 otherwise
    2. dpi,1=max(dpi1,1+1 if ai>ai1,dpi2,0+1 if ai>ai2)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}), 11 otherwise
  2. Calculate LiL_i, length of longest strictly increasing sequence from the left ending at ii, and RiR_i, length of longest strictly decreasing subsequence from the right ending at ii. The answer is then the max of LiL_i and Li1+Ri+1:ai1<ai+1\\{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 ii to jj. Build a graph containing all edges jij \to i. Then perform two multi-source BFS: (a) one where disti=0dist_i = 0 for all ii where aia_i is odd, and (b) one where disti=0dist_i = 0 for all ii where aia_i is even.

For each ii, output shortest distance to node ii in (a) if aia_i is even, and shortest distance to node ii in (b) if aia_i is odd.

F: Two Bracket Sequences

Cannot solve during contest time.

Derived a O(N4)O(N^4) DP solution, where dpi,j,k,ldp_{i,j,k,l} is whether string of length ii, already matching jj characters of SS and kk characters of TT, with ll 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 ii, but only the smallest ii for each j,k,l\\{j, k, l\\}. So we can calculate dpj,k,ldp_{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)