MERGEDLIS - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Jeevan Jyot Singh
Tester : Takuki Kurokawa
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy

PREREQUISITES:

LIS, Observation

PROBLEM:

You have two arrays A and B of size N and M respectively. You have to merge both the arrays to form a new array C of size N+M (the relative order of elements in the original arrays A and B should not change in the array C).

Your goal is to maximize the length of longest non-decreasing subsequence of the merged array C.

QUICK EXPLANATION:

  • Find the length of longest non-decreasing subsequence in the array A.

  • Find the length of longest non-decreasing subsequence in the array B.

The answer to our problem is just the sum of both the above cases.

EXPLANATION:

LNDS = Longest Non- Decreasing Subsequence

  • Let’s say the length of the LNDS in the array A is l_1.

  • Let’s say the length of the LNDS in the array B is l_2.

Can the final answer be more than (l_1+l_2) ?

  • Since we are not allowed to change the relative order of elements of any of the given arrays. Hence it is never possible to get the array that is a combination of the given arrays having the length of LNDS more than (l_1+l_2).

It means the longest length we can get in our array is (l_1+l_2). Is it possible to get this maximum length irrespective of what arrays are given to us? Let’s see:

Suppose we have an array A of length N such that the length of the LNDS is l_1 and the elements of array contributing to this LNDS are in dark as shown below:

  • A[1], A[2] ,A[3], A[4] , A[5] ,A[6]......, A[N]

Similarly, say we have an array B of length M such that the length of the LNDS is l_2 and the elements of array contributing to this LNDS are in dark as shown below:

  • B[1] ,B[2], B[3] , B[4] , B[5] ,B[6]......,B[M]

Now let’s construct another array C which is just the combination of both the given arrays such that the relative order of elements is not changed. Let’s just focus on those elements which are part of the LNDS.

A' = A_2,A_4,A_5,....,A_N
B' = B_1,B_3,B_4,B_5....

Now as both the arrays A' and B' are sorted arrays, now we can simply merge both the arrays such that the resultant array is sorted. It can be done easily by the two-pointers technique. Suppose the resultant is:

A_2 \le B_1 \le B_3 \le A4 \le A_5 \le B4 \le A_N \le B_5 \le ....

Now just add the remaining elements in their given position and hence you will get the resultant array and the LNDS for that array will be l_1+l_2 such that the above elements are part of the given sequence.

Hence we can say that we can always get the length of LNDS as l_1+l_2.

LNDS can be found in NlogN time. You can refer to this for understanding and implementation.

TIME COMPLEXITY:

O(N*logN+M*logM) per test case

SOLUTIONS:

Author's Solution
#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int LIS(vector<int> &a)
{
    // lis[i] = element at which an increasing subseqeunce of lenght 'i' ends
    vector<int> lis; lis.reserve(a.size());
    for(auto &x: a)
    {
        auto it = upper_bound(lis.begin(), lis.end(), x);  // upper_bound for non-decreasing
        if(it == lis.end())
            lis.push_back(x);
        else
            *it = x;
    }
    return lis.size();    
}


void solve()
{
    int n, m; cin >> n >> m;
    vector<int> a(n), b(m);
    for(int &x: a)
        cin >> x;
    for(int &x: b)
        cin >> x;
    cout << LIS(a) + LIS(b) << "\n";
}

int32_t main()
{
    IOS;
    int T; cin >> T;
    for(int tc = 1; tc <= T; tc++)
    {
        solve();
    }
    return 0;
}
Tester's Solution
// tester solution for editorial. please remove this comment section.
#include <bits/stdc++.h>
using namespace std;

int lis(vector<int> x) {
    vector<int> y;
    for (int i : x) {
        auto iter = upper_bound(y.begin(), y.end(), i);
        if (iter == y.end()) {
            y.emplace_back(i);
        } else {
            *iter = i;
        }
    }
    return (int) y.size();
}

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n, m;
        cin >> n >> m;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        vector<int> b(m);
        for (int i = 0; i < m; i++) {
            cin >> b[i];
        }
        cout << lis(a) + lis(b) << '\n';
    }
    return 0;
}
Editorialist Solution
#include<bits/stdc++.h>
using namespace std;

