Editorial for DMOPC '22 Contest 1 P5 - Wesley's Cabins

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: Riolku

Subtask 1 Hint 1

For any given node, suppose the water we get from our parent is fixed. We have to press our lever to fill up the node. At what points do we stop?

Subtask 1 Hint 2

We stop whenever any child (including non-direct child) fills up, at which point we recurse.

Subtask 1

We stop whenever any child (including non-direct child) fills up, at which point we recurse. On a line, this means we get a complexity of \mathcal O(N!).

Specifically, we are pressing the current node's lever until a child fills up, and then summing the costs from all the children.

This is much like an algorithm that tries all amounts to push down, except since we are using floats, we have to determine the breakpoints ourselves.

There is also a simplex solution to this subtask, but it is useless for further subtask solving.

Subtask 2 Hint 1

Let f_u(v) be the cost to satisfy node u's subtree assuming it is provided with v units of water from its parent. Based on subtask 1, what observations can we make about f_u?

Subtask 2 Hint 2

f_u(v) is a piecewise function, since we have to re-calculate the costs every time a node fills. It is convex, since when a node fills up we always have more, not less, options for levers. Each of the pieces of the function is linear, since we are pressing a lever that fills linearly.

Subtask 2 Hint 3

Slope trick.

Subtask 2

We can represent the functions as a set of pairs, (change_point, slope_change). This definition means that when we add the functions (because this function is recursive), adding functions is equivalent to merging the sets.

Let F_u be the portion, as a decimal, of water that remains in node u when a lever is pushed.

Subtask 3 Hint 1

Very large points will cause precision issues. How can we deal with them?

Subtask 3 Hint 2

What if we delete large points and replace them with a flat section?

Subtask 3

By deleting very large points (>10^{50}) and adding a constant to the answer, we can circumvent issues with precision.

Since the slopes get big very quickly, the sets get pruned quickly enough to achieve a good enough complexity.


There are no comments at the moment.