TREEGAME - Editorial

general
, , , ,
1

Problem Link: contest, practice

Difficulty: Easy

Pre-requisites: Greedy, Games

Problem:

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.

Explanation:

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

2

I think the problem statement was very disappointing and had too many assumptions about the way of interpreting the problem statement as a reader. I asked you a few questions during the challenge with no answers, but at the end, I managed to understand it after getting the crucial “hint” from the announcement.

Technically, the way you’ve wanted to define the leaves, did not correspond to the real definition of leaves in a tree.

"A leaf is a vertex of degree 1. An internal vertex is a vertex of degree at least 2." (Wikipedia)

Also, when I drew the tree on my scratchpaper, I had marked the number 1 node as the root. So my tree was rooted, but not drawn in the way, where deeper nodes are closer to the bottom of the paper. So when I removed a node in my mind, I was thinking about for a long time, which nodes were the new roots of the new subtrees.

11 Likes
3

The problem can actually be solved in O(n) time. Just compute depths by breadth-first search, and no sorting is required since BFS guarantees that processed vertices will have nondecreasing depths. (I’d have to admit though that I failed to solve this during the contest because I took the edges as unidirectional.)

1 Like
4

I misunderstood edges as directed :frowning:

3 Likes
5

The problem statement was not clear enough :-/
At least there could have been an example to show that edges were undirected.

4 Likes
6

Did this one with a deque, really short code after calculating all the depths. :slight_smile:

7

Alternatively, the depths are up to N, so linear-time sort works as well.

8

I also thought about that. But then again, we don’t talk about edge directions with trees (plus if they’re rooted, there’s a clear direction “to the root”).

1 Like
9

me too assumed that the edges are unidirectional. problem statement is too unclear :frowning:

10

How does it matter if the graph is undirected? Can you please put a test case here to show how answer would be different if a graph is undirected?

11

Can someone point out which case am I missing here -
http://www.codechef.com/viewsolution/4621787

I used dfs to find height of the tree and number of nodes at each level. Then at each turn the first player moves one level down and the other player subtracts one node if there is any left on his level or else he moves up.

The soln gives WA after 0.15 secs so it must be a corner case or some thing :stuck_out_tongue:
Even some tough test case would be helpful where my code fails.

12

I did it using Level order traversal of the tree.
Then start from last level and for every node in the current level increase the turn number for both the players .Then the turn where the players are on the same level, answer there is ans=2turn+1 or 2turn-1.

My solution: http://www.codechef.com/viewsolution/4643962

13

i have a testcase where the given algorithm may give a wrong answer :
1
8
1 2
2 5
5 8
1 3
3 6
1 4
4 7
the answer to this is 6 while the given algorithm will give 5 as answer!!!

1 Like