Hi!

Hints

A: Let Cost(k) the answer if we compress the image with k, find min Cost(k).

B: Solve the problem without first query.

C: Let the frequencies of the characters be a₁, a₂, ..., a_k. Alice loses if and only if is odd and n is even.

D: Consider adding an extra seat, and the plane is now circular.

E: Let dp_i, j be the longest path given that we've included segment i, j in our solution, and we are only considering points to the right of ray i, j (so dp_i, j and dp_j, i may be different).

F: We want to compute dp_i, j: expected value given we have seen i red balls and j black balls.

Solutions

P.S. Author solutions will be added soon. Please notify me if there are any problems.