Judging the Southeast Region

This was another of the World-Finals-Hard problems (along with Teleport and Lawrence), and another that wasn’t solved by any team.

You can check out the Judge Input, the Judge Output, the main Solving Program, a C++ solution, and another in C++.

Check out the spoiler for a solution outline.

[spoiler]
There’s a lot of words in this problem, but when you pick through them all, it boils down to a highly recursive algorithm with memoizing to keep it reasonable.

Look at the input cell structure of the worm as an array of characters. In C or C++, that’s natural. In Java, it might be easier to deal with it as a char[] rather than a String. Now, write a method fastest( i, j, ch ) which will tell you the least number of days it would take to generate the cells in the array from index i to index j (inclusive) if you start with cell ch. If n is the number of cells in the input cell structure, then the minimum of fastest( 0, n-1, ch ) over all possible starting cells ch is the final answer. So what does fastest( i, j, ch ) look like?

Well, if i==j, then look at the i^th cell in the input structure. If that is equal to ch, then we’re there already – it takes 0 days. If it isn’t, then it’s impossible. We’ll use an unreasonably large number to signify this – say, 10000.

If i<j, then we’ve got to use a rule. We’ve got to look at all rules of the form ch ⇒ A B, and then we’ve got to look at all ways of splitting that substring from i to j in two, and see how long it takes to use A to generate the first part, and B to generate the second part. Since those can happen in parallel, we’ve got to look at the maximum of the two – and then add one, for the day that the ch ⇒ A B expansion happened. We’ll take the best (i.e. smallest) of all of those.

Here’s that idea in pseudocode:

fastest( i, j, ch )
Begin
    If i==j Then
        If structure[i]==ch Then
            result = 0
        Else
            result = 10000
        End If
    Else
        best = 10000
        For Every Rule of the form ch ⇒ A B
            For break = i to j-1 Do
                days = 1 + Maximum( fastest( i, break, A ), fastest( break+1, j, B ) )
                If days < best
                    best = days
                End If
            End For
        End For
        result = best
    End If
    Return result
End fastest

Of course, this is massively recursive - but we can use memoizing to reduce the burden. Create an array memo[i][j][ch] to store the results. Since the initial cell structure is at most 50 cells long, and there are at most 20 kinds of cells, that makes the array at most 50x50x20 in size, or 50000, which is easily tractable. That also means that there are at most 50000 values we need to compute, also tractable. Initialize this array to be all -1's - that will be our flag that the real value hasn't been computed yet. Then, modify fastest like this:

fastest( i, j, ch )
    If memo[i][j][ch] < 0 Then
        Do all that other stuff
        memo[i][j][ch] = result
    End If
    Return memo[i][j][ch]
End fastest

And, that's it. We won't go any further down in the recursion if the value has already been computed.
[/spoiler]

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]

This problem was not one of the problems we had considered to be World-Finals-Hard, but yet no team solved it. This was disappointing. The fundamental algorithm is actually pretty simple – but the input numbers were so large that the solution needs some trickery in order to complete in time. That trickery introduces a bit of tedium and boundary cases, which is probably why no team managed to solve it.

Check out the Judge Input, the Judge Output, the main Solving Program, and another in Java, and one in C++.

A solution outline follows in the spoiler.
[spoiler]
The fundamental algorithm is simple:

For Each Tree
    Find the closest horizontal path north of this tree
    See if there are any trees with the same X between this tree and the path, blocking the view
    Find the closest horizontal path south of this tree
    See if there are any trees with the same X between this tree and the path, blocking the view
    Find the closest vertical path east of this tree
    See if there are any trees with the same Y between this tree and the path, blocking the view
    Find the closest vertical path west of this tree
    See if there are any trees with the same Y between this tree and the path, blocking the view
    If all four views are blocked, then the tree can't be seen
    Else it can be seen, add one to the Visible count
End For 

The problem is the large number of paths and trees. Locating the closest paths, searching through to see if any trees block the view, can add up to O(n^2), and with the data set size, that just won’t do.

There’s a simple trick that we’ll use to cut down on the iterations – sorting. First, separate the paths into horizontal (by Y) and vertical (by X), and sort each of these lists. For any tree, the paths immediately north and south will be next to each other in the horizontal array. Ditto for the east & west in the vertical array. Finding both north and south is just a binary search, O(logn). Same for east and west.

