10534 - Wavio Sequence

[erfan]

So try now..

[erfan]

Do u think it is correct?

Code: Select all

for (i = 1; i <= n; i ++) { 
         if (left[i] == right[n+1-i] && left[i] > mx) mx = left[i]; 
      } 

I think no.
It should be like

Code: Select all

mx=0;
for(i=1;i<=n;i++)
{
         if((left[i]<=right[i]) && (left[i]>mx))mx=left[i];
         if((left[i]>=right[i]) && (right[i]>mx))mx=right[i];
}

Why it should ,i think u can understand now..ok.
Hope this will be help.

[Zhou Yiyan@SHU]

Finally I got accepted...
Yeah, you are right about that.
I didn't understand the problem statement clearly.
Thank you for the help.

[jackie]

USACO GATE has a wonderful article on this subject. I read it and got AC in 0.7 sec use O(n*m) DP algorithm (m is the lengest increasing subsequce).

The best algorithm maybe O(n * lg(m)), but when i use lower_bound to do the binary_search i got AC in almost 1 sec. (Maybe special for the

test data on the judge )

test data in debugging (generated randomly)

input:

5
8 5 2 4 10
8
5 6 7 2 6 10 6 5
8
6 3 10 6 10 5 8 7
7
3 9 5 5 7 7 9
8
1 3 1 3 7 5 10 9
2
6 10
7
4 1 8 1 6 8 4
6
10 9 10 1 2 9
4
9 5 3 2
9
9 6 8 7 8 4 1 10 10
3
8 6 6
3
1 7 4
8
5 3 5 3 2 1 6 1
6
10 7 10 3 9 9
6
2 5 8 2 2 1
1
2
10
9 9 4 1 8 4 6 2 3 8
4
8 7 10 6
8
4 9 10 8 4 10 2 2
9
5 8 5 8 9 6 4 2 9
9
9 8 6 4 9 6 1 3 6
2
5 5
5
9 3 2 5 2
3
7 10 5
4
3 2 4 10
7
5 5 6 8 4 5 4
9
8 8 7 5 9 10 9 7 10
2
5 1
10
1 3 6 3 4 9 4 6 7 4
2
7 7
3
4 6 3
10
7 4 4 10 6 8 4 2 6 9
1
10
6
7 3 7 2 2 5
8
3 7 5 9 4 5 5 7
5
8 5 7 5 6
4
8 4 1 5
3
7 4 1
1
4
2
1 10
6
3 8 1 3 5 10
9
8 10 7 1 5 1 6 10 7
7
3 9 10 9 7 4 8
10
4 4 5 1 6 1 9 4 2 9
4
3 10 7 3
8
2 8 7 5 4 2 5 3
6
10 9 4 4 3 6
8
7 5 5 8 6 4 3 2
5
1 7 10 1 2
5
10 2 9 4 8
6
8 6 10 3 8 3
1
2
2
9 10
2
1 3
2
4 3
5
6 5 2 2 2
5
8 7 5 5 9
10
1 4 1 3 6 8 5 4 8 9
10
6 9 1 8 9 4 4 2 6 9
2
7 6
3
3 9 5
10
9 1 9 3 8 8 10 7 5 9
1
8
8
10 8 4 10 10 6 1 2
8
9 6 6 5 10 6 6 6
2
9 8
2
10 9
2
4 3
5
2 8 6 10 5
2
3 7
3
7 9 3
10
2 7 5 3 2 6 3 2 1 10
6
8 4 3 2 2 2
3
8 9 3
4
6 6 2 2
9
3 4 5 6 10 6 7 8 1
4
3 10 4 6
2
2 7
3
3 2 4
10
10 10 4 3 6 1 3 6 1 5
9
10 5 1 1 10 2 8 3 1
3
3 10 3
9
6 6 3 2 9 3 4 1 1
10
8 9 2 6 1 5 1 3 1 9
5
5 6 9 2 9
6
3 5 2 3 6 10
7
1 10 2 3 1 7 6
9
2 6 10 7 7 8 9 8 9
6
10 3 3 5 10 6
5
3 1 6 3 8
3
1 10 9
4
1 5 3 2
5
1 5 5 10 10
3
8 6 8
1
7
10
7 8 5 7 10 8 3 8 1 9
2
5 10
5
5 4 6 8 6
8
10 5 5 1 9 1 10 5
9
1 9 2 8 3 10 10 4 5

output

1
5
5
3
3
1
3
3
1
5
1
3
3
3
5
1
3
3
5
5
3
1
3
3
1
5
5
1
5
1
3
5
1
3
3
3
1
1
1
1
3
3
5
5
3
3
1
3
3
3
3
1
1
1
1
1
1
5
5
1
3
5
1
3
3
1
1
1
3
1
3
5
1
3
1
5
3
1
1
3
5
3
3
3
3
3
3
5
3
3
3
3
1
1
1
5
1
3
3
3

