Judging the Southeast Region

This post is to discuss additional activities at regional contests. More content forthcoming, as soon as the minutes are available.

Here it is – the 2010 problem set. You can download the text from here.

The Southeast USA Regional Programming Contest will be held on Saturday 6 November this year, and I will once again be Chief Judge.

As usual, the Problem Selection Committee will be responsible for putting the problem set together. The PSC will also be responsible for judging, so problem providers won’t have to judge. Because of this, you can provide a problem, and also coach your team, and attend the contest with them at your chosen site. Anyone can submit a problem for consideration – however, although a problem submitter can also act as a coach, they cannot be a contestant, whether or not their problem is chosen for the set. In other words, if a student submits a problem, they are ineligible to compete.

Candidate problems should be e-mailed to me (at vanb@vanb.org). A statement of the problem is all that’s necessary, either in text or in MS Word format (right in the e-mail is fine). If you wish to include a solving program and/or test data, that’s very, very helpful, but not necessary. If you have a rough idea and want to talk about it, feel free to e-mail it to me, and I’ll be happy to work with you.

Problems should be sent by 13 September to be eligible for consideration. I’ll remind you again, but I’m sending out the call for problems early, to get you thinking!

Below you will find an excerpt from the Call for Problems issued from World Finals this year. It’s a good set of guidelines for candidate problems. If you are thinking of submitting a candidate problem for Southeast Regionals, you should read through it. I will add a couple of constraints of my own:

1. The problem should be original. It should not be a restatement of a problem that has been used previously in the Southeast USA, or any other ICPC regional, World Finals, or other contest environment such as TopCoder or Google CodeJam. It also should not come from a book, such as “Programming Challenges.” If it has its own Wikipedia page, then it’s too well-known.
2. The output for any given input should be unique. Try to add constraints to your problem so that there is exactly one answer for each input case.

Based on suggestions from last year’s regional contest, I have started a blog to talk about judging at our contest. It’s at:

http://serjudging.vanb.org

Feel free to drop by and give suggestions – however, do NOT post candidate problems on this site. It is open to everyone, including students. Any problem posted on the site cannot be used in the contest.

————- Some excerpts from the World Finals call for problems: ————-

Problem Statements

1. Each problem must be unambiguously described in English.
2. All problems must require input.
3. Unless the core of the problem is input/output related, the formats chosen for input data and the displayed results should be relatively simple. Still, the format of the input data and the appearance of the expected displayed results must be described in suitable detail.
4. Multiple data sets testing different cases are appropriate; make the problem statement include iterative data sets as input to avoid using separate input files.
5. Anticipate questions about special cases. Where appropriate, explicitly state that certain special cases will not appear in the input data. It is not necessary to specifically identify the special cases that will appear.
6. Indicate the precision that is required for real results.
7. Contestants must write solutions for problems in a short time. While very simple problems are not appropriate, neither are problems that require a great deal of code; a few hundred lines of Java or C should be an upper
   limit on what can be expected in a solution.
8. The program and chosen test data should not require excessive execution time. Contestants’ solutions may be less efficient than yours and so a generous margin is allowed for execution. If your test data requires the program to execute for a long time, then incorrect student solutions (e.g., those with infinite loops) will take an excessively long time to judge. We would like to avoid those situations.
9. The problem description (excluding sample input/output) should generally require at most one page.

Submission of Problems, Solutions, and Test Data

1. Use electronic mail and send all files as either MS Word documents, or flat ASCII.
2. Do not put your name in documents, or the body of e-mails, containing the problem statement, solution, or test data. This will simplify the transformation from your form to the one used for ranking.
3. Be discreet about problem statements and solutions. It is not appropriate to discuss problems with people not involved with the contest.

We considered this problem an E/F, World-Finals level of difficulty. There were 3 correct solutions – on only 7 submissions, and the first came only 65 minutes into the contest. It had the highest solution percentage of any problem outside of the two A/Bs (Knitting and Minesweeper). That means that few teams knew how to solve it, and few tried, but those who knew it, knew it well, and got it quickly and accurately.