int lis(vector<int> a) {

    int n = (int)a.size();
    vector<int> d;

    for (int i=0;i<n;i++)
    {
        auto itr = upper_bound(d.begin(), d.end(), a[i]);
        if (itr == d.end())
            d.push_back(a[i]);
        else
            *itr = a[i];
    }

    return d.size();
}

void solve()
{
  int n,m;
  cin>>n>>m;

  vector <int> a(n),b(m);

  for(int i=0;i<n;i++)
    cin>>a[i];

  for(int i=0;i<m;i++)
    cin>>b[i];

  cout<<lis(a)+lis(b)<<"\n";
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

6 Likes

Can any one tell me why this is not working?
https://www.codechef.com/viewsolution/56945486
I first created a new array C in such a way that the lesser number comes first and the order of A and B is maintained . After that I calculated the LNDS length in O(nlogn) in the new array.
Please provide some test-cases where this fails

#include <bits/stdc++.h>
#define int long long int
#define all(x) x.begin(), x.end()
using namespace std;

void solve()
{
	int n;
	int m;
	cin >> n >> m;
	int a[n];
	int b[m];
	int c[n + m];
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	for (int i = 0; i < m; ++i)
		cin >> b[i];
	int i = 0, j = 0;
	int index = 0;
	while (i < n && j < m)
	{
		if (a[i] < b[j])
		{
			c[index++] = a[i];
			i++;
		}
		else if (b[j] < a[i])
		{
			c[index++] = b[j];
			j++;
		}
		else
		{
			c[index++] = a[i];
			c[index++] = b[j];
			i++; j++;
		}
	}
	while (i < n)
		c[index++] = a[i++];
	while (j < m)
		c[index++] = b[j++];
	// for (int i = 0; i < n + m; ++i)
	// 	cout << c[i] << " ";
	// cout << endl;
	vector<int> d(n + m + 1, INT_MAX);
	d[0] = INT_MIN;
	int len = 0;
	for (int i = 0; i < n + m; i++) {
		int j = upper_bound(all(d), c[i]) - d.begin();
		if (c[i] < d[j]) d[j] = c[i];
		len = max(len, j);
	}
	cout << len << endl;


}

int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int tc = 1;
	cin >> tc;
	while (tc--)
		solve();

}

Thx a lot in advance !!!

Authors and setters Can you share the DP code for the same ??? I think it can be solved using DP as well .Its not easy to come up with such observation.

I wrote the recursive code for the same but couldn’t memoized it as 3D array was needed for the same as constraints were big .

My
// Recursive code for those who are interested in recursion …
[0/1 knapsack type]
Link:CodeChef: Practical coding for everyone

OR see Below

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

typedef long long ll;

#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mod 1000000007

ll fun(vector<int>&a , vector<int>&b ,ll inda,ll indb, ll prev)
{
   	if (inda >= a.size() && indb >= b.size()) 
   	{
		return 0;
	}
   
   	ll x = INT_MIN, y =INT_MIN,z = INT_MIN, w =INT_MIN;


   if(inda<a.size())
   {
       if(a[inda]>=prev)
       {
        x =  1+fun(a ,b,inda+1,indb,a[inda]);
       }

        w =  fun(a ,b,inda+1,indb,prev);
   }
   
   if(indb<b.size())
   {
        if(b[indb]>=prev)
       {
         y=  1+fun(a ,b,inda,indb+1,b[indb]);
       }

         z = fun(a ,b,inda,indb+1,prev);
   }
   
     return  max({x, y,z,w});


}


int main() 
{
FIO;

ll t;cin>>t;
while(t--)
{
    ll n,m;cin>>n>>m;
    vector<int>a(n);
    vector<int>b(m);

    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<m;i++)
    {
        cin>>b[i];
    }
    
    cout<< fun(a , b ,0,0,0)<<"\n";

}

}

https://cp-algorithms.com/sequences/longest_increasing_subsequence.html#solution-in-on-log-n-with-dynamic-programming-and-binary-search

1 Like

i used the same technique(in c), but it will give us wrong ans,
what if 2 arrays are
4,2,1
1,3
resulted array will be
4,1,2,3,1
and ans is 3
so in 1st case, 4>1( means A[i]>B[i]) but we saved 4 in C[i] not 1.
thats all in can find

