10382 - Watering Grass

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

Moderator: Board moderators

Postby Jan » Sat Sep 01, 2007 4:37 pm

I havent checked why you are getting RTE but I can say that your code isnt correct. Check the case

Input:
Code: Select all
12 28 15
1 10
5 19
19 3
5 6
6 2
8 2
12 16
3 8
17 12
5 3
14 13
3 2

Output:
Code: Select all
-1

Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru
 
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

Postby Terro » Sat Sep 01, 2007 5:16 pm

Jan wrote:I havent checked why you are getting RTE but I can say that your code isnt correct. Check the case

Input:
Code: Select all
12 28 15
1 10
5 19
19 3
5 6
6 2
8 2
12 16
3 8
17 12
5 3
14 13
3 2

Output:
Code: Select all
-1

Hope it helps.


Thanks a lot.
I've modified my program. And I didn't get RE. But after modifying, I got WA. Here is my new 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;
         int pre = maxi;   //In order to check wheather it's able to find the next section
         while (section[++p].begin - st < 1e-8 && p <= n)
            if (section[p].end - st > tmpmax)
            {
               tmpmax = section[p].end - st;
               maxi = p;
            }
         if (maxi == pre)
         {
            cout << "-1\n";
            st = l;
            count = -1;
         }
         else
         {
            st = section[maxi].end;
            count++;
         }
      }
      if (count > 0)
         cout << count << endl;
   }
   return 0;
}
Terro
New poster
 
Posts: 4
Joined: Sat Sep 01, 2007 3:21 pm

Postby Jan » Sat Sep 01, 2007 5:30 pm

Try the cases.

Input:
Code: Select all
2 26 6
4 10
16 14
10 6 37
20 4
19 20
19 2
8 4
7 19
7 14
3 17
1 19
18 1
15 19

Output:
Code: Select all
2
2

Hope these help.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru
 
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

Postby Terro » Sun Sep 02, 2007 10:29 am

Jan wrote:Try the cases.

Input:
Code: Select all
2 26 6
4 10
16 14
10 6 37
20 4
19 20
19 2
8 4
7 19
7 14
3 17
1 19
18 1
15 19

Output:
Code: Select all
2
2

Hope these help.


Really thanks for your datas. It just helped me find a mistake. But I still get WA. I've been very confused. Could you please give me some advice? Thanks a lot.
Terro
New poster
 
Posts: 4
Joined: Sat Sep 01, 2007 3:21 pm

Postby Jan » Sun Sep 02, 2007 7:26 pm

Check the following files...

Input
Ouput
Hope these help.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru
 
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

Postby Tirdad » Mon Sep 03, 2007 5:45 am

Jan said:
I havent checked why you are getting RTE but I can say that your code isnt correct. Check the case

Input:
Code:
12 28 15
1 10
5 19
19 3
5 6
6 2
8 2
12 16
3 8
17 12
5 3
14 13
3 2

Output:
Code:
-1

I checked this test case too and it produced the correct output with my binary. now I guess that there might be some coflicts with the compilers.
I use VS2005 but in near future I switch to a better substitude!
can you tell me what is your IDE and compiler Jan?
by the way I cheched the input and output file that you upload and unfortunatly the code is still correct!
Tirdad
New poster
 
Posts: 5
Joined: Tue Sep 20, 2005 2:53 pm
Location: iran

Postby Jan » Mon Sep 03, 2007 6:43 am

My compiler is MS visual studio 6.0. Its hard to generate effective cases for geometry problems. The random cases matched! Thats why I had to check your coe manually. But couldnt figure out the error.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru
 
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

Postby Terro » Mon Sep 03, 2007 3:23 pm

Jan wrote:Check the following files...

Input
Ouput
Hope these help.


I've been really confused. I checked my program using these datas just now. It worked well. But I still got a WA.
So what should I exactly do?
Terro
New poster
 
Posts: 4
Joined: Sat Sep 01, 2007 3:21 pm

Postby Jan » Wed Sep 05, 2007 7:51 am

There can be precision errors. For floating point numbers you should use the comparisons as follows:

Code: Select all
 int      double
