SUBLCS - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Longest increasing subsequence, Greedy

PROBLEM:

Given array A, determine the maximal possible longest common subsequence over all pairs of longest non-increasing and longest non-decreasing subsequences of A.

EXPLANATION:

Let P and Q be some longest non-increasing and longest non-decreasing subsequences of A respectively.

Claim: The longest common subsequence of P and Q can not contain two different numbers (that is, all terms of the LCS are the same).

Proof

Assume the contrary.

Then there exists some a,b\space(a\ne b) in the LCS. WLOG, let a<b.
If a appears before b in the LCS, since the LCS is a subsequence of P, a appears before b in P, a contradiction to the non-increasing property of P.
We can similarly show contradiction for the case where a appears after b.

Thus proved.

From the above claim, it is obvious that if the optimal LCS is comprised of integer x, then the number of times x occurs in both P and Q should be maximum (while still being some longest non-increasing and longest non-decreasing subsequence, respectively).

If c_x and d_x represent the maximum number of times x occurs over all P and Q respectively, the answer is then equal to

\max_{0\le i<N}(\min(c_{A_i}, d_{A_i}))
How do I compute these values?

We only discuss the steps to compute array c, since d can be computed in a similar fashion.

Let I[i] be the length of the longest non-increasing subsequence (from left to right) of A with A_i as it’s last term. Also, let IC[i] be the maximum number of times elements with value A_i can occur in this subsequence.

Similarly, let D[i] be the length of the longest non-decreasing subsequence (from right to left) of A with A_i as it’s last term. Let DC[i] be the maximum number of times elements with value A_i can occur in this subsequence.

Both these arrays can be computed in O(N\log N) each, using a slightly modified version of the longest increasing subsequence algorithm.

Then, the longest non-increasing subsequence that contains A_i has length I[i]+D[i]-1 (the -1 is because element A_i is double counted), and the maximum number of times elements with value A_i can occur is equal to IC[i]+DC[i]-1.

Finally (this step is important, since selecting A_i might not give the longest possible non-increasing subsequence of A), if I[i]+D[i]-1 is equal to the length of the longest non-increasing subsequence of A, update

c_{A_i} = \max(c_{A_i}, IC[i]+DC[i]-1)

TIME COMPLEXITY:

Calculating array c and d takes amortized O(N\log N), and calculating the answer from this takes O(N), making the total time complexity

O(N\log N+N)\approx O(N\log N)

per test case.

SOLUTIONS:

Editorialist’s solution can be found here.


Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

2 Likes

Nowadays link to the editorial is not published under the problem statement, had to search for it on discuss. I thought editorial wasn’t published yet.

5 Likes

I apologise, the mistake is mine.

The admin usually links the editorial to the problem once the contest gets over, but I hadn’t uploaded the editorial yet, so the admin’s work got delayed.

1 Like

could u tell me what’s wrong with this code? I guess it’s following the same idea as in your tutorial.

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>>findLIS(vector<int>arr,bool rev){
    
    if(rev)reverse(arr.begin(),arr.end());
    int n=arr.size();
    vector<int>maxlen(n),maxoccur(n);
    vector<int>dp;
    dp.push_back(INT_MIN);
    unordered_map<int,int>last;

    for(int i=0;i<n;i++){
        if(arr[i]>=dp.back()){
            maxlen[i]=dp.size();
            dp.push_back(arr[i]);
           
        }
        else{

             int index= upper_bound(dp.begin(),dp.end(),arr[i])-dp.begin();

             maxlen[i]=index;
             dp[index]=arr[i];
        }
         if(last[arr[i]] ){
                maxoccur[i]=maxoccur[last[arr[i]]]+1;
            }
            else{
                maxoccur[i]=1;
            }
            last[arr[i]]=i;
    }
    
    if(rev)reverse(maxlen.begin(),maxlen.end()),reverse(maxoccur.begin(),maxoccur.end());

    return {maxlen,maxoccur};

}

vector<vector<int>>findLDS(vector<int>arr,bool rev){
    	
        for(auto &num:arr)num=-num;
        return findLIS(arr,rev);
}

int main(){
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        vector<int>arr(n);
        for(int i=0;i<n;i++){
            cin>>arr[i];
        }
        // length of longest increasing subseq including ith element = LIS_LR[0][i]+LDS_RL[0][i]-1
        // occurence of ith element in longest subseq =LIS_LR[1][i]+LDS_RL[1][i]-1
        //length of longest decreasing subseq including ith element=LDS_LR[0][i]+LIS_RL[0][i]-1
        //occurence of ith element in longest decreasing subseq including ith el = LDS_LR[1][i]-LIS_RL[1][i]-1

        //..............code
        vector<vector<int>>LIS_LR=findLIS(arr,false);
        vector<vector<int>>LDS_RL=findLDS(arr,true);
        vector<vector<int>>LDS_LR=findLDS(arr,false);
        vector<vector<int>>LIS_RL=findLIS(arr,true);
        

        // find the longest increasing subseq max(LIS,LIS_LR[0][i]+LDS_RL[0][i]-1)
        //find the longest decreasing subseq max(LDS,LDS_LR[0][i]+LIS_RL[0][i]-1)
        
        //.........code
        int max_len_LIS=0,max_len_LDS=0;
        for(int i=0;i<n;i++){
            max_len_LIS=max(max_len_LIS,LIS_LR[0][i]);
            max_len_LDS=max(max_len_LDS,LDS_LR[0][i]);
        }
       
       
        
        //compute ans max(min(LIS_LR[1][i]+LDS_RL[1][i]-1,LDS_LR[1][i]+LIS_RL[1][i]-1)) //update only if including
        // this element makes LIS and LDS

        int ans=0;
        for(int i=0;i<n;i++){
            if((LIS_LR[0][i]+LDS_RL[0][i]-1 == max_len_LIS) && (LDS_LR[0][i]+LIS_RL[0][i]-1 == max_len_LDS)){
                ans=max(ans,min(LIS_LR[1][i]+LDS_RL[1][i]-1,LDS_LR[1][i]+LIS_RL[1][i]-1));
               
            }
        }
       cout<<ans<<endl;
    }
}

plzz help me find a test case where its going wrong