10382 - Watering Grass

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

Moderator: Board moderators

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

10382 (* stiupid ?? *)

Post by miras » Mon Feb 02, 2004 3:10 pm

Hello...

i'm trying to solve 10382,
i wrote code but i still getr WA



do u have any intresting tests ??



8)
Regards
MIras

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Tue Feb 03, 2004 3:30 pm

You may wanna post in the 103 board.. :p

koala
New poster
Posts: 7
Joined: Sun Mar 28, 2004 9:41 am
Location: Tsinghua University, Peking, P.R.China
Contact:

10382 - Watering Grass

Post by koala » Sun Mar 28, 2004 1:36 pm

My algorithm is:
1. Since covering the entire strip and covering the upper bound are equivalent, each sprinkler can be represented by an interval.
2. Use GREEDY algorithm to solve it.
Is it correct? I think so, but why did I got WA.
[pascal]
Program Watering_Grass;

Const
Maxn=10000;
Zero=1e-3; {I have tried Zero=0 and Zero=1e-6, but both WA}

Type
Intervaltype=Record
x,y:Real;
End;

Var
a:Array [1..Maxn] of Intervaltype;
n,l,w,ans:Longint;

Procedure Input_Data;
Var
i,x,r:Longint;
Begin
Readln(n,l,w);
For i:=1 to n Do
Begin
Readln(x,r);
If r*r-w*w/4<0
Then Begin a.x:=0; a.y:=0 End
Else Begin
a.x:=x-Sqrt(r*r-w*w/4); a.y:=x+Sqrt(r*r-w*w/4);
End;
End;
End;

Procedure Qsort(p,q:Longint);
Var
r,i,j:Longint;
k:Intervaltype;
Begin
r:=Random(q-p+1)+p;
k:=a[r];
a[r]:=a[p];
i:=p; j:=q;
While i<j Do
Begin
While (i<j) and (k.x<=a[j].x) Do Dec(j);
a:=a[j];
While (i<j) and (a.x<=k.x) Do Inc(i);
a[j]:=a;
End;
a:=k;
If p<i-1 Then Qsort(p,i-1);
If i+1<q Then Qsort(i+1,q);
End;

Procedure Solve;
Var
x,y:Real;
i:Longint;
Begin
Qsort(1,n);
ans:=0;
x:=0;
i:=1;
While (i<=n) and (x<l-zero) Do
Begin
Inc(ans);
y:=x;
While (i<=n) and (a.x<=x+zero) Do
Begin
If a.y>y Then y:=a[i].y;
Inc(i);
End;
If y=x Then Begin ans:=-1; Exit End;
x:=y;
End;
If x<l-zero Then ans:=-1;
End;

Procedure Output_Data;
Begin
Writeln(ans);
End;

Begin
While not EOF Do
Begin
Input_Data;
Solve;
Output_Data;
End;
End.
[/pascal]

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Mon Mar 29, 2004 11:18 am

Hi koala,

Haven't look your code, but I suggest you to be careful with precision error. First, I used PASCAL and got WA, but after I translated it to C, I got AC.

Hope it helps,
angga888

shenyute
New poster
Posts: 1
Joined: Tue Jul 27, 2004 2:57 pm

10382

Post by shenyute » Tue Jul 27, 2004 3:01 pm

angga888 wrote:Hi koala,

Haven't look your code, but I suggest you to be careful with precision error. First, I used PASCAL and got WA, but after I translated it to C, I got AC.

Hope it helps,
angga888
can you give me some sample input to check my code~
i got WA><
thanx~

Yax
New poster
Posts: 1
Joined: Fri Oct 07, 2005 9:18 am

10382 TLE

Post by Yax » Fri Oct 07, 2005 9:22 am

Hello, has anyone some reeeeeal long input to this one? I'm getting TLE and i'm not sure if it is inefficient program or some stupid endless loop inside or slow Java. Thanx.

ZhangChi
New poster
Posts: 4
Joined: Tue Oct 18, 2005 6:55 pm
Contact:

Post by ZhangChi » Wed Oct 26, 2005 3:12 pm

I got WA too....

Is there any trick in the test data ? I need some data.

help!

ZhangChi
New poster
Posts: 4
Joined: Tue Oct 18, 2005 6:55 pm
Contact:

Post by ZhangChi » Thu Oct 27, 2005 7:54 pm

I know the reason now!

there are many blank lines at the end of the test data . so if we use EOF , it can't works well ...... this is my code...

Code: Select all

{$S-,R-}

program UVA10382;

const
	maxn	=	10000;

type
	tseg	=	record
				l , r	:	double;
			end;

var
	seg	:	array [ 1 .. maxn ] of tseg;
	w , l	:	double;
	n	:	integer;
	tot	:	integer;
	ans	:	integer;

procedure init;
    var
	i	:	integer;
	p , r	:	double;
	len	:	double;
    begin
	read ( n , l , w );
	tot := 0;
	for i := 1 to n do
	begin
		read ( p , r );
		if r * 2 > w then
		begin
			inc ( tot );
			len := sqrt ( sqr ( r ) - sqr ( w / 2 ) );
			seg [ tot ] . l := p - len ;
			seg [ tot ] . r := p + len ;
		end;
	end;
    end;