Take a look at the Judge Input, the Judge Output, the main Solving Program, and another java solution.

A solution is in the spoiler.

[spoiler]
The key to understanding this solution is to see a column of the mosaic as a bitmap – with the bit set (=1) if there’s a tile there, and unset (=0) if not. Since there are at most 10 rows, that gives us 1024 possible bitmaps, which is manageable.

Try to build a Mosaic, column by column. Since the pieces are 2×2, you can’t fill a column without leaving some residue in the next column. So, you need to figure out, for any bitmap j representing a residue from the last column, how many ways can we fill this column and leave a residue of bitmap k in the next column? The following picture illustrates one way of filling 1001101001 (617) and ending up with 1111011110 (990).

Here’s an interesting thing – that depends only on the number of rows. So, you can compute all of that a priori, before you start reading the data, rather than doing it over and over for each data set. A recursive algorithm will do the trick.

Once you’ve got that computed, then for each input, you need to fill the columns so that you start with a bitmap of 0 (on the edge, no residue), go through m columns, and end up with a bitmap of 0 (no residue – nothing hanging off the edge of the mosaic)

     
// Assume n rows and m columns.
// Let p be the number of bitmaps if there are n rows.
// So, p = 2^n, or 1<<n
int p = 1<<n;
       
// Let next[k] be the number of ways of achieving bitmap k
// on the next column
int next[] = new int[p];

// We'll start at the very beginning (a very good place to start)
// with one bitmap of 0, and no others.
next[0] = 1;

// Go through all of the columns
for( int i=0; i<m; i++ )
{
    // Swap current and next - last iterations' next[]
    // is this iteration's current[]
    int temp[] = current;
    current = next;
    next = temp;
            	
    // Start afresh
    Arrays.fill( next, 0 );
            	
    // Go through all possible bitmaps.
    for( int j=0; j<p; j++ ) if( current[j]>0 ) for( int k=0; k<p; k++  )
    {
        // Assume that ways[n][j][k] is the number of ways of getting from 
        // bitmap j to bitmap k if there are n rows. (In the actual code, a linked list 
        // is used for efficiency, since this matrix will be sparse.)
        //
        // If there are current[j] ways of getting to bitmap j on the current column,
        // and ways[n][j][k] ways of getting from there to bitmap k, then we've
        // just found current[j]*ways[n][j][k] more ways of getting to bitmap k
        // on the next column. So, add them in.
        next[k] += current[j] * ways[n][j][k];

        // Mod to keep the numbers manageable.
        next[k] %= 1000000;
    }
}

// We're done! How many ways were there of achieving bitmap 0
// on the last iteration - that is, we nicely filled in the mosaic with
// nothing hanging over?
System.out.println( next[0] );

[/spoiler]

We had wanted this problem to be a Dynamic Programming problem, and early versions of it had large input limits that would force DP. However, other constraints caused us to put limits on it, making it solvable by other means. It was in our “second wave” of problems. The “first wave” was Knitting and Minesweeper – every team that solved one or two problems solved one (or both) of those two. This problem and “Euclid” made up the second wave – every team that solved 3 or 4 solved both problems in the first wave, and then one or two from the second wave. Every team that solved more than 4 solved both problems in the first wave, and both problems in the second wave.

OK, here’s the Judge Input, the Judge Output, the main Solving Program, another java solution, one in C++, another in C++, and one using a different technique.

Look in the spoiler for not one, but two solution ideas!

[spoiler]
The original intent was for this problem to require Dynamic Programming. Create an array best[], where best[i] is the best you can do from here to the end if you stop at target point i. Clearly, best[i] can be computed pretty simply from best[i+1], best[i+2], and so on (best[i] = Minimum over k of [1+(the cost of skipping targets between i and i+k) + (the Euclidean distance between i and i+k) + best[i+k]]. ). So, start at the end, work back to the beginning, and best[0] is your answer.