What’s the problem in the following code, ig i’ve applied the exact same logic, but it wasn’t accepted though…

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve()
{
  ll n,m;
  cin>>n>>m;
  ll a[n],b[m];
  for(ll i=0; i<n; i++) cin>>a[i];
  for(ll i=0; i<m; i++) cin>>b[i];

  ll max1=1,len1=1;
  for (ll i=1; i<n; i++)
  {
    if (a[i]>=a[i-1]) len1++;
    else
    {
      if(max1<len1) max1=len1; 
      len1=1;   
    }
  }
  if(max1<len1) max1=len1;

  ll max2=1,len2=1;
  for (ll i=1; i<m; i++)
  {
    if(b[i]>=b[i-1]) len2++;
    else
    {
      if(max2<len2) max2=len2; 
      len2=1;   
    }   
  }
  if(max2<len2) max2=len2;
     
  cout<<max1+max2<<"\n";
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ll t;
  cin>>t;
  while(t--) solve();
}

Your approach of calculating LNDS is wrong.

No , answer is correct.
If the arrays are [4,2,1] and [1,3] the according to my solution C should be [1,3,4,2,1].
That way also answer is 3. Moreover , we have to find the length of the longest increasing subsequence and nothing else. The combined array can be anything.

Hey i wrote this code and followed the same approach but showing up wrong answer

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define mod 1000000007
signed main()
{
int t;
cin >> t;
while (t–)
{
int n,m;
cin>>n>>m;
int a[n+1],b[m+1];
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=m;i++)
cin>>b[i];
vectorv(n+1,1),w(m+1,1);
for(int i=2;i<=n;i++)
{
if(a[i]>=a[i-1])
v[i]+=v[i-1];
}
for(int i=2;i<=m;i++)
{
if(b[i]>=b[i-1])
w[i]+=w[i-1];
}
cout<<*max_element(v.begin(),v.end())+*max_element(w.begin(),w.end())<<endl;
}
}

Thnx a lot in advance

Got it .
It fails for
A = [4,2,3] , B = [3]
Correct Answer :- 3
My Answer :- 2
Thx

1 Like

It fails for the following case :
1
3 4
3 3 1
5 2 3 3

1 Like

You are calculating the longest continuous sequence of non decreasing whereas you need to calculate the longest subsequence. Please read the question once again.

Did you read the problem code as MADRIGALS or am I the only one who looped over Encanto’s songs for more times than I’m proud of ?

2 Likes

Yahh I too also came up with same solution but got wa what I didn’t get is if the ans is sum of 2 lis of arrays why the array which contains a and b after merging will not give the same lis length

I haven’t seen Encanto . Will society accept me ? :sneezing_face: :cry:

Consider the example A=[4,2,3] and B=[3]
Here for optimal answer B should come after A i.e [4,2,3,3] which gives LNDS length = 3
But if you merge it like that due to “4” , “3” comes before resulting in [3,4,2,3] . Hence giving answer 2

oh tysm, mb

Ig it’s because question is for LNDS and not LIS

So resultant will also have repeated numbers in answer [4,2,3,3]
2 3 3 will make here ans as 3

ok if lis(a) + lis(b) gives correct ans then c(merged a and b in any order(maintained order of elements)) should also give correct ans.
so why I am getting wrong ans : CodeChef: Practical coding for everyone

I am not able to find out the test case where this code gone wrong?

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

//longest nn decreasing subsequence
int lis(vector<int>&arr)
{
    int n = arr.size();
    const int INF = 1e9;
    vector<int>d(n+1,INF);
    d[0] = -INF;
    
    for(int i=0;i<n;i++)
    {
        int  j  = upper_bound(d.begin(),d.end(),arr[i]) - d.begin();
        // longest non decreasing subsequence
        if(d[j-1] <= arr[i] and d[j] >arr[i])
        {
            d[j] = arr[i];
        }
    }
    
    int ans = 0;
    for(int i=0;i<=n;i++)
    {
        if(d[i]<INF)
        {
            ans = i;
        }
    }
    return ans;
    
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
   
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        vector<int>a(n),b(m);
        
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
        }
        
        for(int i=0;i<m;i++)
        {
            cin>>b[i];
        }
        
        
        int x = lis(a);
        int y = lis(b);
        
        // cout<<x<<" "<<y<<" "<<x+y<<"\n";
        cout<<x+y<<"\n";
    }
    return 0;
}