MLIS - Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Kartik Malik
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

DIFFICULTY:

Easy

PREREQUISITES:

Longest Increasing Subsequence

PROBLEM:

Chef received an array A of N integers as a valentine’s day present. He wants to maximize the length of the longest strictly increasing subsequence by choosing a subarray and adding a fixed integer X to all its elements.

More formally, Chef wants to maximize the length of the longest strictly increasing subsequence of A by performing the following operation at most once:

  • Pick 3 integers L, R and X \ (1 \leq L \leq R \leq N, \ X \in \mathbb{Z}) and assign A_i := A_i + X \ \forall \ i \in [L, R].

Find the length of the longest strictly increasing sequence Chef can obtain after performing the operation at most once.

EXPLANATION:

Let say that the Chef has chosen L, R and X, and have assigned A_i := A_i + X \ \forall \ i \in [L, R] to get the optimal answer. Also, assume that X \gt 0 for the current discussion. We will handle the other case later. So we can divide our array into three parts: A[1 \ldots L-1], A[L \ldots R], A[R+1 \ldots N]

Now, let say B = \{A_{i_1} \ldots A_{i_x}, A_{j_1} \ldots A_{j_y}, A_{k_1} \ldots A_{k_z} \} be the final LIS, such that i_u \in [1, L-1], j_u \in [L, R], k_u \in [R+1, N]. Observe that if we further increase all A_i for R \lt i \leq N, the length of resulting LIS will either remain same as that of B, or it will increase. In simple words, increasing all A_i for R \lt i \leq N only improves our solution.

So we can claim that if X \geq 0, we will only increase a suffix in the optimal case. If X \lt 0, we can have a similar analysis to show that we will only decrease the prefix, which is equivalent to increasing the remaining suffix by same amount, as long as LIS is considered. So, we only need to analyze X \geq 0, and R = N.

Let us now try to analyze what happens when we fix L. What is the maximum length of LIS that we can get. Now, we can divide our array into two parts: A[1 \ldots L-1], A[L \ldots N].

Let B_1 = \{A_{i_1} \ldots A_{i_x} \} and B_2 = \{ A_{j_1} \ldots A_{j_y} \} be the LIS of A[1 \ldots L-1] and A[L \ldots N] respectively. If we choose X in such a way that A_{i_x} \lt A_{j_1} + X, we can have our final LIS as B_1 + B_2, where the + sign denotes the concatenation. Observe that this is the maximum length of LIS that we can get for this specific L.

Hence, for each i such that 1 \leq i \leq N, we can first calculate dp_1[i] = Length of LIS of A[1 \ldots i] and dp_2[i] = Length of LIS of A[i \ldots N], and take the maximum of dp_1[i] + dp_2[i+1] for all valid i.

TIME COMPLEXITY:

To calculate length of LIS for each i, we will require O(N \cdot \log{N}) time. To further calculate answer, we will require O(N) time. Hence the overall time complexity is O(N \cdot \log{N}) for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution

3 Likes
2

Why the difficulty for this problem is mentioned as Cakewalk?
At least, mention it as a medium level problem.

13 Likes
3

Not sure if it is medium, I guess should be Easy at least, definitely not a cakewalk!

1 Like
4

Anyone having difficulty in understanding can checkout my explanation. Hope it will help

2 Likes
5

Sorry it was a mistake… Updated.

2 Likes
6

Can someone help me out in this code?

vector<int>a;
int n;
void solve()
{   
   cin>>n;
  a.clear();
  a.resize(n);
  for(int i=0;i<n;i++)
   cin>>a[i];

   int ans=0;
   int len1=1;
   int len2=1;
   int stop=0;
   for(int i=1;i<n;i++)
   {
       if(a[i]>a[i-1])
           len1++;
       else{
           for(int j=i+1;j<n;j++)
           {
               if(a[j]>a[j-1])
                   len2++;
               else{
                   ans=max(ans,len1+len2);
                   i=j-1;
                   len1=len2;
                   len2=1;
                   break;
               }
           }
           ans=max(ans,len1+len2);
       }
   }
   cout<<ans;   
}
7

solved it using fenwick tree kind of overkill . Btw cool problem here is my submission
https://www.codechef.com/viewsolution/60651061

1 Like
9

What will be its time complexity??

10

I tried using the concept of hashing to solve this problem.
First I mapped how an element is (> or < or == ) wrt to its’s prev element.
1 for increasing
0 for same
-1 for decreasing

Example: 1 2 4 3 9 7 16 12 5
Mapped: 1 1 1 -1 1 -1 1 -1 -1
Ans = 5

Example: 2 4 5 6 2 2 7 8 3 4 5 6 7
Mapped: 1 1 1 1 -1 0 1 1 -1 1 1 1 1
Ans = 7

