GOSTONES-editorial

PROBLEM LINK:

Practice

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*[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*[a*]=1 and DP*[j]=0 for j!=a*. For all other nodes, DP*[j]=max(DP[v][j]) for all v adjacent to i, for every colour j. Also, we need to increment DP*[a*] 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.