IndiaHacks 2nd Elimination 2017 editorial

Revision en4, by Arpa, 2017-08-07 20:58:26

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.

History

Revisions

Rev. Lang. By When Δ Comment
en4 Arpa 2017-08-07 20:58:26 102 Added codes
en3 Arpa 2017-08-07 20:24:45 91
en2 Arpa 2017-08-07 20:23:29 2 Tiny change: 'ots, a_k}}\n$is odd a' -> 'ots, a_k}}$ is odd a' (published)
en1 Arpa 2017-08-07 20:19:09 924 Initial revision (saved to drafts)