Google CodeJam

[Tony]

I'm actually more curious in your calculus approach than otherwise. How'd you construct the formula?

[uncompetence]

Being the honest person that I am, I signed myself up at being under 18. I think there was a rule there that we're not allowed to progress to the next round if we're under 18. Any chance they'll be nice or that I could do a quick profile change to move on? For me, it was a pretty fun qualifier, I didn't really rush to finish. I sat watching TV on one monitor and slowly typing away on the other. Finished the first two, didn't bother with the last =\.

[jeffgreco13]

I'm pretty sure only the top 500 get to travel to the locations specified...
if u just 'didnt' do the last one im pretty sure u wont be in that 500

[Zeroth]

Mmm, I tried to do number one, but got number two, but it looks like there was an error in my input file. So I didn't make it to round 1

[aramadia]

Spoilers for Question 3!

The probability of the fly not being hit by the racket is the area of the "gaps" divided by the area of the total racket. To make it easier, assume the fly is a point and make the gap size smaller by the fly's radius (around the edges). Also notice the racket is symmetrical so you only need to calculate one quarter of the area and then multiply of by four (I picked the SE quarter). So the only hard part is to calculate the area where the ring intersects the gaps. In the end loop through all the gaps and check if the the square intersects the ring. If it does calculate the area lost due to the circle. You can integrate the equation (x-h)^2 + (y-k)^2 = R^2 using mathematica or if your lazy I just approximated it with 10000 rectangles. There are a lot of annoying parts so it helps to draw out all possible ways the circle can intersect a square (there are four in this case).

It's fast enough and it gives you an accurate answer. Only problem is calculus is rarely used in programming contests. I'm guessing another way is to actually simulate a million trials to get the final probability.

[jeffgreco13]

So how are our participants doing?? Is anyone in the top 500 as of right now

[jernst]

bah i forgot all about the darn thing and i made a post about it earlier stupid homework and work eating all my time lol

[klopyrev]

There is a fairly simple way to solve #3 using only simple geometry(area of a triangle) and basic trig(area of a sector, angle between 2 vectors). The code for that is really short. Like the calculus solution, you have to consider every gap and count how much area is inside the circle and that gap.

[thegoose]

klopyrev @ Sun Jul 20, 2008 7:59 pm wrote:

There is a fairly simple way to solve #3 using only simple geometry(area of a triangle) and basic trig(area of a sector, angle between 2 vectors). The code for that is really short. Like the calculus solution, you have to consider every gap and count how much area is inside the circle and that gap.

Most contest geometry problems tend to boil down to cross-producting and angle chasing. Also, geo code tend to be short, but extremely dense. You can do some pretty horrendous things in 20-40 lines. (Case and point: Tor's N^2 code to CCC08 Landing was 30 lines, excluding comments)

[bugzpodder]

meh, I am interning with them I didn't go participate