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

Rand thicknesst(so the inner radius of the ring isR-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 lengthgbetween 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:

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 do

*not hit*it…

This is so the interesting area:

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**

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 **square**s. Some of them are cut off, but that’s **should not be** a problem… *it should*…

Now consider an *hole*:

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 (

*)^2*

**g**-2***f**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*:

- The center of the ball has to be in the
**small**area - 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 **square**s there are in the **small** area. That number is **nos** = **small**/**square** (where **nos** stands for **n**umber **o**f **s**quares)

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_*is just our

**not**_hitting_area**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.9**20132

Case #3: **0.000000**

Case #4: **0.0023**64

Case #5: **0.573**156

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”