This problem can be solved by the following three steps. Firstly, change all the letters into lower case ones. Secondly, remove all the required letters. Thirdly, add “.” in front of each survived letter.
Take care of the number of spaces that should be output before each digit.
We can enumerate all the digits, and for each digit d, we replace several original digits so that there exist at least k digits which are the same. To achieve the minimum cost and also the minimum lexicographic order, we should replace digits in the order of d (this can be viewed as a trivial case), d + 1, d - 1, d + 2, d - 2, and so on. The replacement should be stopped once we have obtained k same digits.
To simplify the implementation, for each digit, we can also record how many of them should be replaced. Finally, we implement the replacment. However, here we should be very careful. Suppose that the original digit t is replaced with d. If t < d, then we should replace digit t from right to left; otherwise we should do it from left to right, so that we can achieve the minimum lexicographic order.
The solution is DP. Let us use a[n][m][e] to denote the number of all the feasible patterns that have e type-1 people standing at the end of the line one after another, while the total number of type-1 and type-2 people are n and m, respectively. Similarly, we use b[n][m][f] to denote the total number of feasible patterns that have f type-2 people standing at the end of the line.
The recursive formula is as follows:
The initialization should be done as follows:
a[0][m][m] = 1, for all m < k2
a[n][0][n] = 1, for all n < k1
We can start from any node, and implement DFS. During this process, when we are visiting a node a and enumerating its “child” (since this may not be its true child node) node b, if b is still not visited, we add a directed edge from a to b. If b has been visited but its “child” nodes are still not fully visited, then we add a directed edge from a to b as well. If b has been visited and all of its “child” nodes have also been visited, then we do nothing, since this edge must have been assigned with a “direction”.
After the above operations, we in fact have established a directed graph. Then, we check whether it is strongly connected or not, which can be done by inversing all the direction of the edges and implement DFS again.
The last step is to prove that if the above obtained directed graph is not strongly connected, then it is impossible to construct any strongly connected directed graph. Well, I did not figure out a strict proof. But from an intuitive understanding, if the constructed directed graph is not strongly connected, it implies that there is at least one bridge edge, and thus it is impossible to establish any strongly connected graph.
Comments (0)
