Pre-requisites: Greedy, Games
Given a rooted tree. Two players play a game on the tree. The first player can delete arbitrary non-empty set of roots during his turn, the second player can delete arbitrary non-empty set of leaves during his turn. The game ends when the tree becomes empty. The first player wants the game to end as soon as possible, while the second player wants the game to run as long as possible. Both players play optimally. You are to determine the number of moves of the game.
In problems like this it’s always required to come up with some insights like “It’s always optimal to play like this…” or “It’s possible to win making only that kind of operations…” and so on.
The first greedy insight for solving this problem is the following: the first player should always delete all available roots at the moment.
Why? Because he wants to end up this game as soon as possible! Not deleting all available roots may lead the game to be longer.
The second player always delete the deepest leaf in the current tree.
So, we should just simulate the game according to the winning strategy of both players. Let’s focus on some implementation details.
First of all, we can sort all the vertices by its depth. Then we can maintain pointer L on the last vertex deleted by the first player. Also, we can maintain pointers R on the last vertex deleted by the first player.
When it’s the first player’s move, then we should delete all vertices that have the same depth with L’s vertex in sorted order.
When it’s the second player’s move, then we should delete R’s vertex in sorted order.
Total complexity is O( N log N ) per testcase.
Please, check out Setter’s and Tester’s solutions for your better understanding.
Setter’s Solution: link
Tester’s Solution: link