This is a very tricky problem... For instance, given RRL, my first solution will output 1 2 3 2, however it is obvious that a better sequence 1 2 3 1 exists.
For each integer, we have known that it must be at least 1. However, the "L" letters on its right side mean that it should be some larger integer. Thus, we should count the number of "L" on its right side until a "R" is met (note that we should continue if any "=" is met but this is not counted) or arrive at the end, which is denoted as nL. Similarly, we count the number of "R" on its left side until a "L" is met or reach the starting position, which is denoted as nR. The value of this integer is thus max(nL, nR).
For an intuitive understanding, nL implies that there are exactly nL integers on its right side, which are smaller, and thus it must be at least as large as nL.
67B - Restoration of the Permutation
We can check array b[ ] from left to right, and find the first element that is 0. Suppose that we are trying to restore a[i], and find b[j]=0. It means that the number of integers to the left of "j" which are larger than "j+k" is zero (the indices are counted from 1). Thus, we can set a[i]=j. Next, we should enumerate array b[ ] again, and for each b[j], if a[i] is no less than "j+k", we should decrease b[j] by 1. The total complexity is O(N^2).
However, in fact, I do not know why the above algorithm works... i.e., why it will give the optimal answer...
I think this is a very nicely designed problem!! The solution turns out to be clear, if we replace the indices upside from left to right by 0,1,2,..., i.e., "remap" them to a naturally increasing order, while the indices downside should be "remapped" correspondingly.
After the above operations, we in fact have obtained two sequences, one of which is in an naturally increasing order, denoted as a[n] (a[1]=1, a[2]=2,...,a[n]=n), while the other one can be viewed as a permutation sequence of the first one, denoted as p[n]. Suppose that rays with indices i<j<k (these indices are in a[n]) intersect with each other. This means that if b[x]=i, b[y]=j, b[z]=k, we must have x>y>z. In other words, we can always find some z<y<x so that
b[z]>b[y]>b[x]
It can be seen that the original problem in fact has been converted to an equivalent one, which asks to find out the longest decreasing sub-array in array b[n]. One can find a lot of information about this classic and well investigated problem on the Internet. To avoid Time Limited Error, one should adopt the algorithm with complexity O(NlogN).
Comments (0)
