PROBLEM LINK:Author: 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.
This question is marked "community wiki".
asked 06 Jun '18, 20:58