[kjw0612]

I have absolutely no idea why this code causes Compiler Error when I submitted.

There was no error when I compiled on my computer, though.

There's one more question. Is there any way to pre-compile using the same environment as Valladolid to make sure it doesn't have compiler error?

this is for 10534

#include <stdio.h>

int max(int x, int y)
{
return (x > y) ? x : y;
}
int min(int x, int y)
{
return (x < y ) ? x : y;
}

int n, arr[10000], arr2[10000], arr3[10000];

void process(int *table)
{
int temp[10000], len = 0, i;
int left = 0, right = len - 1, mid;

temp[0] = arr[0]; len = 1; table[0] = 1;
for(i = 1; i < n; i++)
{
if(temp[len - 1] < arr) { temp[len++] = arr; table = len; }
else if(temp[0] >= arr) { temp[0] = arr; table = 1; }
else
{
left = 0; right = len - 1;
while(1)
{
mid = (left + right) / 2;
// cout << left << " " << right << " " << mid << " " << temp[mid - 1] << " " << temp[mid] << " " << arr << endl;
if(temp[mid - 1] < arr && temp[mid] >= arr) { temp[mid] = arr; table[i] = mid + 1; break; }
else if(temp[mid] > arr[i]) right = mid - 1;
else left = mid + 1;
}
}
}
}

int main(void)
{

int i, t;
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; i++)
scanf("%d", &arr[i]);

process(arr2);
for(i = 0; i < n / 2; i++)
{ t = arr[i]; arr[i] = arr[n - 1 - i]; arr[n - 1 - i] = t; }
process(arr3);
int sol = 0;
for(i = 0; i < n; i++)
sol = max(sol, min(arr2[i], arr3[n - i - 1]));
printf("%d\n", 2 * (sol - 1) + 1);
}

return 0;
}

[Krzysztof Duleba]

Please provide more info, like what error message did you exactly received.

[little joey]

You can't comment out lines using slashes (//) in pure C like the judge uses. You can only use the standard /* ... */ method, or submit your code as a C++ program.

I don't know the exact command line options that the judge uses, but you can find them somewhere on this board.

[Minilek]

