Triway Cup '19 Summer A - Cave Escape - DMOJ: Modern Online Judge

Triway Cup '19 Summer A - Cave Escape

Points: 17

Time limit: 1.0s

Memory limit: 256M

Authors:

Problem types

Rico and Reg are running from the authorities as they descend into the first floor of the abyss. The authorities are trying to catch them, and asked you for help!

The first floor of the abyss is an interconnected network of $N$ ~N~ caves and $N-1$ ~N-1~ tunnels. The entrance is located at cave $0$ ~0~, which the authorities wish to force Rico and Reg to. Their method of forcing the adventurers out from the caves is a series of traps, one in each cave, that when activated, force any adventurers in that cave to move to a connected cave that is closer to the entrance.

The authorities try to catch Rico and Reg over a series of days. At the start of each day, traps can be turned on or off. Each trap is initially off and can be turned on exactly once. Traps that are on can also be turned off, but cannot be turned on again afterwards. Then, Rico and Reg can repeatedly travel from the node that they occupy to another cave that it is connected to (but if they travel to a node with a trap that is on, or a trap is activated in their current node, they are immediately forced to move, however, if they are moved by another trap, they will not be forced to move again). Note that they cannot "skip past" caves that have activated traps. (Example: if caves $0$ ~0~, $1$ ~1~, $2$ ~2~, $3$ ~3~, $4$ ~4~ are connected in that order, and cave $3$ ~3~ has an activated trap, it is impossible to move from cave $2\to 3\to 4$ ~2\to 3\to 4~, since upon moving to $3$ ~3~, they would immediately be sent back to $2$ ~2~). Also note that Rico and Reg do not move while traps are being switched on or off.

Let the power be the maximum number of traps that must be on during a single day, assuming the authorities try to minimize this value. Find the minimum power required to force the adventurers back to cave $0$ ~0~, if both parties move optimally.