Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

rahul_1234's blog

By rahul_1234, history, 3 years ago, In English,

Given an array A of n numbers, we want to select a sub-sequence of A such that each number in the sub-sequence is at least as large as the previous one, and such that the length of this sub-sequence is as large as possible. Give a divide-and-conquer algorithm for this problem. What is the running time of your algorithm?

I got this explanation but could not understand:

A natural algorithm is to divide the problem into n problems of size n/2, where for problems on the left, we compute the longest increasing subsequence ending at a given position, for the ones on the right we want to compute the longest increasing subsequence with a given element as the smallest. The recursion is therefore T(n) = nT(n/2) + O(1).

So please explain this to me. I'll be thankful to you.

 
 
 
 
  • Vote: I like it  
  • -12
  • Vote: I do not like it  

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

I don't understand this explanation as well. Moreover, it seems incorrect, as longest subsequence in the left is not neccessary to be the part of the longest subsequence of all sequence.

2 1 7 8 | 3 4 5 6

As you find 2 7, 2 8, 1 7 or 1 8 as a LIS for left part, you'll probably get WA since correct length is 5.

You can easily compute longest increasing subsequence with Fenwick or Segtree, but I doubt it's the case in your task.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have made a little edit in explanation, it would be n/2 and not n=2. Now can u plz see it again?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rahul_1234 (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I will use Miyukine's test to explain what I understood from the explanation: 2 1 7 8 | 3 4 5 6

Let's consider the first half — (2,1,7,8). We will find the longest increasing subsequence ending in each number (let's say L[i]). So L[2] is 1, L[1] is 1, L[7] is 2 and L[8] is 3.

Now similarly for the second half — (3,4,5,6), we will find the longest increasing subsequence starting in each number (let's say R[i]). So R[6] is 1, R[5] is 2, R[4] is 3 and R[3] is 4.

How to compute L, R? Well, L[X]=1+max(L[1],L[2],...L[X-1]) and R[X]=1+max(R[X+1],R[X+2],...,R[MAXVAL]). It can be done with a binary indexed tree in O(NlogN) or in O(N^2) using a naive algorithm.

What remains is to see how to get the answer for the sequence. It's quite easy, let's fix some index i on the left side. The answer for this index will be L[i]+max(R[A[i]+1],R[A[i]+2],...R[MAXVALUE]) and the whole answer will be the maximum among the answers for all indices. For example ANS[1] (index 1, not value) will be L[2]+R[3]=5, ANS[2] will be L[1]+R[3]=5, ANS[3] will be L[7]+0=1 and ANS[4] will be L[8]+0=1, so the final answer is 5 :)

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Okay thanks a lot for nice explanation. Can u plz tell how one can get recursion T(n) = nT(n/2) + O(1) from the above explanation?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Minor Correction: In the last paragraph, you meant L[A[i]] instead of L[i] probably

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Please somebody guide me how one will get the following recurrence relation T(n) = nT(n/2) + O(1) ?

»
3 months ago, # |
  Vote: I like it -18 Vote: I do not like it

I think its O(n^log(n)) which is really more than O(n^2)