Editorial for COCI '16 Contest 3 #3 Kroničan
Submitting an official solution before solving the problem yourself is a bannable offence.
It was possible to get partial points worth 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 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 , and can be potentially accelerated, but there is no need. The total complexity is .
Comments