The numbers were small enough, however, that a simple, best-first-search shortest path (aka Dijkstra’s Algorithm) would work. Define the “Distance” between two targets as 1 + (the Euclidean distance) + (the cost of skipping targets in between). Then, just run Dijkstra’s Algorithm and voila.

Note: in both cases, the “1+” is for the one second that the robot must stop on a target point.
[/spoiler]

Pool Table was one of our tougher, E/F problems. There were two parts to the problem – figuring out that distance, and making sure you didn’t hit the target ball too soon.

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

Take a look in the Spoiler for solution ideas.

[spoiler]
For the first part, finding the distance, it’s easier to not try to compute reflections, but rather to set up a coordinate system of reflected pool tables. Let dx and dy be a number of pool tables over, and up. If n is the desired number of bounces, then look at all reflections where |dx|+|dy|=n.

For example, if n=2 bounces, instead of this:

See it as this:

Then, look at all reflections where |dx|+|dy|=n (for our example of n=2, they’re the lightest colored ones in the example above), and just calculate the straight linear distance between the cue ball and the reflection of the target ball. Be careful about the position of the target ball in the reflection!

Then, the second part of the problem is to make sure that there are no reflections of the target ball that get in the way – that is, no chance of hitting the target ball too soon. You’ve got to check that no reflection of the target ball (including the original!) is collinear with the cue ball and the reflection you’re trying to hit AND between them.

Here’s a case that caught a few teams: consider a large table, with the cue at (1,1) and the target at (2,2), with n=2 bounces. The correct answer is to shoot at the corner at (0,0), and have the cue bounce straight back to the target. Several teams failed this particular test. It’s because, in checking to see if an earlier version of the target blocked the shot, they only checked collinearity, not betweenness. Here, the original target ball is collinear with the cue and the reflected target, but it is not between them!
[/spoiler]

This problem turned out to be harder than we expected. We rated it a C/D, yet only 2 teams managed to solve it, the first coming about three and a half hours into the contest. It’s really not a difficult algorithm, but it’s off the beaten path, and requires some thinking and some care.

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

Look in the spoiler for a description of a solution.
[spoiler]
Use a Greedy algorithm. First, assume that the trees are laid out right next to each other, as tightly as possible. Then, find the positions of the smallest and largest trees – let’s say s and t – and then try to stretch the gap between s and s+1 as far as possible, then the gap between s+1 and s+2, then s+2 and s+3, all the way up to t-1 and t. Look at all pairs of trees that are adjacent height-wise (that the Ninjas would jump between) that span each of those gaps, to see how far the gaps can be stretched.

The only way the Greedy algorithm can fail is if stretching an early gap limits your options of stretching a later gap. I’m not going to go through a convoluted argument, but it’s true. It’s left as an exercise to the reader to confirm!
[/spoiler]

It’s just Minesweeper. Everyone knows Minesweeper. This problem was solved by more teams than any other.

Check out the Judge Input, the Judge Output, the main Solving Program, another solution, and another. There are also C++ solutions here and here.

[spoiler]
The algorithm is obvious – just do what the problem says. For every non-mine cell, look at the (up to) 8 cells around, and count the number of mines. So, the key to solving this problem is just to be careful about certain things.

• Don’t go off the edge of the board when you’re checking edge cells and corner cells
• For some, correctly convert an integer to a char (others just printed the int directly). In both C++ and Java, this will work: ch = (char)(x+’0′)
• Make sure your output spacing is correct.

[/spoiler]

Knitting was one of the two easiest problems in the set (Minesweeper is the other), and was solved by most teams.

Here’s the Judge Input, the Judge Output, the main Solving Program, another solution, and another.

