Codeforces Round #165 (Div. 1) B. Greenhouse Effect
- Because Xi < Xi+1, for i in [1, N). The plants are given in order "from left to the right". So all of Xi values are not important in this problem. We can discard them.
- Now the problem is:
Given N numbers S[N]. Given a number M <= N. 1 <= S[i] <= N. Please divide the array into M sections numbered from 1 to M from left to right with i-th section contains all of the number i. Find the minimum number of numbers you need to reorder. Note that you can insert any number of numbers between two numbers without changing the two number's position.
Let me assume the result numbers are R[N]. Let's compare array R[N] and S[N]. We know that we can insert any number of numbers between any two numbers. So we can find the longest common subsequence of R[N] and S[N] are the numbers which remain their position. Besides, R[i] <= R[i+1], for i in [1,N). So the longest common subsequence is non-decreasing. So we can find the longest non-decreasing subsequence size of S[N]. We assume the sequence is L[K], K <= N. In other words, all of the numbers in L[K] remains their position in R[N]. So the minimum numbers we need to change their positions is N - K.
So key problem is to find the longest non-decreasing subsequence size of S[N].
The easiest algorithm is in O(N^2). However it got TLE in Perl.
So we need to use a more efficient algorithm. There is a O(N*logN) solution. We know there is O(NlogN) algorithm for the getting the size of longest increasing subsequence. We can change it a little bit to get the O(NlogN) algorithm for the non-decreasing version. Perl code is below:
About the solution to the O(NlogN) algorithm to get the size of longest increasing subsequence, see the link below.
