×

# GOSTONES-editorial

Practice

Author: sriram10
Tester: sriram10
Editorialist: sriram10

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".

1
accept rate: 0%

19.8k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,657
×2,212
×733
×374
×28
×16
×2

question asked: 06 Jun '18, 20:58

question was seen: 235 times

last updated: 19 Jun '18, 11:43