arc081_c: Don’t Be a Subsequence

Start from empty string, try finding the first index where all a-z are included. If unable to find it before the end of the string, we have an answer. Otherwise, reset indices, and repeat the process

Official solution

  1. Use dp to caluate the length of target subsequence len[i] = min(len(next(i, c))) + 1

  2. start from 0, find the smallest char c, s.t., len[i] = len(next(i,c)) + 1, and then update i

arc083_c: Bichrome Tree

Official solution

Consider minV(v) = min total of the values of different color, then for each child node, we can mark either the child node same as the root color or not!!! i.e., we add sum to either v(c) or minV(c) to the current node value. We want to find min other value while to current node value <= v(parent), we can use a minOther(child, current value total) dp at each node. Again, because the value is positive, we can just ignore out of boudn case

arc085_b: ABS

Claim: A can not get better result than taking all but last or last in the first step!!! Proof: If A takes less than second last in the first move, and can achieve better result, then B can take the last or second last instead, which blocks A’s moves

arc086_b: Non-decreasing

If |minV| > |maxV|, add minV to all, and do a rolling add from n to 1. Otherwise, add maxV to all, and do a rolling add from 1 to n.

arc087_b: FT Robot

Standard coding problem. Note that for the each of coding, we can handle x and y separately!!!

arc088_b: Wide Flip

bsearch on K, at each K guess, do a greey conversion, start at the leftmost 1, and issue a flip, to improve the speed, use an even-based approach.

Official solution

For each different a[i] and a[i+1], we know we have to flip it, and the min length <= min(i + 1, L - i + 1).

It becomes obvious that we can find a solution given these upperbounds, i.e., the tighest upper bound is the solution, because it is no problem for us to filp longer segments. We can fix them one by one from left to right