GCJ 2008: Fly Swatter

July 19th, 2008 § 8 comments § permalink

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”