Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

Pancake's blog

By Pancake, 8 years ago, In English

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
 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 :)

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey I'm a noob, please if you can help with the complete solution.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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