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.
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:
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;
}