There’s a pseudocode solution in the spoiler.
[spoiler]
The only real trick is to recognize that the numbers are so small that you don’t need fancy math. Just iterate through it.

    Input numberOfRows, firstRow, numberOfDeltas, deltas
    stitchesOnRow = firstRow
    total = 0;
    For i = 0 to numberOfRows-1
        total = total + stitchesOnRow
        stitchesOnRow = stitchesOnRow + deltas[i mod numberOfDeltas]
    End
    Print total

[/spoiler]

This was the hardest problem in the set. No team solved it, although several came close. Here’s one bit of trickyness that bit some teams – the problem states:

These time intervals may overlap. The union of all time intervals provides the complete set of times at which the guard is available.

If a guard says they’re available from 2:05 to 3:15, and also from 3:10 to 4:20, then they are available for the 3:00 to 3:30 time interval. Some teams did not perform this union correctly.

Here’s the Judge Input, the Judge Output, the main Solving Program, another solution, and another.

[spoiler]
We’ll frame this as a Max Flow problem, but with a twist. We’ll start with a brief discussion of Max Flow problems.

Consider a directional, weighted graph that has a special node called the ‘Source’, and another called the ‘Sink’. Consider the weights to be a ‘capacity’. Think of each edge like a one-way pipe, and the ‘capacity’ is the most stuff you can push through that pipe. (The internet is a series of tubes, right?) Well, the question is… How much stuff can you push from the Source to the Sink, given the limited capacities of all the edges?

The solution technique for a Max Flow problem is called Ford-Fulkerson, and I’ll only give a brief outline of it here.

First, for every edge A⇒B, create a dual edge, B⇒A, which starts with 0 capacity. The way to think of A⇒B and its capacity is: How much capacity is available to use. The way to think of B⇒A and its capacity is: How much capacity has been used, that I could give back if I had to. That’s why B⇒A starts out as 0 – because, at the beginning of the algorithm, you haven’t done anything, so you haven’t used any capacity.

Now, find a path from the Source to the Sink, only traversing edges that have some capacity (that is, capacity>0), and don’t hit any node more than once. You can find this path any way you like, but Breadth-First Search has become the standard.

When you’ve got a path, go back over the edges on the path, and find the one with the smallest capacity. That’s the most stuff you can push through that path, right? That’s the weakest link. Then, go back over the path again, and move that amount of capacity from each edge to its dual (that is, subtract it from each edge, add it to each edge’s dual).

Keep doing this (finding paths, finding the min capacity, moving that capacity from each edge to its dual) until you can’t find a path with >0 capacity. Then, you’re done! The total amount of capacity that you moved over all the paths you found is the Max Flow!

OK, so how do we see Museum Guards as a Max Flow problem? Well, the ‘stuff’ we’ll flow through the system is guard-periods. Build two kinds of nodes, for guards, and for time periods. Link the Source to each guard, with the capacity being the number of time periods that guard is able to work. Link a guard to a time period if the guard is willing to work that time period, with capacity 1. Finally, link the time periods to the sink. What should the capacity for those edges be? Well, that’s tough. We could set them all to n, and see how many guard-periods flow through – but we have no way of forcing the guard-periods to be balanced over the time periods. Some periods could be over-represented, and some under-represented. The result wouldn’t be meaningful. Hmmm….

Consider this: If we set the capacity of each of those links to some value x, 0≤x≤n, and we get a total flow of x*48 (48=number of 30 minute periods in a day), then we know we can cover all time periods with x guards. The only way to geta total flow of x*48 is to get a full x from each of the 48 time periods. We can’t get any more from one time period (and less from another), because we’ve set the max capacity from each time period to the sink to x. That’s our hook. We just have to do repeated Ford-Fulkersons to find the largest value of x which leads to success.
[/spoiler]

This one was just Math. Some teams solved this very quickly, others struggled with it. It was still one of the 4 most solved problems. There were several ways to approach it, which you’ll see in the spoiler.

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

