Page 3 of 3
Posted: Sun Jul 18, 2004 11:57 am
by erfan
So try now..
Posted: Sun Jul 18, 2004 11:59 am
by 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.
Thank you!
Posted: Sun Jul 18, 2004 12:28 pm
by 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.
Posted: Tue Jul 20, 2004 9:15 am
by 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
Compiler Error
Posted: Mon Aug 23, 2004 8:22 pm
by 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;
}
Posted: Mon Aug 23, 2004 11:06 pm
by Krzysztof Duleba
Please provide more info, like what error message did you exactly received.
Posted: Mon Aug 23, 2004 11:40 pm
by 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.
Posted: Tue Aug 24, 2004 2:31 am
by 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
10534wrong answer?????Please give me some test input.
Posted: Thu Nov 25, 2004 9:07 pm
by 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;
}
Posted: Tue Mar 01, 2005 4:01 pm
by Sedefcho
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
by 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.
Posted: Sat Apr 09, 2005 3:50 am
by 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.
10534 java, Why Wrong Answer???
Posted: Sun Jan 29, 2006 12:33 am
by 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);
}
}
}
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
Why WA??
Re: 10534 - Wavio Sequence
Posted: Mon Feb 23, 2015 6:56 pm
by ehsanulbigboss
C.K.
Re: 10534 - Wavio Sequence
Posted: Tue Feb 24, 2015 9:50 pm
by brianfry713
You can solve it in O(n log n), you have a O(n * n) section.