SRM 621: Invisible slowness

So another SRM day. I've been with headache since yesterday so running at half the steam...

Div1 275: The one with the geometry

So you have a circle (signal) centered at `(0,0)` with radius `S` , `S` is a real number picked uniformly at random from 0.00 to `Z`. There are some other circles (cities) each with center `(x,y)` and radius `r`. Things are good if, for each city, the main circle (signal) either doesn't include the city or it includes ALL of the points inside the city. Return the probability that this happens. The answer can have an absolute or relative error or 1e-6 (whichever is smallest)

So that's a nice thing about the allowed error. After topcoder added the ability to include a custom checker in problem sets, I thought it was only a matter of time until someone makes a problem that allows less precision than the usual 1e-9. The first thing I did in this problem was take my special python tester template that allows you to test automatically even when there is a custom checker. I used CNP super powers to paste the usual python checker, but replacing the 1e-9 with 1e-6... I really wanted to have accurate tester results.

The first thing is to notice what makes a radius `S` valid for a specific circle with `(x,y,r)`. A nice trick in problems involving plenty of circles is to consider only the distance between their centers. Eventually you will notice that if the distance between `(0,0)` is `d`, then there are two ranges in which is `S` is valid: `S <= d - r` or `S >= d + r`. Something that caused me to take a bit of time in this sub-problem, because of a special corner case: What if `(0,0)` is inside circle `(x,y,r)` ? Then `d-r` is negative. It turns out that it doesn't matter. `S` cannot be negative, and thus: `S <= d - r` or `S >= d + r` is still a good condition.

Once we know that condition. How to deal with the probability? You should see those `d-r` and `d+r` (for all cities) as the only points where the validity of `S` could change. So we can divide the `[0,Z]` interval using those points as delimiters. Now we can test each segment `[a,b]`, we know that `a` or `b` are points in which the result could change, so all points exclusively inside `(a,b)` will have the same result. `S` is valid for `(a+b)/2` if and only if it is valid for all points in interval `[a,b]`. For each valid interval `[a,b]`, if any of those points is picked for `S`, it is valid just add `(b - a) / Z` to the probability.

class RadioRange:
 def RadiusProbability(self, X, Y, R, Z):
    cities = zip(X,Y,R)
    
    def goodCity(x,y,r,s):     #city completely inside circle of radius s or not
        d = (x**2 + y**2) ** 0.5
        return ( (s <= d - r) or (s >= d + r) )
    
    def goodRadius(s):         # each circle must be completely included or not
        return all( goodCity(x,y,r,s) for (x,y,r) in cities )
    
    def getEvents():
        yield 0.0
        yield Z
        for (x,y,r) in cities:
            d = (x**2 + y**2) ** 0.5
            yield d + r
            yield d - r
    
    # remove invalid events (less than 0, more than Z), duplicates (using set)
    # and turn into a list (so we can use indexes) and sort
    # (possibly unnecessary to call sorted, the set likely already sorted)
    evs = sorted( list(set( x for x in getEvents() if (0 <= x <= Z) ) ) )
    good = 0.0
    for i in range(0, len(evs) - 1):
        p = (evs[i] + evs[i+1]) / 2
        if goodRadius(p):
            good += evs[i+1] - evs[i]
            
    return good / Z

I knew how to solve the problem since the beginning, except dealing with the corner case that turned out not to exist anyway. I am not sure why it took me so long to solve it, but it did.

Div1 500: tree stuff

Seems hard, I was tired and with headache so I went to lie down while I supposedly thought of the problem, but couldn't think of much.

Challenge phase

During the challenge phase I discovered why people were faster than my in 275, it turns out that `S` is invalid if and only if it intersects with any circle (city) in the input. While most of the code remains the same, this makes reaching the code a bit easier and also removes the need for checking for validity of `(a+b)/2`at the end, instead you just do a line sweep. (Each event `d-r` increments the number of intersecting circles, each `d+r` decrements it, sum up intervals in which the count is 0.)