## 10421 - Critical Wave

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 10421 - Critical Wave

Can anybody see what I can't see?
I implemented a quick and dirty program that should work IMO.
It's sorting is clumsy, it's loops are too long, but it finishes in 7.5 sec with WA (no runtime error). So it ought to be able to get AC, in principle.
Who gives me a hint?
Ofcourse the code will be removed after AC
[pascal]program p10421;

//CODE REMOVED, AC AT LAST!

[/pascal]
Last edited by little joey on Thu May 15, 2003 7:11 pm, edited 1 time in total.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Hi!,

I always got WA on this problem, Is there any critical input ? I use DP(LIS) to break this problem.

Can anyone give me some test case.
Thanks,
RS

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I got WA too, and I use LIS as Red Scorpion ...
Could anyone tell us some special cases for this problem ?

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Hi, all:
try this input:

Code: Select all

``0``
output:

Code: Select all

``0``

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I try with this case, and I output 0 in this case but still got WA :|
Maybe other hints ?

Best regards and thanks
DM

PS.
My algorithm exactly is:
2. sort them by increasing x-value, and then if x are the same by y (increasing)
3. apply LIS to sorted points
4. print computed result.....
Is this OK?
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
I solved this by LIS, too.
Maybe your program goes wrong with boundary case?
Try these inputs

Code: Select all

``````1
0 2
2
0 2
2 0
2
0 2
2 -1
``````
The output is

Code: Select all

``````1
2
1``````
If still WA, checking your source code again may help

p.s. Every point I memorize two max answers.
One comes from the above, while the other comes from the below..

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I don't know what I'm doing wrong ...
I think, that my code handles correct boundary cases, including yours IO. I memorize two answers for each point, handle 0 points and got ...... WA
I don't know why ....

Best regards
DM

PS. Maybe want you look at my code ?
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Input:

Code: Select all

``````5
0 0
0 1
0 2
0 3
0 4``````

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
My code output "1" for this test, and I think that's correct ...

DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
I'm getting insane from this problem. It's been nearly 4 weeks since I published my code, but noone seems to be able to spot the error.
My program gives all the right answers for all the testcases published here, but still can't get accepted.
I'm a bit worried by this '2 byte signed integer' thing. Do they want us to believe that the right answer for

Code: Select all

``````2
1 -32768
2 32766``````
is 2?
Can someone with AC give the correct answer for this case?

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Well, the answer should be 1. (I use C language)
Is the integer range of pascal on linux still 16 bits?

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
little joey, I think your problem may be that your program only keeps track of one of the 'upper path' and 'lower path' for each point. In this way, it can lose track of the path which falls behind but will eventually become optimal. You need to keep track of the upper path and the lower path separately.

try:

Code: Select all

``````16
0 0
1 2
2 0
3 2
4 4
5 2
6 4
7 2
8 4
9 2
10 0
11 2
12 0
13 2
14 0
15 2``````

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
No, my answer is 10, which is correct. I keep both options for all points, that's why my stack-size is twice the number of points.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
AC at last!

Thanks ChristopherH. My program handled your input correctly, but in confirming that I finaly looked deep enough into the code to see the error. It was a range check error, which the judges so kindly report as 'Wrong Answer' for Pascal programs, instead of giving decent error messages as they do for C and C++ programs.

My program couldn't handle the case where 1000 points alternate the y-coordinate between two values like

Code: Select all

``````1000
0 0
1 2
2 0
3 2
..
998 0
999 2``````
My program started off some 249750 waves in the first round, and that was too much for my program to handle...

And again, judges: Thanks for not giving proper error messages to Pascal programmers and simply ignoring my messages in that respect. I guess sorting it all out for yourself makes one a better programmer

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
Could anyone tell me what I'm doing wrong ? I passed all the tests and got WA ...

Best regards
DM

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

#define MAX	1024

typedef struct _point { int x,y,len[2],next; } POINT;

int Compare(const void *a,const void *b)
{
POINT *A = (POINT *)a,*B = (POINT *)b;

if(A->x < B->x) return -1;
if(A->x > B->x) return 1;
if(A->y < B->y) return -1;
if(A->y > B->y) return 1;
return 0;
}

int LIS(POINT *p,int N)
{
int i,j,htmp,hmax,d;

hmax = 0;
for(i=0;i<N;i++) p[i].len[0] = p[i].len[1] = 1;
for(i=0;i<N;i++)
{
d = (p[i].next == 0) ? 2 : p[i].next;
if(hmax == 0) hmax = ((p[i].len[0] > p[i].len[1]) ? p[i].len[0] : p[i].len[1]);
for(j=i+1;j<N;j++)
{
if(p[j].y == p[i].y + d)
{
htmp = p[i].len[0] + 1;
if((p[i].x != p[j].x) && (p[j].len[0] < htmp))
{
p[j].len[0] = htmp;
p[j].next = -d;
if(hmax < htmp) hmax = htmp;
}
}
if(p[j].y == p[i].y - d)
{
htmp = p[i].len[1] + 1;
if((p[i].x != p[j].x) && (p[j].len[1] < htmp))
{
p[j].len[1] = htmp;
p[j].next = -d;
if(hmax < htmp) hmax = htmp;
}
}
}
}
return hmax;
}

int main(void)
{
int N,i;
POINT nums[MAX];

while(scanf("%d",&N) == 1)
{
for(i=0;i<N;i++)
{
scanf("%d %d",&(nums[i].x),&(nums[i].y));
nums[i].next = 0;
}
qsort(nums,N,sizeof(POINT),Compare);
printf("%d\n",LIS(nums,N));
}
return 0;
}
``````
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)