Editorial for GFSSOC '15 Fall S5 - Raider
Submitting an official solution before solving the problem yourself is a bannable offence.
Alright, so this is by far the toughest problem in this contest. First we need to notice that a province is simply a Strongly Connected Component (SCC). Secondly, notice that if we loot from a province, might as well take everything there! Computing the SCC's will make your work a lot easier. So, we will find the SCC's, and the summed loot values for each component. This can be done using Kosaraju's or Tarjan's algorithm. After finding the SCC's, we should reconstruct the graph, which will become a Directed Acyclic Graph, and then suddenly doing DP on it is much easier. The DP part of this question is asking the classic maximum sum question (CCC 2015 S5 was also a variant of this), except it's on a graph, and we need to count the number of ways as well. To do this, we use DFS, keeping track of most loot we can grab at each node, and how many ways we can do it. Our state must be [node number, whether or not we want to take the loot at this province]. For example,
dp represents the maximum loot we can get at province 3 if we do not take the loot there. From this, the transition formula for max loot is quite simple:
for each node v that is reachable from node u: dp[u] = max(dp[v] + val[u], dp[u]) dp[u] = max(dp[v], dp[u])
To take care of number of ways, we simply add an extra condition to each case:
for each node v that is reachable from node u: if (dp[v] + val[u] > dp[u]) dp[u] = dp[v] + val[u] cnt[u] = cnt[v] else if (dp[v] + val[u] == dp[u]) cnt[u] += cnt[v] if (dp[v] > dp[u]) dp[u] = dp[v] cnt[u] = cnt[v] else if (dp[v] == dp[u]) cnt[u] += cnt[v]
The first case is if we will take from province ~u~, which means we can't take from any of its children. The second case is if we do not take from province ~u~, so we should take from its children. The key observation in handling the number of ways has the same idea as J5 - Nightmare-a-thon: Whenever we find a new best form child node ~v~, the new number of ways should be the number of ways that best value could be found at node ~v~. Whenever we find an equal best, we need to accumulate the number of ways instead.