Now, about the trees. Start by sorting them by X, then Y. What I mean by that is: sort them by X, but if two trees have the same X, then use Y as a tiebreaker. Now, all the trees with the same X are grouped together, ordered by Y. That means that, if any tree is going to block the next path north, it’s going to be the next tree in the list, and likewise, for south, it’ll be the tree immediately previous. It’s cost us O(nlogn) to sort the list, but finding the tree that blocks the view (if there is one) is reduced to O(1). For east/west, it’s the same deal, but we must re-sort the list by Y, then X.

That’s about it. There are lots of boundary conditions to consider – what if there’s no path to the north? or south? or east? or west? what if there’s no next/previous tree? Lots of care must be taken, but the algorithm, at its core, is really pretty simple.
[/spoiler]

This was a simple simulation. No fancy algorithms, just do what you’re told. Unfortunately, that turned out to be harder than we thought. It seems that a lot of our competitors didn’t know how to play Blackjack. That’s probably a good thing. We tried to explain it thoroughly in the problem statement, but we still got a lot of questions, like:

When is an Ace 11, and when is it one? Who chooses, and when?

Do we have to decide when we get the Ace whether it’s going to be 11 or 1?

What happens when we have, say an A=11 and a 5 for 16, but then we get a 9?

How does the dealer choose whether to take a card or not?

If the player has 14 and the dealer has 16, why wouldn’t the dealer stand?

OK, no more Blackjack problems in the SER.

For the Ace = 1 or 11 questions, an Ace counts for 11 unless that would cause a bust, in which case it counts as 1. There is no decision to be made. It’s automatic – in the rules. When does it change value? As soon as a new card is dealt. If you have A5, your hand is worth 16. If you are then dealt  a 9, your A59 hand is worth 15. If your hand has more than one A, then your hand will have the max value possible without busting. Since 11+11=22=bust, that means that at most one of your Aces can count as 11, all the rest are 1.  Which one? It simply doesn’t matter. Pick one.

Here’s another way to look at it: Since Aces can be worth 1 OR 11, if you have an Ace in your hand, then your hand could have different scores. the House will always use the best possible score for any hand – that is, the closest to 21 without going over.

The Dealer’s behavior is completely deterministic. The Dealer has no choice. S/he MUST take a card if his/her score is less than 17. S/he MUST stand if his/her score is greater than or equal to 17. That’s also in the rules. The Dealer is not allowed to think about it, or react to the players’ hands.  <17, Hit. >=17, Stand. That’s it.

The most frequent logic problems we saw had to do with saving and restoring the state of the system each time you try a new possibility. Most often, it was the Dealer’s hand that didn’t get saved and restored correctly.

Here’s the Judge Input, the Judge Output, the main solving program, another Java program, and a C++ program.

It’s not much of an algorithm, but if you need more, there’s some pseudocode in the spoiler.

[spoiler]

Deal first card to Player
Deal second card to Dealer
Deal third card to Player
Deal fourth card to Dealer
Save the Dealer's hand!
While player hasn't won and hasn't busted
    Save the state of the deck
    Restore Dealer's hand
    While Dealer's hand value < 17
        Deal next card to Dealer
    End While
    If Player score >= Dealer score OR Dealer score > 21
        Player wins!
    Else
        Restore the Deck
        Deal next card to Player
    End if
End While

It’s probably smart to use the same logic for dealing a card to the Player and to the Dealer. The score of the hand is computed the same way for both of them. Here’s some pseudocode for that:

If the Card is an Ace
    Add 11 to the Score
    Add 1 to the Number of Aces counting as Eleven
Else
    Add the Value of the Card to the Score
End If

While the Score > 21 AND the Number of Aces counting as Eleven > 0
    Subtract 10 from the Score
    Subtract 1 from the Number of Aces counting as Eleven
End

[/spoiler]

This was the simplest problem in the set. It was originally going to be one of the practice problems, but when one of the judged got confused about Combination Lock, we knew we needed something easier, and Lotto got promoted.

Here’s the Judge Input, the Judge Output, the main solving program, another Java program, and a C++ program.

If you really need it, there’s a solution outlined in the spoiler.
[spoiler]
You can completely ignore the concept of “tickets” – just read in 6n numbers. Java’s Scanner will do this easily, and I believe C++’s cin will as well. You’re just making life harder on yourself if you’re reading a whole line and then parsing it into 6 integers.

You can just keep a boolean array and count the trues – say Yes if there are 49 of them – or, just keep a set (like Java’s HashSet). Shove the numbers into a set as you read them, and at the and, say “Yes” if the set has 49 elements.

[/spoiler]

Combination Lock was originally going to be the simplest problem in the set. Then, one of our judges got confused about it, and we realized we needed a simpler problem (Lotto).

The confusion comes because the numbers are on the dial, and the arrow on the lock, not the other way around. So, when you turn the lock clockwise, the numbers go down, and counterclockwise, they go up. This was confusing to many people.

