PROBLEM LINK:
Practice
Author: Jatin Yadav
Tester: tncks0121
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Graph Theory
PROBLEM:
Define a beautiful walk in a directed graph as a walk that contains all the vertices atleast once and has \leq \frac{n^2}{4} edges. Given a directed graph G, find a beautiful walk in it or claim that no such walk exists.
EXPLANATION:
Define a covering walk as one that contains all vertices at least once.
Consider the SCC DAG (each strongly connected component condensed into a single vertex) for this directed graph.
In the topological ordering, there must be an edge from component i to component i + 1 for each i, otherwise one can not come back to i + 1 after they have left component i.
We claim that this condition is also sufficient for there to exist a beautiful walk.
First, say the graph was strongly connected. Consider a walk which first traverses its diameter and then visits each unvisited vertex one by one. Let d be the diameter. It takes d edges to traverse the diameter, and then \leq d edges each for the unvisited nodes. Since there are n - 1 - d unvisited vertices, the total number of edges in this walk is \leq d + (n - 1 - d)d = d(n - d) \leq \frac{n^2}{4}.
Let the walk found above be w_1, w_2, \ldots, w_l.
Now, say we had to find a covering walk in an SCC that starts at a given node s. We claim that this can be done in \leq \frac{(n + 1)^2}{4} - 1 edges. If there is a diameter starting at s, we can use that to find a walk with \leq \frac{n^2}{4} edges.
Else, there is a path from s to w_1 with < d edges. So, prepending this path to our walk w_1, \ldots w_l, we have the total length \leq d - 1 + d + (n - 1 - d)d = d(n + 1 - d) - 1 \leq \frac{(n+1)^2}{4} - 1 edges.
Similarly, if we have to find a covering walk ending at a given node t, we can also do that in \leq \frac{(n + 1)^2}{4} - 1 edges.
If we have to find a covering walk starting at a given node s and ending at a given node t, we can do it in \leq \frac{(n+2)^2}{4} - 2 using a similar logic( Prepend s - w_1 walk and append w_l-t walk. If anyone of these has a length d, we can use that instead of original walk, else we have \leq 2(d-1) + d + (n-1-d)d \leq \frac{(n+2)^2}{4} - 2 edges).
Now, say we had k \geq 2 SCCs in the graph, in a chain, having sizes x_1, x_2, \ldots x_k.
Find any starting and ending nodes in the middle SCCs. Clearly, the first and the last SCC have a constraint on one end of the walk whereas the middle SCCs have a constraint on both endpoints. So, from the previous conclusions, our walk has a maximum of :
\dfrac{(x_1+1)^2}{4} - 1 + \dfrac{(x_k+1)^2}{4} - 1 + \displaystyle \sum_{i=2}^{k-1} \left ( \dfrac{(x_i + 2)^2}{4} - 2 \right ) + k - 1
edges.
We know that the sum of squares is maximized when the sum is concentrated around one variable. So, the worst possible cases we need to consider are x = (n - 1, 1) and x = (1, n - 2, 1). In both of these cases, the above value comes out to be exactly \lfloor \frac{n^2}{4} \rfloor.
The overall complexity is O(nm) as we do a bfs in every SCC from all of its nodes to find the required paths.
AUTHOR’S SOLUTION:
Author’s solution can be found here