GCJ 2008: Fly Swatter

July 19th, 2008 § 8 comments

Consider this:
GCJ 2008 - Problem C - raquet

Believe it or not, but that’s a racquet! In fact the third problem of the Qualification Round of Google Code Jam 2008 is about balls and racquets (or rackets if you prefer)… well… actually it’s about probability :^D

You can find the whole text of the problem here, I’m reporting just the interesting part (IMHO):

Problem

What are your chances of hitting a fly with a tennis racquet?

To start with, ignore the racquet’s handle. Assume the racquet is a perfect ring, of outer radius R and thickness t (so the inner radius of the ring is R-t).

The ring is covered with horizontal and vertical strings. Each string is a cylinder of radius r. Each string is a chord of the ring (a straight line connecting two points of the circle). There is a gap of length g between neighbouring strings. The strings are symmetric with respect to the center of the racquet i.e. there is a pair of strings whose centers meet at the center of the ring.

The fly is a sphere of radius f. Assume that the racquet is moving in a straight line perpendicular to the plane of the ring. Assume also that the fly’s center is inside the outer radius of the racquet and is equally likely to be anywhere within that radius. Any overlap between the fly and the racquet (the ring or a string) counts as a hit.

The input file consists in N lines containing values of f, R, t, r and g separated by spaces.

I’m now trying to explain my approach. The probability we’re looking for it’s given by total_hitting_area/total_racquet_area, or 1 – total_not_hitting_area/total_racquet_area

total racquet area it’s simple:
GCJ 2008 - Problem C - big
I’ll call it big, and it’s given by pi*R^2

The problem is the other area. I’ll try to calculate the not hitting area. Calculus gives a solution to get area of any kind of shape: integrals, but I don’t think it’s necessary to use them in this case. First for all we need to simplify. I don’t care about the ball, I’ll care about the center of the ball. The center of the ball has to be a distance f (the ball radius) from the border of the racquet in order to donot hit it…

This is so the interesting area:
GCJ 2008 - Problem C - small
I’ll call it small, and has a radius of R-t-f so the area is given by pi*(R-t-f)^2

The probability of the center of the ball to be in the small area is given by small/big, and I call it q1

Now consider this:
GCJ 2008 - Problem C - square

The two red areas are identical, they are both composed by the same amount of green and white area, I can consider any of them as a square, its area is given by (g+2*r)^2

Note that small is composed by squares. Some of them are cut off, but that’s should not be a problem… it should

Now consider an hole:
GCJ 2008 - Problem C - gap
I’ll call the red area gap, it’s a little square with sides long g-2*f as I subtract 2 times the ball radius. In fact the center of the ball has to be at least at a distance of f from the sides of the white area in order to do not hit a string. So a gap is (g-2*f)^2

The probability of the center of the ball to pass through a gap contained in a square is given by gap/square and I’ll call it q2

In order to do not hit the racquet to events have to happen at the same time:

    1. The center of the ball has to be in the small area
    2. The center of the ball has to be in a gap area

These to events have probability q1 and q2 respectively.
The probability they are both verified is q = q1 * q2, and that’s the not successful case.

The successful case is p = 1 – q… the probability we were looking for…

It should work… it should… But it doesn’t.

I tried an other approach so. I calculate how many squares there are in the small area. That number is nos = small/square (where nos stands for number of squares)

We know there are as many gap as squares, that’s just because there is one gap inside each square.

In this way I can calculate the total gap area, that is just nos*gap and I call it totalgap

Do you remember the 1 – total_not_hitting_area/total_racquet_area… well the total_not_hitting_area is just our totalgap!

So we have q = totalgap/big… and p = 1 – q

I’ve found the same p as the one above… and it’s wrong.

I went so close the solution but there is something wrong, just to show you, these are the sample cases:
0.25 1.0 0.1 0.01 0.5
0.25 1.0 0.1 0.01 0.9
0.00001 10000 0.00001 0.00001 1000
0.4 10000 0.00001 0.00001 700
1 100 1 1 10

The Google’s results for these cases are:
Case #1: 1.000000
Case #2: 0.910015
Case #3: 0.000000
Case #4: 0.002371
Case #5: 0.573972

But mines are:
Case #1: 1.000000
Case #2: 0.920132
Case #3: 0.000000
Case #4: 0.002364
Case #5: 0.573156

They are so close.

You can download my solution file by clicking here.
That’s my implementation in python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def solve(f,R,t,r,g):
    if 2*f >= g: return 1.0
    t += f
    g -= 2*f
    r += f
 
 
    big = pi*R**2
    small = pi*(R-t)**2
    square = (2*r+g)**2
    gap = g**2
 
    # Way 1
 
    q1 = 1.0 * small/big
    q2 = 1.0 * gap/square
    q = q1*q2
 
 
    # Way 2
    '''
    nos = 1.0*small/square
    totalgap = gap*nos
    q1 = 1.0 * small/big
    q2 = 1.0 * totalgap/small
 
    q = q1*q2
    '''
 
 
    if 0 <= q:
        if q <= 1:
            p = 1-q
        else:
            p = 0.0
    else:
        p = 1.0
    #print 1-q
    return p
 
 
def sfs(s):
    'solve from string'
    s = s.replace('\n', '').split(' ')
    f,R,t,r,g = [float(i) for i in s]
    return solve(f,R,t,r,g)

