As the input only contains positive integers, it is sufficient to just consider the right border of each type, and we can store them as strings. Similarly, the input should be stored as a string as well. Then, we compare the input with the right borders from small to large. For each border, if the length of the input is smaller, this type is just the answer, while if they have the same length, then we can compare them using the "string comparison".
A straightforward solution has complexity O(N^2). We check every element, and find the longest non-increasing sub-arrays that both start from this element but extend to the right and left direction. Then, we add their length together, and the answer is just the maximum one. In fact, the longest non-increasing sub-arrays mentioned above can be computed with complexity O(N) in advance, and thus an improved solution has linear complexity.
For any n that is larger than 2, the required sequence always exists. One feasible sequence is 3*2, 5*2, 3*5, 3*2*2, 3*2*2*2, 3*2*2...*2.
This is really a well designed problem. One can check http://codeforces.com/blog/entry/1452 for more details. I think the most tricky part is that
(a1+a2+...an)-(b1+b2+...bn)=0
Thus, we have
0-(a1-b1)=(a2+a3+...an)-(b2+b3+...bn)
which is just the metric calculated if we start from position a2.
Comments (0)