The idea was to select the most extended sequence in this map which contains at most one -1 / 0.

Here is my code.

Kindly someone please point out mistakes in logic with the failed test cases.

12

N + nlogn + nlogN
where n is size of array and N size of tree which is 2e5
O(N) cause of memset
nlogn cause of compression as elements are larger than 2e5
and nlogN for finding the values using fenwick tree for every index

1 Like
13

You are finding longest strictly increasing subarray,I was doing the same mistake.

1 Like
14

Can anyone please help me, I am getting one test case wrong

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

int main() {
    ll t;
    cin >> t;
    while(t--) {
        ll n;
        cin >> n;
        vector<ll>arr(n);
        for(ll i = 0; i < n; i++) {
            cin >> arr[i];
        }
        
        vector<ll>dp(n),revdp(n);
        vector<ll>res;

        // dp1
        for(ll i = 0; i < n; i++) {
            if(res.empty() or arr[i] > res.back()) res.push_back(arr[i]);
            else *upper_bound(res.begin(),res.end(),arr[i]) = arr[i];
            dp[i] = res.size();
        }
        
        // dp2
        reverse(arr.begin(),arr.end());
        for(ll i = 0; i < n; i++) arr[i] = -arr[i];
        res.clear();
        for(ll i = 0; i < n; i++) {
            if(res.empty() or arr[i] > res.back()) res.push_back(arr[i]);
            else *lower_bound(res.begin(),res.end(),arr[i]) = arr[i];
            revdp[i] = res.size();
        }
        reverse(revdp.begin(),revdp.end());
        
        for(ll i = 1; i < n; i++) dp[i] = max(dp[i], dp[i-1]);
        for(ll i = n-2; i >= 0; i--) revdp[i] = max(revdp[i], revdp[i+1]);
        
        ll ans = dp[n-1];
        for(ll i = 0; i < n-1; i++) ans = max(ans, dp[i]+revdp[i+1]);
        
        cout << ans << endl;
    } 
    return 0;
}
15

When I was trying to solve this problem, I came up with some TCs and realized we can only increase the LIS once if the LIS of the original array is less than n(size of the array) i.e. if size of LIS(original arr) == n then ans is n else ans is (size of LIS(original array) + 1). But I guess this is wrong so can anyone give a testcase where the size of LIS is increased by more than 1 than the original LIS’s size?

16

A = [10 11 12 13 1 2 3]

take the last three elements of the array and add x = 100 to them, the new subarray becomes [10 11 12 13 101 102 103] and its LIS = 7, while LIS of original array was 4.

1 Like
17

Can anyone help me with the following code:
In the code I am traversing the array and storing the all the max length of subarrays that are in strictly increasing sequence into a list called lis. Then I am finding the max of sum of length of 2 consecutive subarrays in increasing sequence.
For example:

  1. if input array = [1, 2, 2, 1] then lis array = [2, 1, 1] as the subarrays with increasing sequence are [1,2], [2] and [1] and max of sum of 2 consecutive elements is 3.
  2. If input array = [1, 2, 4, 3, 9, 7, 16, 12, 5], then lis = [3, 2, 2, 1, 1] as the subarrays with increasing sequence are [1, 2, 4], [3, 9], [7, 16]. [12] and [5]. Then taking a max of sum of 2 consecutive elements which is 5 in this case.

But I am getting wrong answer for it although it passing the sample test cases. Please help me in understanding the incorrectness in logic/code.

tc = int(input())
for i in range(tc):
  n = int(input())
  arr = list(map(int, input().split()))
  lis = []
  count = 0
  for j in range(n):
    if j == 0:
      count += 1
    elif arr[j - 1] < arr[j]:
      count += 1
    else:
      lis.append(count)
      count = 1
  lis.append(count)
  max_sum = lis[0]
  for j in range(len(lis) - 1):
    if lis[j] + lis[j + 1] > max_sum:
      max_sum = lis[j] + lis[j + 1]
  print(max_sum)
1 Like
18

Can anyone please share some more problems where we can find the suffix array by multiplying the whole array with -1? Actually, I have never seen this thing before and I’m not getting the intuition behind this. I was also able to figure out the approach in the contest but was not able to find this suffix array.
Any kind of help will be appreciated.
Thanks in advance.

19

I have been doing the same, did you figure out why?

20

By suffix array, if you mean finding the LIS in A[i \ldots N], then you can do it as follows:
Reverse the subarray A[i \ldots N]. The longest increasing subsequence of A[1 \ldots N] is the longest decreasing subsequence of the reversed subarray. If you multiply the reversed subarray by -1, the same subsequence will now become the longest increasing subsequence of the reversed array.

2 Likes
21

I got it, thanks.
Can you share some more problems where we can use the same trick?

22

No. Still not able to figure out why the submission is giving incorrect answer.