PROBLEM LINKS
Author: Roman Furko
Tester: Sergey Kulik
Editorialist: Vinod Reddy
DIFFICULTY:
easy
PREREQUISITES:
longest increasing subsequence, dp, greedy
EXPLANATION
SubTask 1 :
In this task the number of elements in the sequence is less than or equal to 10 so we can use the fact to formulate a DP solution which is very easy to code. The algorithm runs in O(N*2^N) time.
Now we make a simple observation which will help to formulate our DP solution. First of all suppose we have a decomposition D of the first i elements into chains where D consists of Chains of the type A[i1]->A[i2]…A[ik1]. Now I want to add further elements but the process of addition of future element is only influenced by the last element of each chain and the elements which aren’t last doesn’t influence the addition process. In the chain above if we want to add an element A[p] to chain above we will check with only A[ik1]. So its important only to remember the last element of each chain.
So our DP state is of the type DP[i][j] where 1 <= i <= n and 0 <= j <= 2^N-1. Here the second dimension(j in DP[i][j]) represents the last elements of chains in decomposition of first i elements i.e if kth bit of j is 1 then kth element is the last element of some chain. So DP[i][j] = 1 means that there exists a decomposition D of first i elements into chains such that the last elements of the chains in D are the ones whose bits are set in j. If the bits set in j are (i1,i2,i3…ik) then there exists a decomposition D such that the last elements of chains are (A[i1],A[i2],A[i3]…A[ik]).
The following pseudo code calculates all the values in DP[][] array. First all DP[][] contains 0.To calculate DP[][] array we first set DP[1][6] to 1 and put the pair(1,1) in a queue. Now each pair(i,j) in the queue represents a pair for which partial decompositions exist and we take each of them and insert (i+1)th element in the decomposition and also queue them for further expansion. This will finally fill up the DP array. The following code is almost self explanatory.
calculate(){
for all i,j set DP[i][j] = 0.
set DP[1][7] = 1. // This is because after putting 1st element into decomposition the
bitmask will be 1
queue Q.
Q.push(pair(1,1)).
while Q is not empty{
pair(i,j) = Q.front();
Q.pop();
pair[] P = expand(i,j)
foreach(P as pair(i1,j1)){
Q.push(pair(i1,j1));
}
}
int minC = N;
for i in (1,2^N-1){
if DP[N][i] = 1 : minC = min (minC, No of bits set in i);
}
return minC.
}
expand(i,j){
pair[] P;
if i = N return P.
foreach bit k such that kth bit is set in j and A[k] < A[i+1]{
set kth bit in j to 0 and (i+1)th bit in j to 1.
P.push(pair(i+1,j)).
revert changes in j.
}
return P.
}
Subtask 2 and Subtask 3 :
We will look at 2 solutions for both these tasks. One greedy solution and other due to result of dilworth theorem from order theory.
Method 1:
In this solution we try to build the decomposition incrementally by adding the elements(in increasing order of index) to the decomposition in a greedy manner. When we add a element to the decomposition,out of all chains for which the present element can be added pick the one with the largest last element and add the present element to the end of the picked chain. The proof for the optimality of this algorithm can be argued using Induction.
Proof :
Let P be the decomposition given by our algorithm. For any complete decomposition Q let Qi be the partial decomposition obtained by removing elements from Q whose index is greater than Q.
We prove using induction that for every Pi(0 <= i <= n) there exists an optimal solution Q such that Pi = Qi. The base is P0 = Q0 which is obvious. let it be true for all i less than k. So Pk-1 = Qk-1. Now if Pk != Qk i.e A[k] goes in a different chain in Qk-1(let the chain Cx) than Pk-1(here the chain be Cy).The situation looks like in Q :
xth chain : Cx->A[k]->remaining_part1
yth chain : Cy->remaining_part2
Now we can exchange remaining_part2 with A[k]->remaining_part1 because Cy has the largest last element less than A[k]. So if we attach remaining_part2 with Cx the decomposition is still valid. After this operation Pk will be equal to Qk and the optimality of Q is not compromised. So by the induction there exists an optimal solution Q which will be equal to P.
Implementation :
Implementation part is easy as we maintain the last element of each chain. And at each step we find the largest element which is smaller than A[i] either by binary search(This will give O(N*lgN) solution or a linear search(This will give O(N^2) solution This doesn’t pass subtask 3).
In C++ we can use set to put the elements in a set and use upper_bound to find the largest element which is smaller than A[i]. See the editorialist’s solution for implementation
Method 2
We will not go into details here. The minimum number of non increasing sequences to remove is same the length of the longest decreasing sequence in the array. Refer to this answer on quora for more details.
We can simply find the length of the decreasing sequence using an O(n^2) DP refer to editorialist’s solution for this. You can solve this in O(n log n) using efficient techniques, refer to http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms. If you didn’t knew of this or can’t come up with this during the contest but are aware of segment trees you can use segment trees to come up with O(n log n) solution. See editorialist’s java solution for this approach it uses O(m + n log m) where m is the maximum value present in the array but it can be easily modified to O(n log n).
SOLUTIONS
Setter’s Solution: CHRL3.cpp
Tester’s Solution: CHRL3.cpp
Editorialist’s Solution: CHRL3.cpp CHRL3.java