SATA04 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

Author: Akul Sareen

Tester: -

Editorialist: Akul Sareen

DIFFICULTY:

HARD.

PREREQUISITES:

Basic graph theory

PROBLEM:

Given a tournament graph on N nodes, find a node such that the maximum distance from this node to any other node is minimized.

QUICK EXPLANATION:

Maximum distance is at most 2. Node with maximum degree is always a valid starting point. Both these claims can be proven with some basic amount of logic.

EXPLANATION:

The given question can be modeled easily as a tournament graph. After playing for a while with random tournament graphs you might get the feeling that the minimum required range of the car is never very high.

Claim 1: Minimum required range is at most 2

Let us prove this claim by induction on the number of nodes. For the base case (n = 1), we can see it is trivially true that minimum required range (zero) is less than 3.

Now let this claim be true for some tournament graph on n nodes. Then there exists a node x, such that every node other than x is either at a distance of 1 from x or at a distance of 2. We can partition all nodes into 3 sets, X(the optimum start node), D1(nodes at distance 1 from x) and D2(nodes at distance 2 from x).

alt text

Now, consider the n+1th node. If the edge between x and the n+1th node is from x to n+1 then we can put n+1 in D1 and minimum range is still at most 2.

Otherwise, consider all the nodes in D1. If any of them has an outgoing edge to n+1, then we can put n+1 in D2 and minimum range is still at most 2.

Otherwise, we can say that maximum distance from n+1 to any node is at most 2 since,

a) x is at a distance of 1 from n+1

b) all nodes in D1 are at a distance of 1 from n+1

c) all nodes in D2 are at a distance of at most 2 from n+1 (because of b)

Claim 2: The node with maximum outdegree (number of outgoing edges) always minimizes range.

Consider the case where minimum required range is 1. In that case, there exists some node such that it has an outgoing edge to every other node. This node will also have the maximum outdegree.

Consider the case where minimum required range is 2. Let the node with maximum outdegree be x. If there are many nodes with the maximum outdegree pick any one at random. Now, we can make 2 sets D1 and D2. In D1, we will put every node which is at a distance of 1 from X (i.e. number of nodes in D1 = outdegree of x). In D2, we will put all nodes which are at a distance of 2 from x. If we can show that all nodes are part of either D1 or D2, then we have successfully shown that x is a valid starting node. We will show this by contradiction.

Let there be some node y (y != x), such that y is not in D1 or in D2. This means that y has outgoing edges to x (otherwise y would be in D1) and every node in D1 (otherwise y would be in D2). But this means that:

outdegree of **y** >= 1 + outdegree of **x**

which means that x does not have the maximum outdegree, which is a contradiction. So we can safely say that there is no such y, which means all the nodes are at distance at most 2 from x.

So now, we can easily come up with the following solution:

  1. If n = 1, ans = 0, 1

  2. Find the node with maximum outdegree, say x. If max. outdegree = n-1, then ans = 1, x, else ans = 2, x.

ALTERNATIVE SOLUTION:

After proving claim 1, you could also use fast methods of matrix multiplication to get the answer by squaring the adjacency matrix of the tournament graph given.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.