I did one in C too, I was thinking python did something wrong with math…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <stdio.h>
#define pi 3.1415926535897931
 
double solve(double f,double R,double t,double r,double g)
{
    double big,small,square,gap,q1,q2,q,p;
 
    if (2*f >=g )
    {
         return 1;
    }
 
    t = t + f;
    g = g - 2*f;
    r = r +f;
 
    big = pi*R*R;
    small = pi*(R-t)*(R-t);
    square = (2*r+g)*(2*r+g);
    gap = g*g;
 
    q1 = small/big;
    q2 = gap/square;
    q = q1*q2;
 
    if (0<=q)
    {
        if (q<=1)
        {
            p = 1-q;
        } else p = 0;
    } else p = 1;
 
    return p;
}
 
int main()
{
    printf("Case #1: %lf\n",solve(0.25, 1.0, 0.1, 0.01, 0.5));
    printf("Case #2: %lf\n",solve(0.25, 1.0, 0.1, 0.01, 0.9));
    printf("Case #3: %lf\n",solve(0.00001, 10000, 0.00001, 0.00001, 1000));
    printf("Case #4: %lf\n",solve(0.4, 10000, 0.00001, 0.00001, 700));
    printf("Case #5: %lf\n",solve(1, 100, 1, 1, 10));
}

There’s no need to say that the result was the very same.

I don’t know what’s wrong with my approach, all the others’ code I read used something involving integrals, sometime already solved and they just did the “definite” part.

Did you read someone’s code that is not using integrals but pure geometry and probability approach?
I think it’s possible, I think there is something very bastard I’m missing… don’t know what… do you?

return “grr”

Tagged , , ,

§ 8 Responses to GCJ 2008: Fly Swatter"

  • Authentic says:

    Hi, I think your approach is wrong because these two events: small and gap are not independent events. Gap is intersected with small at the border.

  • Authentic says:

    Also, you don’t consider times of event “small” it ocurrs.

  • e.nigma says:

    >Hi, I think your approach is wrong because these two events:
    >small and gap are not independent events. Gap is intersected
    >with small at the border.

    I took them as independent because a ball can be in a “not hitting area” like a gap BUT may hit the border…

    http://e.nigma.be/wp-content/uploads/2008/07/hitting_ball.png

    (If you cannot see it the image link is: http://e.nigma.be/wp-content/uploads/2008/07/hitting_ball.png)

    That means they have to be both verified …

    > Also, you don’t consider times of event “small” it ocurrs.

    I don’t understand what does it mean (maybe is my english fault), can you try to explain me what do you mean with that?

  • Authentic says:

    >> Also, you don’t consider times of event “small” it ocurrs.

    >I don’t understand what does it mean (maybe is my english fault), >can you try to explain me what do you mean with that?

    Event gap occurrs many times inside the racket. In your formula you don’t take care about that.

  • e.nigma says:

    >Event gap occurrs many times inside the racket. In your formula
    >you don’t take care about that
    >

    Uhm… Im sure that a ball falling in the small area will fall into a square, ok? that’s a sure event.

    I called the probability to fall in a gap area of ONE square q2 = gap/small…

    if there are 3.215 squares in the small area well… as there is one gap for each square there will be 3.215 gap in the small area…

    if you do 3.215 * gap/ small you’re take care about it… but the result (as I’ve shown) is the same… am I right? am I missing your point?

  • Clive says:

    You appear to be trying to treat the two cases of the fly going through the “big” circular hole (inside of the inner rim of the racquet), and that of it going through a square hole between strings (where these strings and gaps between them are considered to be extending over the full area of the whole racquet) as two independent events. But that is totally wrong! If the fly hits the rim of the racquet it cannot ever go through the hole between strings that might be lying “behind” that point.

    Imagine a simpler case where there are two “filters” that can catch the fly. Say each is set up in a way that the fly (hitting the filter randomly) has a 50% probability of being hit. You are (I think) saying you can always just multiply those probabilities to get the correct value for the combined set of filters. But those filters might (when overlapped) produce zero chance of the fly getting through.

    For example, say you have two sets filters consisting of vertical strings (only vertical string all with infinitesimal thickness (r~=0), suspended in an outer square frame also with infinitesimal thickness (t~=0) to keep things simple) with a gap of 4f between them. Now each such set of strings alone gives a 50% chance for the flying getting through. Your approach would trying to multipl0 0.5 by 0.5 and get 0.25 for it getting through both. However if the two sets of strings are positioned exactly on top of each other the probability is still 50%, and if they are offset horizontally by 2f then the fly cannot ever get through!

    To get the correct answer, you have to treat the different cases separately!

  • e.nigma says:

    Maybe this:
    http://e.nigma.be/wp-content/uploads/2008/07/hitting_ball.png

    was not so clear. I putted black on all except for one ball, do you see the one on the bottom? If the gap was complete the ball could pass through it, but its center it’s out of the small area and so it’s hitting the border, that seems to be the event have to be verified at the same time, and (in math, not in the real world) one event can be verified without the other, am I wrong?

  • […] racquets (or rackets if you prefer)… well… actually it’s about probability :^D… [full post] Andrea nigma codinggcj 2008gcjgoogle code jam 0 0 0 0 […]

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>