Here’s a question we got a lot:

Where does the dial start?

The answer is that it starts at the worst possible place for it to start, which would be n-1 away from t1. This is stated in the problem:

You must find the maximum possible number of ticks the dial must be turned in
order to open the lock.

Here’s the Judge Input, the Judge Output, the main solving program, another Java program, and a C++ program.

A solution waits for you in the spoiler.

[spoiler]
The worst possible case is that you start out n-1 away from t1.
Tally up the number of clicks like this:

Note: How many clicks is it from t1 to t2? Well, turning the dial counter-clockwise, the numbers go up. If t2>t1, then you just go straight from t1 to t2, and the answer is t2-t1. If t2<t1, then you go up from t1 to n (which is the same as 0), and then from 0 to t2. That’s n-t1 + t2. Either way, (t2-t1+n)%n covers it.

To go to from t2 to t3, it’s the same logic, except the dial is spinning the other way and the numbers go down. Then, you get (t2-t3+n)%n.
[/spoiler]

An All Math All the Time problem. But, there are ways to solve it with only minimal math knowledge.

There is one bit of a sticking point, that caught some teams. The problem asks you to sort the answers by area, and by perimeter if the areas are equal – which means you have to compare real numbers. Comparing real numbers for equality in a program in problematic, because of roundoff error. You always need a tolerance. So, in Levees, what should the tolerance be? The problem tells you:

If two Quadrants have the same area when rounded to 3 decimal places, output the one with the largest perimeter first.

Some teams got caught by this, put answers in the wrong order when the areas were too close. In the judges’ programs, you’ll see that often, the judges converted the reals numbers to strings and then sorted the strings to get around this problem.

So, here’s the Judge Input, the Judge Output, the main solving program, a C++ program, and another C++ program.

Some solution ideas are inside the spoiler.
[spoiler]
First, you’ve got to find that middle point – the intersection of the two diagonals. Note that since the polygon is guaranteed to be convex, the diagonals are guaranteed to intersect at a single point inside the figure. Convenient! The main judge program uses Cramer’s Rule. There are other ways.

Once you’ve got that point, the perimeters are easy – just use the distance formula for each leg of each triangle. You can use your favorite technique to get the areas of the triangles – Heron’s formula, one half the cross-product of any two side vectors which share an endpoint, the programmer’s standard polygon area trick, you name it.

Then it’s just a matter of sorting the results, with the caveat described above.
[/spoiler]

Lawrence was one of the three “World Finals” level problems in the set. Only two teams managed to solve it. It’s a shining example of a Dynamic Programming problem, with a little bit extra.

Here’s the Judge Input, the Judge Output, the main solving program, another Java program, and a C++ program.

Jump into the spoiler for an outline of a solution.
[spoiler]
This is a simple 2D dynamic programming problem, with the number of attacks being one dimension, and the depots being the other. The trick is to precompute the costs of leaving the rail line intact between every pair of depots BEFORE you get into the DP loops (or recursion). If you try to compute these on the fly, you’ll end up going over the same territory too much, looping and looping, and running out of time.

Here’s how you can compute the costs. sum[a][b] (a<=b) is the sum of strategic values of depots a through b, and cost[a][b] (a<=b) is the cost of leaving the railroad connected from depot a through depot b. stations[i] is the strategic value of station i.

            for( int j=0; j<n; j++ )
            {
                sum[j][j] = stations[j];
                cost[j][j] = 0;
                for( int i=0; i<j; i++ )
                {
                    sum[i][j] = sum[i][j-1] + stations[j];
                    cost[i][j] = cost[i][j-1] + stations[j]*sum[i][j-1];
                }
            }

To do the DP, it’s easiest to write a recursive function and memoize it. Check out the main judge program for details – it uses a method called place( attacks, start ) which returns the best score Lawrence can obtain by starting at start if he has attacks attacks remaining. The limits that the problem places on these makes it feasible to use a big memoizing array.
[/spoiler]

This problem surprised us, in many ways. Firstly, we knew that the algorithm wasn’t complicated, but we thought it would take a while for competitors to come up with it. We were wrong – Heart started coming in very early. Also, a bit of wording caused us some headaches. The problem says:

Graphia erected prosperous cities and connected them with a network of highways.

In the next paragraph, the problem statement says:

Graphia consists of several cities, connected by highways.

Nowhere does it say that it is a connected graph, in the sense of the graph theory jargon! It just says that it’s a graph – a bunch of cities with highways between them. Even if you stretch your imagination, this is all talking about the starting graph, not the Heart. Here’s the definition:

