PROBLEM LINK:
Author: Soumik Sarkar
Tester: Subham Das
Editorialist: Soumik Sarkar
DIFFICULTY:
EASY
PREREQUISITES:
Graphs, Depth first search, Permutations
PROBLEM:
Find the longest trail in a graph where a character of the alphabet represents a vertex and provided words represent edges between the first and last characters of each word.
EXPLANATION:
The problem can easily be restated as the problem of finding the longest trail in a graph. Here each character represents a vertex, and a provided word represents an edge connecting its first letter to the last letter. Keep in mind that the graph is a directed graph.
The time limits for this problem were not strict to allow various approaches to pass.
One simple approach is using an exhaustive depth first search, we can explore all possible trails and simply choose the longest one as answer.
function dfs(u):
visited[u] = 1
longest = 0
for each v given edge u→v exists and not visited[v]:
trail_length = dfs(v)
longest = max(longest, trail_length)
visited[v] = 0
return 1+longest
We can run dfs(u) for all given strings considering them the starting point of the trail, and choose the maximum value as the answer.
The complexity of this approach is \mathcal{O}(n^2 2^n). Refer to the setter’s solution for implementation details.
AUTHOR’S SOLUTION:
Author’s solution can be found here.