PROBLEM LINK:
Author: Shahjalal Shohag
Tester: Ildar Gainullin
Editorialist: Rajarshi Basu
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming, Longest-Increasng Subsequence, Segment trees
PROBLEM:
The longest increasing subsequence (LIS) of a sequence B_1, B_2, \ldots, B_L is the longest sequence of valid indices i_1, i_2, \ldots, i_k such that i_1 \lt i_2 \lt \ldots \lt i_k and B_{i_1} \lt B_{i_2} \lt \ldots \lt B_{i_k}.
You are given a sequence A_1, A_2, \ldots, A_N. You may modify it by performing the following operation zero or more times:
- Let K be the length of the LIS of the current sequence A.
- Choose a position in this sequence (possibly the beginning or end of the sequence) and insert a new element K into this sequence at this position.
- This way, the sequence A changes and the next operation is performed on this changed sequence.
Find the maximum length of the LIS of A that can be obtained after performing the given operation a finite number of times.
Constraints
- 1 \le T \le 10^5
- 1 \le N \le 10^6
- 1 \le A_i \le 10^9 for each valid i
- the sum of N over all test cases does not exceed 10^6
EXPLANATION
NOTE: For a brief explanation, just directly checkout Full Solution portion.
Observation 1
Let us say the LIS of the sequence A is of length K. That means in the first step, we need to add K to some index of our array, which we will think about later.
Observation 2
After we the aforementioned K to our array, if our length of LIS does not increase, then we will again need to add the same K, and it doesn’t really help us adding repeated numbers. So we need to ensure that the new number K actually increases the length of LIS.
The Most Important Fact about LIS that we use
The LIS of a sequence is not unique, but its length is unique.
I am putting this in bold so that the reader realises that there can be multiple different LIS for a particular sequence. This is crucial for the problem.
Observation 3
In particular, from our previous observations, we can conclude that if the number K is already present in our chosen LIS, then we cannot really extend this LIS anymore. In particular, we want to choose such a LIS in which the number K = Length of LIS, is not included. Then, we can actual extend our LIS. And we indeed can since we can add that element K to any place in our array.
Observation 4
It follows from the previous observation, that we can follow an inductive logic, and keep adding K, K+1,K+2 \dots and so on till X, where, in all the possible LIS ’s of the sequence, an element of value X is present. That means that adding the value X, which is the length of the LIS currently, will not increase the length of the LIS any more.
Reduced Problem
Hence, we are adding exactly (X-K) new elements to the LIS, for a LIS where the smallest value \geq K is X where K is the original length of the LIS. Hence, it makes sense to select such a LIS where X is maximised.
Inefficient Solution
A slightly inefficient solution for the problem would be the following :
- Find the value K, which is the length of the LIS.
- Binary search for the largest value X.
- To check whether the chosen value of X is possible or not, i:e, X_{chosen} \leq X_{optimal}, just delete all K \leq A[i] \leq X_{chosen}, and then check if LIS of this new sequence is equal to K or not.
- Assuming we can find LIS in O(NlogN) time, total complexity would have been O(Nlog^2N) overall.
Observation 5
- Let’s try to look a bit more closely at the LIS sequence. For a particular LIS , let us write the number of that LIS as B_1, B_2, \dots B_{k-1}, B_k.
- We can effectively divide it into two parts B_1,B_2, B_3 … B_i and B_{i+1}, B_{i+2} \dots B_k, where B_i \leq K and B_{i+1} = X.
- EXPL : Essentially, all values in the left part are less than the value K as we discussed earlier. Note that the length of the sequence is also K, hence we are trying to insert the value K.
How does breaking it into two parts like this help us?
Hint
Try to compute each part separately, and then try to maximise the value of X.
Full Solution
- First, for every value i, compute the length of LIS (of A[1 \dots i]) ending at A[i]. Denote this by End[i].
- Similarly, for every i, compute the length of LIS (of A[i \dots N]) starting at A[i]. Denote this by Start[i].
- Then, X = \max {A[j]} such that
- i<j,
- end[i] + start[j]=k,
- A[i] < k <A[j]
How to implement this?
To implement this:
- First calculate end[i] and start[i] using dp + Segment Tree. This should be similar to how we calculate LIS.
- Then, iterate over all values of i and if end[i], find j such that the given conditions hold. This can also be done with Segment trees in a variety of ways. Here is one such way. We keep a segment tree over an array Z[.] where Z[i] stores max value of A[j] such that start[j] = i and the j index has already been processed. Then, loop over i from N to 1, ie, in the reverse order. I will leave the rest upon the reader to figure out how this will ensure we can keep track of all the conditions mentioned above for a valid pair i and j.
- Time complexity for this solution is O(NlogN).
SOLUTION
Setter’s Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9, inf = 2e9;
struct ST {
int t[4 * N];
ST() {
memset(t, 0, sizeof t);
}
void build(int n, int b, int e) {
if(b == e) {
t[n] = 0;
return;
}
int mid = (b + e) >> 1, l = n << 1, r = l | 1;
build(l, b, mid);
build(r, mid + 1, e);
t[n] = max(t[l], t[r]);
}
void upd(int n, int b, int e, int i, int x) {
if(b > i || e < i) return;
if(b == e && b == i) {
t[n] = max(t[n], x);
return;
}
int mid = (b + e) >> 1, l = n << 1, r = l | 1;
upd(l, b, mid, i, x);
upd(r, mid + 1, e, i, x);
t[n] = max(t[l], t[r]);
}
int query(int n, int b, int e, int i, int j) {
if(b > j || e < i) return -inf;
if(b >= i && e <= j) return t[n];
int mid = (b + e) >> 1, l = n << 1, r = l | 1;
int L = query(l, b, mid, i, j);
int R = query(r, mid + 1, e, i, j);
return max(L, R);
}
}t;
int LIS(vector<int> a) {
set<int> se;
int n = a.size();
for (int i = 0; i < n; i++) {
auto it = se.lower_bound(a[i]);
if (it != se.end()) se.erase(it);
se.insert(a[i]);
}
return se.size();
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int tc; cin >> tc;
int sum = 0;
assert(1 <= tc && tc <= 100000);
while (tc--) {
int n; cin >> n;
assert(1 <= n && n <= 1000000);
sum += n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
assert(1 <= a[i] && a[i] <= 1000000000);
}
int k = LIS(a);
auto b = a;
b.push_back(k - 1);
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
auto c = a;
for (int i = 0; i < n; i++) {
c[i] = upper_bound(b.begin(), b.end(), a[i]) - b.begin();
}
t.build(1, 1, n + 1);
vector<int> suf(n);
for (int i = n - 1; i >= 0; i--) {
suf[i] = 1 + (c[i] == n + 1 ? 0 : t.query(1, 1, n + 1, c[i] + 1, n + 1));
t.upd(1, 1, n + 1, c[i], suf[i]);
}
t.build(1, 1, n + 1);
int ans = k, id = upper_bound(b.begin(), b.end(), k - 1) - b.begin();
for (int i = 0; i < n; i++) {
if (a[i] >= k) {
int cur = suf[i] + (k == 1 ? 0 : t.query(1, 1, n + 1, 1, id));
if (cur == k) {
ans = max(ans, a[i]);
}
}
if (c[i] <= id) {
int cur = 1 + (c[i] == 1 ? 0 : t.query(1, 1, n + 1, 1, c[i] - 1));
t.upd(1, 1, n + 1, c[i], cur);
}
}
cout << ans << '\n';
}
assert(1 <= sum && sum <= 1000000);
return 0;
}
Tester’ Code
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
const int inf = 2e9;
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector <int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector <int> d(n + 1, inf);
d[0] = -inf;
vector <int> pref(n);
vector <int> suf(n);
int lis = 0;
for (int i = 0; i < n; i++) {
int j = lower_bound(d.begin(), d.end(), a[i]) - d.begin();
pref[i] = j;
lis = max(lis, pref[i]);
d[j] = a[i];
}
d[0] = -inf;
for (int i = 1; i <= n; i++) d[i] = inf;
for (int i = n - 1; i >= 0; i--) {
int j = lower_bound(d.begin(), d.end(), -a[i]) - d.begin();
suf[i] = j;
d[j] = -a[i];
}
int mx = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
if (a[i] < lis) {
mx = max(mx, pref[i]);
} else {
if (mx + suf[i] == lis) {
ans = max(ans, a[i]);
}
}
}
cout << ans << '\n';
}
}