[spoiler]
I’ll talk about three different solutions, but all of them have one thing in common. They all express points G and H, (and, more specifically, their coordinates Gx, Gy, Hx and Hy) parametrically in terms of a parameter t. This parameter represents how far along ray AC point H is. If t=0, then H is right at A. If t=1, then H is right at C. If 0<t<1, H is between A and C. If t>1, then H is further away from A than C is. Once we know t, we can figure out all the coordinates like this:

Hx = Ax + t*(Cx-Ax)
Hy = Ay + t*(Cy-Ay)
Gx = Bx + t*(Cx-Ax)
Gy = By + t*(Cy-Ay)

The first solution, in euclid.java, is a closed-form solution using more trig than anything else. It uses Heron’s formula to get the area of triangle DEF. It then uses the Law of Cosines to get the cosine of angle CAB. Using the distance of line segment AB (we’ll notate that |AB|), and our target area, we can compute the height of the desired parallelogram as area/|AB|. Since we know the cosine of CAB, we can easily compute the sine, and then use the Law of Sines to get the distance we need along ray AC. Then, t = distance / |AC|. The rest is as above.

The second solution, in euclid_binary.java, uses an age-old trick to get the area of any polygon. For every edge (x1,y1) to (x2,y2), add up (y2+y1)*(x2-x1). The area of the polygon is one half of the absolute value of that. Or,

area = 0.5*|∑(y2+y1)*(x2-x1)|

It uses that trick to get the area of triangle DEF. It then uses that trick to get the area of a parallelogram given parameter t, and uses Binary Search to nail down the correct value of t.

The third solution, in euclid_chinmay.java, uses the fact that the magnitude of the cross product of two vectors (with the same base) gives the area of the paralellogram defined by those two vectors. Also, half of that would be the area of the triangle defined by those two vectors. So, the area of triangle DEF is 0.5*|DExDF|. The area of a parallelogram defined by CAB is |ACxAB|. Then, just let t = 0.5*|DExDF| / |ACxAB|, and we have our answer. This works because the area of the parallelogram we seek will be linearly related to the distance that H is from A along AC.

The other solutions, euclidYiu.java and euclid.cpp, use various combinations of these techniques.
[/spoiler]

This problem had a fairly standard solution, but there was some tricky bookkeeping, which is probably why so few teams solved it. It particular, there were two issues that caught teams.

First, a lot of teams didn’t reset the board correctly when moving pieces. For example, suppose that both pieces A and B can move. Some teams wrote programs that would move piece A all the ways it could move, but would forget to put it back where it started before trying to move piece B.

The other catch was a little more tricky. A lot of teams wrote code that checked to see if the special piece could be moved all the way to the right. They figured that if you could move it there, you could just keep moving it and slide it out. And, most of the time, they would be right – but what if the special piece starts out all the way on the right side of the board? A lot of teams would answer 0 – that is, 0 moves. That’s incorrect. It always takes at least 1 move to remove the special piece.

Check out the Judge Input, the Judge Output, the main Solving Program, another solution, and another.

Join me in the spoiler for an outline of a solution.
[spoiler]
It’s just a breadth-first search. Despite the small size of the board and the limitations on how pieces move, the search space can still get quite large, so if you tried to use Depth-First Search (that is, you tried to solve it recursively) you probably ran out of time.

Create a queue of states. Each state has a board, and a number of moves. Start by putting a state on the queue that has the starting position, with 0 moves.

Each time you take a state off of the queue, check to see if the special piece is all the way to the right. If so, remember the number of moves, and exit the loop. Otherwise, generate all possible boards that can be attained in 1 move. For each, check to see if it’s been seen before, and if not, put it on the queue with a number of moves equal to this state’s number of moves plus one.

When you’re done, output the number of moves remembered, unless it’s 0, in which case output 1, or if you emptied the queue without reaching a solved state, output -1.

Sounds simple in paragraph form, but it’s not necessarily easy to generate all of the possible moves – remember, a lot of teams didn’t reset the board correctly. Also, remembering previously seen board positions is important, otherwise you’ll run out of time and memory.
[/spoiler]

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]