You are not logged in. Please login at www.codechef.com to post your questions!

×

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[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

megabidoof's gravatar image

6★megabidoof
1
accept rate: 0%

edited 19 Jun '18, 11:43

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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