### Pancake's blog

By Pancake, 9 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 (3)
 » 6 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.
 » It's been 8 years so i dont know whether u got a your mistake or not. The only problem with your code is that it does not takes the input format correctly. In the problem you have to run it for 10 Test Cases. Just dont forget to reset the globals and code just works fine. BTW the logic was damn GOOD :XD