CHRL3 - Editorial

PROBLEM LINKS

Contest

Practice

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

1 Like

I think the test data for this problem is really weak :

Many people have O(N^2) worst case complexity and still have got 100.

Solution

This solution worked in 0.60 seconds and fetched 100 points. If you look closely , this should not give more than 50 points as the worst case complexity of the algoritm is O(N^2) for those cases where the entire array is in decreasing order.

@Roman Furko.: Can you please tell me why did you set DP[1][7]=1 why 7? why not anything other than that?
Also in the second para of subtask1 editorial why are you using two n’s?(n and N)[ if it is an error please check it, as it will be of problem to beginners like me].

Why this O(n*log(n)) solution [CodeChef: Practical coding for everyone] is getting TLE on last test case?