MLIS - Editorial

editorial
, , ,
23

/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 ??
24

So dumb of me. Thank you so much :smiley:

25

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

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.

27

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.

28

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.

29

How is time Complexity NlogN?

30

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

31

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

32

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.

33

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

34

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?

35

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.

36

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

EDIT: Got it! NVM