### Pancake's blog

By Pancake, 7 years ago, , Hello I'm trying to solve problem SUPPER from SPOJ. I think a number x[n] is defined to be super if length of LIS[n] (longest increasing subsequence ending at x[n]) plus LDC[n] (length of longest decreasing subsequence ending at x[n] , when reading the input permutation in reverse) equals the length of longest increasing subsequence of the entire input permutation . Solution Complexity is O(N log N). I'm using Segment Tree , suppose node n covers interval [i .. j] , then tree[n] = max { LIS [ x [ i ] ] , LIS [ x [ i + 1 ] ] , ... , LIS [ x [ j ] ] }

I used an O(N^2) solution to compare my answers against. Thanks a lot in advance for any help.

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;

const int MAXN = 100001;
int N;
int x[MAXN];
int LIS[MAXN];
int LDS[MAXN];
int lis[MAXN];
int lds[MAXN];
int tree[4 * MAXN];
int best;

int query(int node , int s , int e , int qs , int qe){
if(s > qe || e < qs)
return 0;
if(s >= qs && e <= qe)
return tree[node];
return max(query(2 * node , s , (s+e)/2 , qs , qe) , query(2 * node + 1 , (s+e)/2+1, e , qs , qe));
}
void update(int node , int s , int e , int idx , int val){
if(s == e && s == idx){
tree[node] = val;
return;
}
if(s > idx || e < idx)
return;
update(2 * node , s , (s+e)/2 , idx , val);
update(2 * node + 1 , (s+e)/2 + 1 , e , idx , val);
tree[node] = max(tree[2 * node] , tree[2 * node + 1]);
return;
}

int main(){
scanf("%d" , &N);
for(int n = 1 ; n <= N ; n++)
scanf("%d" , &x[n]);
for(int n = 1 ; n <= N ; n++){
LIS[n] = 1 + query(1 , 1 , N , 1 , x[n] - 1);
update(1 , 1 , N , x[n] , LIS[n]);
best = max(best , LIS[n]);
}
memset(tree , 0 , sizeof(tree));
for(int n = N ; n >= 1 ; n--){
LDS[n] = 1 + query(1 , 1 , N , x[n] + 1 , N);
update(1 , 1 , N , x[n] , LDS[n]);
}
vector < int > res;
for(int n = 1 ; n <= N ; n++){
// printf("%d %d\n" , LIS[n],LDS[n]);
if(LIS[n] + LDS[n] - 1 == best)
res.push_back(x[n]);
}

/*
for(int n = 1 ; n <= N ; n++){
lis[n] = 1;
for(int h = 1 ; h < n ; h++)
if(x[n] > x[h])
lis[n] = max(lis[n] , lis[h] + 1);
}
for(int n = N ; n >= 1 ; n--){
lds[n] = 1;
for(int h = N  ; h > n ; h--)
if(x[n] < x[h])
lds[n] = max(lds[n] , lds[h] + 1);
}
printf("\n\n");
for(int n =  1 ; n <= N ; n++)
printf("%d %d\n" , lis[n] , lds[n]);

*/

sort(res.begin() , res.end());
printf("%d\n" , res.size());
for(int i = 0 ; i < (int)(res.size()) - 1 ; i++)
printf("%d " , res[i]);
printf("%d\n" , res.back());
return 0;
}



Example test case :

Input :
25
19 6 7 11 5 9 8 18 14 4 23 1 13 10 25 2 16 3 12 15 21 17 20 22 24

Output (by both O(N log N) and O(N^2) solutions):
11
6 7 8 9 10 12 15 17 20 22 24  Comments (2)
 » 4 years ago, # | ← Rev. 2 →   lol I've just solved that problem and I think you've only over-complicated the task. Do you really need LDC[ x ]? And why do you use a segment tree when it is slower and worse to code than a BIT? After calculating the LIS terminating at every indexyou can just find super numbers in linear time.Hint: Suppose you're at index i of the array A and you already know that number A[ j ] (where j>i) is a super number. What can you say about A[i], looking at A[i], A[j], Lis[j] and Lis[i] ? Try on paper, I found algorithm in that way :)
•  » » Hey I'm a noob, please if you can help with the complete solution.