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 a1, a2, ..., ak. 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 dpi, 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 dpi, j and dpj, i may be different).
F: We want to compute dpi, j: expected value given we have seen i red balls and j black balls.
Solutions
P.S. Please notify me if there are any problems.