a == b   fabs(a-b) < eps
a != b   fabs(a-b) > eps
a > b    a > b + eps
a < b    a + eps < b

Here 'eps' is a small value. Its better to set 'eps' from 10^(-7) to 10^(-11). Hope it works.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru
 
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

Re: 10382 - Watering Grass

Postby Leonid » Tue Nov 18, 2008 6:53 pm

I'm reaaaaaly confused why I can get AC for this task.
1. I've passed sample cases
2. I've passed all test cases on the board
3. I've passed around 4000 randomly generated test cases verified with http://www.uvatoolkit.com
4. I've found that the problem contains such values with l == 0 or w == 0 and I suspect that the answer for the test cases snould be 0, while the answers produced by http://www.uvatoolkit.com does not follow this logic.
5. I've tried to change EPS value to 1e-7, 1e-11, 1e-13 but still WA
6. WHAT A F*** HAVE I MISSED OUT? When I look at the code I don't feel that there are many mistakes to do so I'm asking for your help guys, please find my mistake!
Code: Select all
const double EPS = 1e-11;
typedef pair<double, double> pii;
bool solve() {
   int n, l, w;
   if (scanf("%d %d %d ",&n,&l,&w) != 3)
      return false;

   vector<pii> sprinklers;
   for (int i = 0; i < n; i++) {
      int p, r;
      scanf("%d %d ",&p,&r);
      pii pd;
      if (2 * r > w) {
         double d = sqrt(r * r - (w * w) / 4.0);
         pd.first = p - d;
         pd.second = p + d;
         sprinklers.push_back(pd);
      }
   }
   sort(sprinklers.begin(), sprinklers.end());
   int m = SZ(sprinklers);
   
   double start = 0;
   int j = 0, total = 0, pj = 0;
   while (start < (double)l - EPS) {
      double go = start;
      while (j < m && sprinklers[j].first - EPS < start) {
         go = max(go, sprinklers[j].second);
         j++;
      }
      if (pj == j) {
         printf("-1\n");
         return true;
      }
      pj = j;
      start = go;
      total++;
   }
   printf("%d\n", total);

   return true;
}
Leonid
Experienced poster
 
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm

Re: 10382 - Watering Grass

Postby Sanik » Wed Sep 16, 2009 4:42 am

For those who have got an WA, this may be the problem you are facing,
I've finally found why I couldn't get an AC after testing all the test cases others have posted(which were all correct).
But I still can't figure out why it is caused ....

At somewhere in my code I wrote

Code: Select all
double length_2 = sqrt((double)(rad*rad)-w2_2);


and got a WA

But when I changed it to

Code: Select all
double length_2 = sqrt((double)rad*rad-w2_2);


I got an AC

But to my knowledge it should be the same(even safer to give a bracket)

Can anybody tell me why??
-------
I've found out why....because it may overflow.... if I used (double)rad*rad
Sanik
New poster
 
Posts: 1
Joined: Wed Sep 16, 2009 4:33 am

10382-watering grass

Postby ACslow » Tue Apr 05, 2011 4:30 pm

Code: Select all
var p,pi,t,len,n,w,i,tot:longint;
    l,r:array[0..10000]of double;
    now,max:double;
    flag:boolean;
procedure qsort(x,y:longint);
  var i,j:longint;
      k,temp:double;
  begin
    i:=x;j:=y;k:=l[(i+j) div 2];
    repeat
      while l[i]<k do inc(i);
      while l[j]>k do dec(j);
      if not (i>j) then begin
        temp:=l[i];l[i]:=l[j];l[j]:=temp;
        temp:=r[i];r[i]:=r[j];r[j]:=temp;
        inc(i);dec(j);
      end;
    until i>j;
    if x<j then qsort(x,j);
    if i<y then qsort(i,y);
  end;