function pre ( a , b : tseg ) : boolean;
    begin
	if a . l < b . l then pre := true else
	if a . l > b . l then pre := false else
	if a . r > b . r then pre := true else pre := false;
    end;

procedure swap ( var a , b : tseg );
    var
	c	:	tseg;
    begin
	c := a ; a := b ; b := c;
    end;

procedure sort ( h , t : integer );
    var
	i , j	:	integer;
	x	:	tseg;
    begin
	if h >= t then exit;
	i := h ; j := t;
	x := seg [ ( h + t ) shr 1 ];
	repeat
		while pre ( seg [ i ] , x ) do inc ( i );
		while pre ( x , seg [ j ] ) do dec ( j );
		if i <= j then
		begin
			swap ( seg [ i ] , seg [ j ] );
			inc ( i ) ; dec ( j );
		end;
	until i > j;
	sort ( h , j );
	sort ( i , t );
    end;

procedure prepare;
    var
	i , j	:	integer;
    begin
	n := tot;
	tot := 0;
	i := 1;
	while i <= n do
	begin
		inc ( tot );
		seg [ tot ] := seg [ i ];
		j := i + 1;
		while ( j <= n ) and ( seg [ j ] . r <= seg [ i ] . r ) do inc ( j );
		i := j;
	end;
    end;

procedure greedy;
    var
	i , j	:	integer;
	x	:	integer;
    begin
	ans := -1;
	if tot = 0 then exit;
	if seg [ 1 ] . l > 0 then exit;
	if seg [ tot ] . r < l then exit;
	i := tot;
	while ( i > 1 ) and ( seg [ i ] . l > 0 ) do dec ( i );
	x := 1;
	while ( i < tot ) and ( seg [ i ] . r < l ) do
	begin
		j := i + 1;
		while ( j <= tot ) and ( seg [ i ] . r >= seg [ j ] . l ) do inc ( j );
		dec ( j );
		if j = i then exit;
		inc ( x );
		i := j;
	end;
	ans := x;
    end;

begin
	repeat
		init;
		sort ( 1 , tot );
		prepare;
		greedy;
		writeln ( ans );
		while not eof ( input ) and eoln ( input ) do readln;
	until eof ( input );
end.

kampu
New poster
Posts: 1
Joined: Sun May 21, 2006 1:02 pm

Post by kampu » Sun May 21, 2006 1:05 pm

hi! I'm also having TLE and i dont know why, then I need some inputs for prove my code.

Can anybody give us some inputs please?

Tirdad
New poster
Posts: 5
Joined: Tue Sep 20, 2005 2:53 pm
Location: iran
Contact:

I,ve got WA for (10382) too!

Post by Tirdad » Mon Aug 14, 2006 8:25 pm

I code this problem in two ways and both of them get WA
my first algorithm is
1.remove all circles which are inside bigger circles.
2.remove all circles which their effecting area(left bound to right bound)
is common with other unremoved circles.
3.count remained circles
i guess its true. but after seeing other posts in this subject i change my algorithm to a simple greedy one that is
1.sort the circles according to the left bound of them
2.from the left cover the grass area with the most rightbound circle which has a less left bound and do this until covering all the area
plz let me know if you find any test case that break the code or one of the algorithm
tanx in advans
here is my code
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
struct circle
{
bool mark;
int radius;
int position;
double left;
double right;
void setRectangle(int ,int);
};
void circle::setRectangle(int w,int l)
{
double temp ;
if(radius > w / 2.0 )
temp = sqrt(((double)(radius * radius) - (double)((w * w)/4.0 )));
else
{
temp = 0.0;
}
left = position - temp;
if(left < 0.0)
left = 0.0;
right = position + temp;
if(right > l)
right = l;
}
bool operator<(const circle &a, const circle &b)
{
return (a.left < b.left);
}
circle data [10001];
int main()
{
int n,w,l,counter,index;
double leftBound,rightBound;
bool find ;
while(cin>>n>>l>>w)
{
for(int i=0;i<n;i++)
{
cin>>data.position>>data.radius;
data.setRectangle(w,l);
}
sort(data,data + n);
leftBound = rightBound = 0;
index = counter = 0;
while(leftBound != l)
{
find = false;
for(int i=index;i<n;i++)
{
if(data.left<=leftBound && data.right > rightBound )
{
index = i;
rightBound = data.right;
find = true;
}
}
if(!find)
break;
counter ++;
leftBound = data[index].right;

}
if(find)
cout<<counter<<endl;
else
cout<<-1<<endl;
}
return 0;
}

Tirdad
New poster
Posts: 5
Joined: Tue Sep 20, 2005 2:53 pm
Location: iran
Contact:

Post by Tirdad » Tue Aug 28, 2007 9:03 pm

is there anybody who can challenge this code?

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Aug 28, 2007 9:28 pm

Try the cases.

Input:

Code: Select all

