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
You are finding longest strictly increasing subarray,I was doing the same mistake.
1 Like
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;
}
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?
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
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:
- 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.
- 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
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.
I have been doing the same, did you figure out why?
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
I got it, thanks.
Can you share some more problems where we can use the same trick?
No. Still not able to figure out why the submission is giving incorrect answer.
/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 ??So dumb of me. Thank you so much 
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;
}
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.
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.
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.
How is time Complexity NlogN?
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
Please either format your code or (better!) link to your submission - the forum software has mangled it and it won’t compile! 