begin
  while not eof do begin
    readln(n,len,w);
    t:=0;
    for i:=1 to n do begin
      readln(p,pi);
      if pi>w/2 then begin
        inc(t);
        l[t]:=p-sqrt(sqr(pi)-sqr(w/2));
        if l[t]<0 then l[t]:=0;
        r[t]:=p+sqrt(sqr(pi)-sqr(w/2));
        if r[t]>len then r[t]:=len;
        //writeln(l[t],' ',r[t]);
      end;
    end;
    qsort(1,t);
    now:=0;
    i:=1;
    tot:=0;
    flag:=true;
    while now<len do begin
      max:=0;
      while (l[i]<=now) and (i<=t) do begin
        if r[i]>max then max:=r[i];
        inc(i);
      end;
      if max=0 then begin
        writeln(-1);
        flag:=false;
        break;
      end;
      now:=max;
      inc(tot);
    end;
    if flag then writeln(tot);
  end;
end.


I test many cases,and it's no problem.But online-judge says "runtime error".I check the program over and over again,but i still can not find any mistake.could you help me?
ACslow
New poster
 
Posts: 1
Joined: Tue Apr 05, 2011 4:23 pm

Re: 10382 - Watering Grass

Postby AhmadKhatar » Tue Aug 28, 2012 2:11 pm

Hi!
I checked the code several times but I can't find any mistake in it. Does anybody know the problem with it?
Here is my code:
Code: Select all
#include <iostream>
#include <cmath>

using namespace std;

int n;
int sX [ 10000 ], sR [ 10000 ];
int l, w;
struct Line
{
   double l, r;
} ln [ 10000 ];

void process();
void construct();

int main()
{
   while ( cin >> n >> l >> w )
   {
      for ( int i = 0; i < n; i++ )
      {
         cin >> sX[ i ] >> sR[ i ];
      }
      process();
   }

   return 0;
}

void process()
{
   construct();

   double cV;
   cV = 0;
   
   Line tLn [ 10000 ];
   int tNo;

   int cnt = 0;
   while ( cV < l && n > 0 )
   {
      int next = -1;
      for ( int i = 0; i < n; i++ )
      {
         if ( next == -1 )
         {
            next = i;
         }
         else if ( (ln[ i ].l < ln[ next ].l) ||
                   (ln[ i ].l == ln[ next ].l && ln[ i ].r > ln[ next ].r) )
         {
            next = i;
         }
      }
      
      if ( ln[ next ].l > cV )
      {
         cout << -1 << endl;
         return;
      }
      cV = ln[ next ].r;
      cnt++;

      tNo = 0; // refresh
      for ( int j = 0; j < n; j++ )
      {
         if ( ln[ j ].l < cV )
         {
            if ( ln[ j ].r <= cV )
            {
               // do nothing
            }
            else
            {
               ln[ j ].l = cV;
               tLn[ tNo++ ] = ln[ j ];
            }
         }
         else
         {
            tLn[ tNo++ ] = ln[ j ];
         }
      }

      for ( int j = 0; j < tNo; j++ )
      {
         ln[ j ] = tLn[ j ];
      }
      n = tNo;
   }

   if ( cV < l )
   {
      cout << -1 << endl;
   }
   else
   {
      cout << cnt << endl;
   }
}

void construct()
{
   double tL, tR;
   int tCnt = 0;
   for ( int i = 0; i < n; i++ )
   {
      if ( sR[ i ] > w / 2.0 )
      {
         tL = max( sX[ i ] - sqrt( 4 * sR[ i ] * sR[ i ] - w * w + 0.0 ) / 2.0 , 0.0 );
         tR = min( sX[ i ] + sqrt( 4 * sR[ i ] * sR[ i ] - w * w + 0.0 ) / 2.0 , l + 0.0 );
         ln[ tCnt ].l = tL;
         ln[ tCnt ].r = tR;
         tCnt++;
      }
   }
   n = tCnt;
}

Thanks in advance! :D
AhmadKhatar
New poster
 
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 10382 - Watering Grass

Postby brianfry713 » Wed Aug 29, 2012 11:57 pm

You're having the same issue as Sanik in the post above yours. There's probably a case like:
Code: Select all
1 1000000001 100
1000000000 1000000000
Check input and AC output for hundreds of problems on uDebug!
brianfry713
Guru
 
Posts: 5409
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10382 - Watering Grass

Postby AhmadKhatar » Thu Aug 30, 2012 1:27 am

Many Thanks!
I got AC! :D
AhmadKhatar
New poster
 
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Previous

Return to Volume CIII

Who is online

Users browsing this forum: No registered users and 2 guests