11 27 3
1 17
2 18
8 1
6 7
2 3
3 7
12 11
16 16
4 4
12 13
16 18
1 6 26
11 11
15 22 16
3 4
5 13
1 12
18 19
2 15
12 1
11 19
8 10
12 11
7 16
12 2
9 16
6 8
9 6
7 14
11 16 7
2 19
3 10
15 15
5 14
5 7
20 16
4 15
2 7
11 17
1 10
11 19
13 25 9
4 17
19 16
8 11
19 18
6 1
13 12
11 8
11 2
1 11
11 18
20 5
15 14
6 13
11 23 4
15 9
3 10
3 9
17 14
3 20
17 5
13 13
18 14
13 3
17 16
13 18
Output:

Code: Select all

1
-1
1
1
1
1
Hope these help.
Last edited by Jan on Wed Aug 29, 2007 8:39 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

Tirdad
New poster
Posts: 5
Joined: Tue Sep 20, 2005 2:53 pm
Location: iran
Contact:

Post by Tirdad » Wed Aug 29, 2007 4:25 am

Now I am getting confused about understanding the problem description!
my output for your test cases is
1
-1
1
1
1
1
and I still can't find out why these 1s should be 2s.
for the first testcase there is the point 16 18 which covers the square completely. for the 3rd and 4th and 5th and 6th testcases I have the same issue with the points 11 19, 2 19, 11 18, 13 18 respectivly.
I know there must be something wrong with my understanding but I can't figure it out
plz help!

Code: Select all


#include <math.h> 
#include <algorithm> 
#include <iostream> 
using namespace std; 
struct circle 
{ 
bool mark; 
int radius; 
int position; 
long double left; 
long double right; 
void setRectangle(int ,int); 
}; 
void circle::setRectangle(int w,int l) 
{ 
long double temp ; 
if(radius > w / 2.0 ) 
temp = sqrt(((long double)(radius * radius) - (long double)((w * w)/4.0 ))); 
else 
{ 
temp = 0.0; 
} 
left = position - temp; 
if(left < 0.0) 
left = 0.0; 
right = position + temp; 
if(right > l) 
right = l; 
} 
bool operator<(const circle &a, const circle &b) 
{ 
return (a.left < b.left); 
} 
circle data [10001]; 
int main() 
{ 
int n,w,l,counter,index; 
double leftBound,rightBound; 
bool find ; 
while(cin>>n>>l>>w) 
{ 
for(int i=0;i<n;i++) 
{ 
cin>>data[i].position>>data[i].radius; 
data[i].setRectangle(w,l); 
} 
sort(data,data + n); 
leftBound = rightBound = 0; 
index = counter = 0; 
while(leftBound != l) 
{ 
find = false; 
for(int i=index;i<n;i++) 
{ 
if(data[i].left<=leftBound && data[i].right > rightBound ) 
{ 
index = i; 
rightBound = data[i].right; 
find = true; 
} 
} 
if(!find) 
break; 
counter ++; 
leftBound = data[index].right; 

} 
if(find) 
cout<<counter<<endl; 
else 
cout<<-1<<endl; 
} 
return 0; 
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Aug 29, 2007 8:45 pm

I was checking some random cases with my old(WA) code. However, I have taken the correct code and ran both the codes, the outputs are equal. I have checked some hand made cases, too. I m still trying. However, if you want the accepted code then PM me.
Ami ekhono shopno dekhi...
HomePage

Terro
New poster
Posts: 4
Joined: Sat Sep 01, 2007 3:21 pm

why runtime error?

Post by Terro » Sat Sep 01, 2007 3:44 pm

A strange problem:
My program can run well when inputting the sample data and the data from Jan. But when I submit, I got a Runtime Error:

Your program has died with signal 11 (SIGSEGV). Meaning:
Invalid memory reference

Here is my program:

Code: Select all

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

struct node
{
	double begin, end;
} section[10001];

inline int cmp(const void* a, const void* b)
{
	return ((node*)a)->begin > ((node*)b)->begin ? 1 : -1;
}

int main()
{
	int n, l, w, r, pos;
	while (cin >> n)
	{
		cin >> l >> w;
		double w2 = double(w*w)/4;
		for (int i = 1; i <= n; i++)
		{
			cin >> pos >> r;
			double tmp = sqrt(r*r-w2>0 ? r*r-w2 : 0);
			section[i].begin = pos - tmp;
			section[i].end = pos + tmp;
		}
		qsort(&section[1], n, sizeof(node), cmp);
		double st = 0;
		int count = 0, p = 0;
		if (section[1].begin > 0 || n <= 0 || w <= 0 || l <= 0)
		{
			cout << "-1\n";
			st = l;
			count = -1;
		}
		while (st < l)
		{
			double tmpmax = 0;
			int maxi = p;
			while (section[++p].begin <= st)
				if (section[p].end - st > tmpmax)
				{
					tmpmax = section[p].end - st;
					maxi = p;
				}
			if (maxi == p)
			{
				cout << "-1\n";
				st = l;
				count = -1;
			}
			else
			{
				st = section[maxi].end;
				count++;
			}
		}
		if (count > 0)
			cout << count << endl;
	}
	return 0;
}

Post Reply

Return to “Volume 103 (10300-10399)”