A straightforward string implementation problem.
The main idea is dfs with memorization, which can also be viewed as an exhaustive tree search with pruning.
We can use dp[a][b][c][d] to denote the state, where a is the number of remaining cards, b, c, d denote the “results” of the rightmost three cards, i.e., the card's value and suit. Note that these four dimensions are sufficient to define a state. The reason is that no matter how we reach the state, all the a - 3 cards except for the current rightmost three ones keep the initial values and suits. Therefore, given a, b, c, d, the remaining cards always lead to the same result. According to the above arguments, we can run dfs to check the final answer, while memorizing the results of intermediate states and directly returning these results if we visit them for multiple times.
The framework is Floyd algorithm. In conventional Floyd algorithm, we calculate the minimum distance dis[u][v]. As an extra “bonus”, we can also compute the number of different paths which all have the minimum distance as cnt[u][v]. When an intermediate node k is checked to update dis[u][v], if dis[u][v] > dis[u][k] + dis[k][v], then we set cnt[u][v] = cnt[u][k] × cnt[k][v]; if dis[u][v] = dis[u][k] + dis[k][v], then we set cnt[u][v] = cnt[u][v] + cnt[u][k] × cnt[k][v]. The term cnt[u][k] × cnt[k][v] means that we have cnt[u][k] ways to reach node k while cnt[k][v] ways to leave node k, and thus this is a straightforward combination.
Finally, we check all the intermediate nodes except for node-1 and node-n, so that dis[1][n] = dis[1][k] + dis[k][n] and 2 × cnt[1][k] × cnt[k][n] / cnt[1][n] has the maximum value. Note that if k = 1 or n, the value is always cnt[1][1] × cnt[1][n] / cnt[1][n] = 1. For intermediate nodes, we have a coefficient 2 since it is an “intermediate” node and it contributes two edges within every shortest path.
208D - Prizes, Prizes, more Prizes
Straightforward implementation.
I think this is a very nice problem for one to gain more understanding about what dfs can do.
If one is familiar with the classical LCA (lowest common ancestor) problem, recall that there is a very clever algorithm which adopts the “timestamp” idea to solve it. For this problem, we implement dfs, and maintain several arrays to store some important “information”. We use depth[u] to denote the depth of node u; timestamp[u] to denote the timestamp of node u, i.e., the time at which this node is visited during dfs; revtimestamp[t] to denote the node that is visited at time t; lefttimeborder[u] and righttimeborder[u] to denote the earliest and latest timestamp of all the children nodes of u, respectively; samedepth[d] to store all the timestamp of nodes with depth d.
Next, we should solve two subproblems.
The first one is to find the p-th parent of given node v. Note that the target node must have been included in samedepth[depth[v] - p], or to be more exact, its timestamp is included there. Moreover, the timestamp of the p-th parent must be the minimum one which is larger than timestamp[v]. Thus, we can use binary search to find its timestamp and then use revtimestamp[u] to get its node index, denoted as pu.
The second subproblem is to find the number of nodes which have the same p-th parent. These nodes must be included in samedepth[depth[v]], and they (their timestamps) must fall into the interval [lefttimeborder[pu], righttimeborder[pu]]. Therefore, we can use binary search again to find out the answer.
As s summary, this is a very excellent problem and it sheds light on the power of dfs and timestamp idea.
Comments (0)
