10421 - Critical Wave

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10421 - Critical Wave

Post by little joey » Tue Apr 22, 2003 1:13 pm

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 :wink:
[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

Post by Red Scorpion » Wed May 14, 2003 4:45 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:

Post by Dominik Michniewski » Wed May 14, 2003 9:09 am

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

Post by LittleJohn » Wed May 14, 2003 9:59 am

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:

Post by Dominik Michniewski » Wed May 14, 2003 10:11 am

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:
1. read data
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

Post by LittleJohn » Wed May 14, 2003 11:26 am

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

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:

Post by Dominik Michniewski » Wed May 14, 2003 12:39 pm

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
Location: Waterloo, Ontario, Canada

Post by ChristopherH » Thu May 15, 2003 12:40 am

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:

Post by Dominik Michniewski » Thu May 15, 2003 7:56 am

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)

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

Post by little joey » Thu May 15, 2003 8:53 am

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

Post by LittleJohn » Thu May 15, 2003 10:18 am

Well, the answer should be 1. (I use C language)
Is the integer range of pascal on linux still 16 bits? :o

ChristopherH
New poster
Posts: 31
Joined: Sun Feb 23, 2003 9:18 pm
Location: Waterloo, Ontario, Canada

Post by ChristopherH » Thu May 15, 2003 6:37 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

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

Post by little joey » Thu May 15, 2003 7:03 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.

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

Post by little joey » Thu May 15, 2003 7:24 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 :wink:

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri May 16, 2003 8:13 am

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)

Post Reply

Return to “Volume 104 (10400-10499)”