MLIS - Editorial

[alucard15]

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)

[shinigam_i]

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.

[eyeamkd]

@dahiyav007

10 11 12 13 1 2 3

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

[lavish_adm]

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.

[shinigam_i]

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

[alucard15]

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

[ayush1_20]

/Template Begins/

     // AYUSH

// Header Files
#include
#include
#include
#include
#include
#include
#include<unordered_set>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include<unordered_map>
#include<stdio.h>
#include
#include<math.h>
#include
#include
#include
#include “ext/pb_ds/assoc_container.hpp”
#include “ext/pb_ds/tree_policy.hpp”
// Header Files End

using namespace std;
using namespace __gnu_pbds;
template
using ordered_set = tree<T, null_type, less, rb_tree_tag, tree_order_statistics_node_update> ;

template<class key, class value, class cmp = std::less>
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;

#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define umap unordered_map
#define uset unordered_set
#define lb lower_bound
#define ub upper_bound
#define fo(i,a,b) for(i=a;i<=b;i++)
#define all(v) (v).begin(),(v).end()
#define all1(v) (v).begin()+1,(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define allr1(v) (v).rbegin()+1,(v).rend()
#define sort0(v) sort(all(v))
typedef pair<int, int> pii;
typedef vector vi;
typedef vector vll;
typedef pair<ll, ll> pll;
#define sz(x) (ll)x.size()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define inf 1000000000000000005
const ll mod = 1e9 + 7;

ll inv(ll i) {if (i == 1) return 1; return (mod - ((mod / i) * inv(mod % i)) % mod) % mod;}

ll mod_mul(ll a, ll b) {a = a % mod; b = b % mod; return (((a * b) % mod) + mod) % mod;}

ll mod_add(ll a, ll b) {a = a % mod; b = b % mod; return (((a + b) % mod) + mod) % mod;}

ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b);}

ll ceil_div(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;}

ll pwr(ll a, ll b) {a %= mod; ll res = 1; while (b > 0) {if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1;} return res;}
//Template Ends***//

int main() {

  fast;

ll t,n,i,j;
cin>>t;

while(t--) {
    
    cin>>n;
    
    ll a[n]; ll flag=0,ct=1;
    
for(i=0;i<n;++i)    {
      cin>>a[i]; } 
      
    ll x = *max_element(a, a+n); 
    
    for(i=1;i<n;++i) {
        
          if(a[i]<=a[i-1]) {
                flag++;
            for(j=i;j<n;++j) {   
                 a[j]+= x;
                 if(a[j]<=a[j-1])
                      break; 
                      
                    else ct++; }  }  
                
            else ct++;
            
              if(flag>0)
                  break; 
          } 
          
            cout<<ct<<'\n'; }
            
} 
            
      
// for which test case I am getting WA ??

[zeref_0464]

So dumb of me. Thank you so much

[adityatrivedi1]

Can anyone explain why is my code wrong for this question?
In my code I have divided the given array into sub arrays each of which is strictly increasing. Also while doing this I have ignored such elements which are equal and adjacent in given original array.
The lengths of sub arrays were stored in vector subsize.
Then I have calculated the maximum sum of size of two adjacent sub arrays, which is the final answer according to me.

#include <iostream>
#include <vector>
#include <algorithm>
typedef unsigned long long int ll;
using namespace std;

int find();
int main() {
    int t;
    cin >> t;
    vector<int> answer(t);
    for (int z=0; z<t; z++) {
        answer.at(z)=find();
    }
    for (auto z:answer) {
        cout << z << '\n';
    }
    return 0;
}
int find() {
    int n, count=1;
    vector<int> subsize;
    cin >> n;
    vector<ll> temp(n);
    for (int z=0; z<n; z++) {
        cin >> temp.at(z);
    }
    for (int z=1; z<n; z++) {
        if (temp.at(z-1)<temp.at(z)) {
            count++;
        } else if (temp.at(z-1)==temp.at(z)) {
            continue;
        } else {
            subsize.push_back(count);
            count=1;
        }
    }
    subsize.push_back(count);
    int ml=subsize.at(0);
    if (subsize.size()>1) {
        for (int z=0; z<subsize.size()-1; z++) {
            ml=max(ml, subsize.at(z)+subsize.at(z+1));
        }
    }
    return ml;
}

[nishan_adm]

Hey, there is a problem in your logic, it seems to work only on limited cases and fails for others.

Take this test case for example:

1
8
1 2 1 1 3 4 1 1

Here, the answer should be 5. How? if we take the elements on indexes 0,1, 4, 5, and then increase the indexes 6 by 4, it become 5, we get the length of our LIS as 5, but your code outputs 3.

[nishan_adm]

Here,

1
4
3 4 1 2

Considering the array to be 0 indexed, if we take L = 2 and R = 4 and X = 4.
After we apply the operation, the array becomes:

3 4 5 6

As you can clearly see, in this case(and many other cases like this) the LIS can increase more than 1.

[nishan_adm]

Hey, there is a fault in your logic, as the LIS formed can have multiple non-contiguous sub-parts, not just 2.

For example take this case:

1
9
1 2 1 1 3 4 1 1 9

Here, the answer should be 6. How? if we increase the indexes 6 by 4, it become 5 and we get the following array:

1 2 1 1 3 4 5 1 9

Here, we get the length of our LIS as 6

If you observe, the LIS here is composed of 3 different parts.

[lit_coder]

How is time Complexity NlogN?

[nishan_adm]

Hey, there is actually a method to calculate the LIS in NLog(N) complexity.
Since we calculate LIS in O(NLog(N)), and then traverse the array in order to compare and find the max ans in O(Log(N)), the overall complexity is O(NLog(N))

In case you don’t know the NlogN LIS algorithm, uou can learn it from here

[nishan_adm]

Please either format your code or (better!) link to your submission - the forum software has mangled it and it won’t compile!

[nishan_adm]

@jellyfish316

#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;
}

Hey, as per my observation, there are 2 things missing in your code

1. you forgot to consider the case where revdp[0] can be the answer.
   Simply adding ans = max(ans, revdp[0]); before printing solves the issue.

2. You need update the vallue of res using the lower_bound, not the upper_bound, as the sequence needs to be strictly increasing.

Here, I have submitted the updated code after correcting those errors.

[jellyfish316]

Hey, Thanks for looking into.
I missed it that I’ve used upper bound.
Changing it to lower bound works.

[aitrcse1088]

I somewhat understood the implementation but i still cannot wrap my head around this in your soln @lavish_adm
for(int i = 1 ; i < n ; i++)
v1[i] = max(v1[i] , v1[i-1]) ;
for(int i = n-2 ; i >= 0 ; i–)
v2[i] = max(v2[i] , v2[i+1]) ;
why did you do this?

[nishan_adm]

Hey, this is done so that v1[i] stores the LIS that can be chosen from the subarray ranging from index 0 to i, and not just the LIS that is formed only if the element at index i is chosen (as the classical LIS algo stores that only in its result). Same is for v2.

[hackapie]

Can somewhere check why my solution is failing ?
Submission:https://www.codechef.com/viewsolution/61912283

EDIT: Got it! NVM