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.