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”

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.

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

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

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

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

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!

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 […]