i used to get compiler errors (would compile on my machine but not the judge's), but i started seeing the compile errors the judge sees after using the following command line:

gcc -pedantic -ansi -Wall <source code file name>

hope it helps you as much as it has helped me

[TISARKER]

The following code gives wrong answer.please Help me.
u can give some test input

#include<stdio.h>
#define type long
#define range 10010
type binary_search(type x[range],type item,type beg,type end);
type lis_left(type *val,type *len,type *path,type n);
type lis_right(type *val,type *len,type *path,type n);
type max(type a,type b);
type min(type a,type b);
void main()
{
type i,n,maxlen,data[range],left[range],right[range],path[range];
//clrscr();
//freopen("F:\\input.txt","r",stdin);
//freopen("F:\\myput.txt","w",stdout);

while(scanf("%ld",&n)==1)
{
maxlen=0;
for(i=0;i<n;i++) scanf("%ld",&data[i]);
lis_left(data,left,path,n);
lis_right(data,right,path,n);
for(i=0;i<n;i++)maxlen=max(maxlen,min(left[i],right[i]));
printf("%ld\n",(2*maxlen)-1);
}

}


type max(type a,type b)
{
if(a>b)return a;
else return b;
}


type min(type a,type b)
{
if(a<b)return a;
else return b;
}

type lis_left(type *val,type *len,type *path,type n)
{
type backup_val[range],backup_pos[range],location=0,i=1,j,maxlen=0,pos;
if(n<1)return -1;
*(backup_val+0)=*(val+0);*(backup_pos+0)=0;
*(len+0)=1;*(path+0)=-1;
while(i<n)
{
if(*(val+i)>*(backup_val+maxlen))
{ maxlen++;pos=maxlen; }
else pos=binary_search(backup_val,*(val+i),0,maxlen);

*(backup_val+pos)=*(val+i); *(backup_pos+pos)=i;
*(len+i)=pos+1;
if(pos>0)*(path+i)=*(backup_pos+pos-1); else *(path+i)=-1;
location=*(backup_pos+maxlen);
i++;
}
return location; //return the last position from which data will start
}


type lis_right(type *val,type *len,type *path,type n)
{
type backup_val[range],backup_pos[range],location=n-1,i=n-1,j,maxlen=0,pos;
if(n<1)return -1;
*(backup_val+0)=*(val+i);*(backup_pos+0)=i; *(len+i)=1; *(path+i)=-1;
while(i>0)
{
i--;
if(*(val+i)>*(backup_val+maxlen))
{ maxlen++;pos=maxlen; }
else pos=binary_search(backup_val,*(val+i),0,maxlen);

*(backup_val+pos)=*(val+i); *(backup_pos+pos)=i;
*(len+i)=pos+1;
if(pos>0)*(path+i)=*(backup_pos+pos-1); else *(path+i)=-1;
location=*(backup_pos+maxlen);

}
return location; //return the last position from which data will finish
}

type binary_search(type x[range],type item,type beg,type end)
{
type mid=(beg+end)/2;
while((beg<(end-1))&&(x[mid]!=item))
{
if(item<x[mid]) end=mid-1;
else beg=mid+1;
mid=(beg+end)/2;
}
if(x[mid]==item)return mid;
if(x[beg]==item)return beg;
if(x[end]==item)return end;
if(x[beg]<item)beg++;
return beg;
}

[Sedefcho]

Have a look at this thread:

http://online-judge.uva.es/board/viewtopic.php?t=3957

There's plenty of I/O there.

[Sedefcho]

Jackie,

Why don't you give some URL / web link to the
article you've read ?
It could be interesting for others too.

Thanks.

[Emilio]

Hi there,
I must write this post because after a lot of WAs, I read this post and then thought maybe my binary search had some small bug and really this was the cause of my WAs.
Thanks by having written this post.

[lord_burgos]

I'm use LIS O(n lon n)

Code: Select all

import java.io.*; 
import java.util.*; 

class Main{ 

  public static String readLn (int maxLg){ 
     byte lin[] = new byte [maxLg]; 
     int lg = 0, car = -1; 

     try{ 
        while (lg < maxLg){ 
          car = System.in.read(); 
          if ((car < 0) || (car == '\n')) break; 
          lin [lg++] += car; 
        } 
     }
     catch (java.io.IOException e){  return (null); } 

     if ((car < 0) && (lg == 0)) return (null); // eof 
     return (new String (lin, 0, lg)); 
  }
  
  
  int datos[] = new int[10001];
  int AI[] = new int[10001];
  int A[] = new int[10001];
  int d[] = new int[10001];
  
  
  public static void main(String arg[]){
  	    Main m = new Main();
  	    m.principal();
  }
  
  int busca(int izq, int der, int val){
  	int m = (izq + der)/2;
  	if(izq >= der) return m;
  	if(val == d[m]) return m;
  	if(val > d[m]) return busca(m + 1, der, val);
  	return busca(izq, m - 1, val);
  }
  
  void incresi(int n){
  	  int np = 0, x, pos;
  	  d[np++] = datos[0];
  	  A[0] = 1;
      for(x = 1; x < n; x++){
      	if(datos[x] > d[np - 1]){  d[np++] = datos[x]; A[x] = np; continue; }
        pos = busca(0, np - 1, datos[x]) - 2;
        if(pos < 0) pos = 0;
        for(; pos < np && datos[x] > d[pos] ; pos++);
        d[pos] = datos[x];
        A[x] = pos + 1;
      }
  }
  
  void dcresi(int n){
  	  int np = 0, x, pos;
  	  d[np++] = datos[n - 1];
  	  AI[n - 1] = 1;
      for(x = n - 2; x >= 0; x--){
      	if(datos[x] > d[np - 1]){  d[np++] = datos[x]; AI[x] = np; continue; }
        pos = busca(0, np - 1, datos[x]) - 2;
        if(pos < 0) pos = 0;
        for(; pos < np && datos[x] > d[pos] ; pos++);
        d[pos] = datos[x];
        AI[x] = pos + 1;
      }
  }
  
  
  void principal(){
      	String line;
     	StringTokenizer st;
     	int n, x, sol;
     	
     	for(;;){
     		line = readLn(100);
     		if(line == null) break;
     		n = Integer.parseInt(line.trim());
     		line = readLn(200001);
     		st = new StringTokenizer(line);
     		for(x = 0; x < n; x++) datos[x] = Integer.parseInt(st.nextToken());
     	    incresi(n);
     	    dcresi(n);
     	    sol = 0;
     	    for(x = 0; x < n; x++) sol = Math.max(sol, 2* ( Math.min(A[x], AI[x]) - 1) + 1 );
     	    System.out.println(sol);
     	} 
     	
  }

}

input

Code: Select all

5
1 2 1 3 5
21
1 2 4 51 2 3 8 4 5 1 8 9 4 12 1 2 2 32 1 2 6

Output

Code: Select all

3
7

Why WA??

[ehsanulbigboss]

C.K.

[brianfry713]

You can solve it in O(n log n), you have a O(n * n) section.