10382 - Watering Grass

[miras]

Hello...

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



do u have any intresting tests ??




Regards
MIras

[junbin]

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

[koala]

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]

[angga888]

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]

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]

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]

I got WA too....

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

help!

[ZhangChi]

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]

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]

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]

is there anybody who can challenge this code?

[Jan]

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.

[Tirdad]

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]

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.

[Terro]

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;
}