Judging the Southeast Region

We believed that this was the hardest problem in the set, and that belief was proven when no team solved it. It requires a knowledge of graph theory, and a bit of math & statistics.

Here’s the Judge Input, the Judge Output, the main Solving Program, and another in Java, and one in C++.

A description of a solution awaits in the spoiler.
[spoiler]
We need to compute the expected number of steps to reach an exit. Expected Value is a well-known thing in Statistics. The Expected Value of anything is ∑p(k)*v(k), where p(k) is the probability of k happening, and v(k) is the value of k. It only works if you add this up for all possible values of k. In other words, ∑p(k) = 1.

OK, back to the problem at hand. We’ll adopt this strategy: Pick a number x. If we’re closer to an exit than x, then go straight there, otherwise, teleport. We’ll need to find the expected number of steps in terms of x, E(x), and then find the x which makes that the lowest it can be.

First, a bit of notation. I’m not good enough with HTML to do a full, proper summation notation. Heck, it’s all I can do to get the sigma in there. But all of our summations will be over the same limits: k = 0 to x. So, whenever you see a ∑, just imagine that it has a little k=0 below it, and a little x above it.

OK, onward. Let p(k) be the probability that we’re on a square that’s exactly k steps from the exit. If k≤x, we go straight to the exit, and the number of steps is k. If k>x, we teleport, which costs us a step, and then we end up right back in the same boat. So our expected number of steps is:

E(x) = p(0)*0 + p(1)*1 + p(2)*2 + …. + p(x)*x + p(k>x)*(1+E(x))

Yeah, I know, E(X) is defined in terms of E(X). We’ll fix that later. For now, lets figure out p(k>x). Well, that’s just 1-p(k≤x), and p(k≤x) is just ∑p(k) (remember my lazy notation). OK, that gives us:

E(x) = ∑p(k)*k + (1 – ∑p(k))*(1 + E(x))

Doing a little bit of algebra, we can solve for E(x):

E(x) = (∑p(k)*k + 1 – ∑p(k)) / ∑p(k)

OK, we know what p(k) means, but how do we compute it? Well, this is where we’ll need a little graph theory. The problem says that teleporting to any open square is equally likely, so p(k) is simply count[k]/total, where count[k] is the number of squares that are k away from an exit, and total is the total number of open squares. We’ll do a little breadth-first search to figure out the number of squares that are k away.

Initialize a 2d array of distances to something unreasonably large. Set count[0] to be the number of exits. Then, set the distance of all the exit squares to 0, and put them all on the queue. When you take something off the queue, set d to its distance. Look at the cells up, down, left and right. If the cell there has a distance greater than d+1, set its distance to d+1, increment count[d+1], and put the cell on the queue. That’s it. Once the queue is empty, every square will have its correct distance, and you’ll have counted all of the count[k]‘s (and, total, while you’re at it.)

OK, so here’s the algorithm in a nutshell:

1. Use BFS to calculate count[k]‘s, total, and the distance of every open square.
2. Go through all possible values of x and find the smallest E(x) (call it mindist)
3. For the input starting location, check its distance. Print the smaller of that distance (going directly to the exit) and 1+mindist (taking a step to teleport)

[/spoiler]