This week in competitive programming

Friday was the day of TopCoder SRM 596 (problems, results, my screencast), featuring three problems which left me wondering how could one ever come up with such questions :) I'm saying that in totally positive sense - they were interesting to solve, but just seemed to come out of nowhere. This was the last round before the TopCoder Open 2013 (program) which takes place November 11-13 in Washington, DC, and which is the oldest open programming competition which has onsite finals. This year the rules have been changed significantly, allowing contestants 20 minutes of downloading software and pre-written algorithms from the Internet before the contest starts. On one hand, it has always been weird to write Java without an IDE at TopCoder Open finals, so I'm glad I won't have to do that anymore. On the other hand, the TopCoder Open competition used to be a completely unique experience - coders entering the arena with nothing but their minds and simple text editors, and finding out who can solve problems faster and better; now it's becoming more similar to the online competitions.

On Sunday, the third round of the Open Cup took place (results). In a funny coincidence, one the hardest problems of this round (problem 10) relied on the fact that the area of a polygon can be represented as f(e₁)+f(e₂)+...+f(e_m), where e₁, e₂, ..., e_m are its edges. This is precisely the fact that allowed the linearity of expectation to work in last week's TopCoder problem I mentioned.

Let me remind you of the problem statement: you are given 50 points on the plane, with each point assigned a probability that it exists. What is the expected area of the convex hull of existing points?

The convex hull is a polygon, and thus its area can be represented in the above form - as a sum of functions of its edges (with each function being the area of the directed triangle or the directed trapezoid - see http://en.wikipedia.org/wiki/Polygon#Area_and_centroid, for example). We can even look at this function as the sum of functions g(u, v) over all pairs u and v of our points. This function will be equal to f(uv) for edges uv of the convex hull and 0 for all other pairs. And here comes the linearity of expectation: finding expected value of the sum of g(u, v) is equal to finding the sum of expected values of g(u, v)! Finding the expected value of g(u, v) for the given u and v is relatively easy: it's equal to f(uv) * p(uv is an edge of the convex hull). Finally, the probability that uv is a (directed) edge of the convex hull is obtained by multiplying the probabilities that u and v exist by the probabilities that all points that would stop uv from being an edge of the convex hull don't exist. Such points are those lying on the line uv outside the segment uv, plus points on the "wrong" side of line uv.

For further clarification, here's my solution from the competition in full:

public double expectation(int[] x, int[] y, int[] prob) {
    double res = 0;
    int n = x.length;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) if (i != j) {
            int x1 = x[i];
            int y1 = y[i];
            int x2 = x[j];
            int y2 = y[j];
            double pr = prob[i] * prob[j] / 1000000.0;
            for (int k = 0; k < n; ++k) if (k != i && k != j) {
                int x3 = x[k];
                int y3 = y[k];
                int z = (x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1);
                boolean bad = false;
                if (z > 0) bad = true; else if (z == 0) {
                    int z1 = (x3 - x1) * (x2 - x1) + (y3 - y1) * (y2 - y1);
                    int z2 = (x3 - x2) * (x1 - x2) + (y3 - y2) * (y1 - y2);
                    if (z1 < 0 || z2 < 0) bad = true;
                }
                if (bad)
                    pr *= (1000 - prob[k]) / 1000.0;
            }
            res += pr * ((x1 - x2) * (y1 + y2)); 
        }
    return res / 2;
}

And here's the editorial with a much more detailed and careful explanation, although that solution is a bit more complex.

Thanks for reading, and come back next week!