P17261 [ICPC 2017 Urumqi R] The Number Triangle

As the baby step for learning dynamic programming, the problem about number triangle is very symbolic. Here we will revisit this classic problem. By starting at any bottom of the triangle below and moving to adjacent numbers on the row above, the maximum total from bottom to top is $23$. $$ \begin{matrix} & & & 3 & & \\ & & 7 & & 4 & \\ & 2 & & 4 & & 6 \\ 8 & & 5 & & 9 & & 3 \end{matrix} $$ However, as a lonely outcome of the whole problem, the maximum total is not enough. Similarly, we are concerned with the trail. Consider the new triangle below and a corresponding letter triangle. The maximum total from bottom to top is $6$ passing through two “$2$”(s). $$ \begin{matrix} & & & 2 & & \\ & & 1 & & 1 & \\ & 2 & & 1 & & 1 \\ 1 & & 1 & & 2 & & 1 \end{matrix} $$ $$ \begin{matrix} & & & a & & \\ & & a & & b & \\ & b & & a & & a \\ b & & a & & b & & a \end{matrix} $$ A best trail can be written by connecting all corresponding letters in the trail consecutively as a string. Then in the above triangle, the lexicographically smallest best trail starting from the first position of the last row is “bbaa”. The lexicographically smallest best trail starting from the second position of the last row is “abaa”. The lexicographically smallest best trail starting from the third position of the last row is “baaa”. No best trail starts from the fourth position of the last row. Now, a program is required to determine all positions of the last row leading at least one best trail (a best trail starting from this position). Sort these possible positions by the lexicographical order of the lexicographically smallest best trails which they lead respectively.

The first line of input contains an integer $T (1 \le T \le 4)$, indicating that there are $T$ test cases. For each test case, the first line contains an integer $N (N \le 1500)$. The $i$-th line of the following $N$ lines describes the $i$-th row of the triangle with $n$ pairs of an integer and a lowercase letter. All integers in input are positive and smaller than $10$.

For each query, output a list of numbers in a line indicating the sorted list of possible positions. If two positions own the same lexicographically smallest best trail, output the one with a smaller index in priority order.