Editorial for Wather

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: leo

Task Wather

It was possible to get partial points worth 40% of total points by trying out each permutation of glasses, where the label of the glass in the permutation denotes spilling the content of the glass with that label to one of the glasses to the right of that label in the permutation. We will always choose spilling over such that the effort is minimal, since we don’t care which of the remaining glasses we spill into.

For 100% of total points, we use dynamic programming. Let the state be a bitmask of the glasses we haven’t yet spilled into another glass, and the content of the rest of the glasses is contained within these glasses. The transition we can make is picking one of the glasses from the set and spilling the content into any other glass from the set. The total complexity of the transitions is O( N^2 ), and can be potentially accelerated, but there is no need. The total complexity is O(2^N * N^2 ). For implementation details, consult the official solution.

Necessary skills: dynamic programming, bitmasks

Category: dynamic programming

Comments