Page 3 of 3
Posted: Sun Jul 18, 2004 11:57 am
So try now..

Posted: Sun Jul 18, 2004 11:59 am
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.

### Thank you!

Posted: Sun Jul 18, 2004 12:28 pm
Finally I got accepted...
Yeah, you are right about that.
I didn't understand the problem statement clearly.
Thank you for the help.

Posted: Tue Jul 20, 2004 9:15 am
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

### Compiler Error

Posted: Mon Aug 23, 2004 8:22 pm
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;
}

Posted: Mon Aug 23, 2004 11:06 pm

Posted: Mon Aug 23, 2004 11:40 pm
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.

Posted: Tue Aug 24, 2004 2:31 am
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

Posted: Thu Nov 25, 2004 9:07 pm
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;
}

Posted: Tue Mar 01, 2005 4:01 pm
Have a look at this thread:

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

There's plenty of I/O there.

Posted: Thu Mar 10, 2005 3:28 pm
Jackie,

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

Thanks.

Posted: Sat Apr 09, 2005 3:50 am
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.

### 10534 java, Why Wrong Answer???

Posted: Sun Jan 29, 2006 12:33 am
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){
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(;;){
if(line == null) break;
n = Integer.parseInt(line.trim());
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??

### Re: 10534 - Wavio Sequence

Posted: Mon Feb 23, 2015 6:56 pm
C.K.

### Re: 10534 - Wavio Sequence

Posted: Tue Feb 24, 2015 9:50 pm
You can solve it in O(n log n), you have a O(n * n) section.