More formally, a city is defensible if it can draw a total of at least K troops from
itself, and from cities directly adjacent to it. A set of cities is defensible if every
city in it is defensible, using only troops from itself and adjacent cities in that set.
The Heart of the country is the largest possible defensible set of cities – that is,
no other defensible set of cities has more cities in it.

The definition of the Heart is very precise – and NOWHERE does it say that the Heart is a connected graph! In most cases, the Heart will NOT be connected. Before the contest, we removed any disconnected graphs from the judge input – but many of the judge outputs were not connected graphs. many competitors spun their wheels looking for a Heart that was connected. I feel a bit badly for the students who misread the problem, but not too much. If they had read the problem carefully, rather than just skimming it for keywords, they wouldn’t have had an issue.

This question came up a lot:

Suppose you have two different sets of nodes which could both be the heart – they’re the same size, and they consist of only defensible nodes. Which one is the heart?

The answer is: Neither. The Heart is unique. It’s easy to show. Suppose that A and B are two sets of defensible nodes, |A|=|B| but A!=B. Look at AUB (U=Union). That is a set of defensible nodes – every node in A can be defended by only nodes in A, so they can all be defended from AUB. Ditto with B. Also, this set is larger than either A or B. Since A!=B, there must be some things in A that are not in B, and vice versa. Then AUB is bigger than A or B. So, since there’s a larger defensible set, neither A nor B can be the Heart. I suspect that this question came from teams who were stuck on the connected issue.

Well, here’s the Judge Input, the Judge Output, the main solving program, another Java program, and a C++ program.

And, here’s the algorithm:

[spoiler]

It’s a pretty simple Greedy algorithm implemented with something like a Breadth-First Search. For each city, keep track of the total number of troops that it can call upon – that’s the number that are there, plus all of those immediately adjacent. If a city’s total troops starts out below the threshold, put it on the queue. When you take a city off of the queue, remove its troops from the total troops of all of its neighbors, and put them on the queue if they go below the threshold. Keep going until the queue is empty. The cities that are left are the heart.

[/spoiler]

This problem was solved later in the contest, and by fewer teams, than we thought it would be. The main algorithm is straightforward, but some special cases are tricky.

First, if you have resistors from P to Q and from Q to R (and no others with Q as an endpoint) then they are in series, and you can reduce them to a single resistor between P and R. However, if the middle node is one of the endpoints A or Z (e.g. P to A to R, or P to Z to R), then you can’t. Because A and Z are the start/end points, they each have an extra connection.

Second, at the end, you’ve got to make sure there’s a single resistor between A and Z, and none anywhere else. If you end up at the end with a resistor between A and Z, and another one between P and Q, that system is NOT well formed!

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

Look below for an outline of a solution.

[spoiler]

First create two arrays – a 1d array of nodes, and a 2d array of resistances between nodes. The 1d array will hold a count of the number of resistors which are connected to that node. The 2d array will hold resistances, or some sentinel value (like -1.0) if there’s no resistor between those nodes.

Now, write a method which will place a resistor into the circuit, something like place( int i, int j, double r). if there is no resistor between i and j (resistance[i][j]<0.0) then just increment nodes[i], increment nodes[j], resistance[i][j]=resistance[j][i]=r. If there’s already a resistor there, then leave nodes[i] and nodes[j] alone, and merge this new resistor with the one that’s already there using the Parallel rule. You can use this method whenever tyou place a resistor into the circuit – reading them in, or later in the algorithm. This’ll take care of all parallel resistors!

Now, let’s look for resistors in series. That’s easy – just look for a node i (skipping A and Z) such that nodes[i]==2. If a node has exactly two resistors connected, then it has to be the center node of two resistors in series! Don’t forget to exclude A and Z. Once you find one (let’s call it Q), you can look through the resistance[][] array to find which two other nodes (let’s call them P and R) are connected and the resistance between them. Then, just set resistance[P][Q]=resistance[Q][P]=-1.0, resistance[Q][R]=resistance[R][Q]=-1.0, resistance[P][R]=resistance[R][P]=(use the Series rule), and nodes[q]=0. Just keep doing this until there are no more nodes with nodes[i]==2.

Once there are no more resistors in series, then check to see if this system is well-formed. See if it reduced to a single resistor between A and Z. Check to see if nodes[A]==1, nodes[Z]==1, and nodes[P]==0 for every other node (that last part was forgotten by a lot of teams!)

[/spoiler]

Here it is – the 2008 problem set. You can download the text from here. You can also download a zip file with all of the input files, output files, solving programs, and the problem set.