PROBLEM LINK:
Author: sriram10
Tester: sriram10
Editorialist: sriram10
DIFFICULTY:
MEDIUM
PREREQUISITES:
Graphs, depth first search (DFS), topological sort, dynamic programming (DP)
EXPLANATION:
Firstly, if there is a cycle, then the answer would be arbitrarily large, as you could keep returning to a particular vertex and collect stones of the same colour. To find if a cycle exists, you can run a DFS on the graph.
Otherwise, the graph becomes a Directed Acyclic Graph. Now, we compute the maximum score by using DP. We first topologically sort the vertices. The DP is computed this way: Let DP[i][j] indicate the maximum score when the player starts from i^{th} vertex and collects the stones of colour code j. Now, if i has no outgoing vertex, i.e. it is the leaf of topological sort, then DP[i][a[i]]=1 and DP[i][j]=0 for j!=a[i]. For all other nodes, DP[i][j]=max(DP[v][j]) for all v adjacent to i, for every colour j. Also, we need to increment DP[i][a[i]] by 1 after the previous process is done. Later, we could print the highest value in the DP table.
AUTHOR’S SOLUTION:
Author’s solution can be found here.