Judging the Southeast Region

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 are the responses that we use in the Southeast Region:

• Correct!
• Compile-Time Error
• Runtime Error
• Time Limit Exceeded
• Incorrect Output
• Incorrect Format
• Incorrect – Contact Staff

At first blush, they may seem pretty simple and straightforward. There can be some subtleties, though. let’s go through them:

Correct! pretty much means that the code produced the expected output. At SER, we use the PC2 contest management system. That system has an autojudger, which will render a verdict of Correct or Incorrect. When it says Correct, the judges usually just go with that. If it says Incorrect, we have to look at see why. But, even when it says Correct, it can be wrong. The autojudger can be set up to react in various ways to whitespace – at SER 2009, we told it to ignore whitespace. We know of at least one case (in 2009) of a submission of Minesweeper that had spaces between characters, and should have been judged Incorrect, but the autojudger said Correct.

Compile-Time Error is perhaps the most straightforward of all the judgments. The submitted program didn’t pass the compiler. We don’t see this much – when we do, it’s either at the beginning of the contest, when a team didn’t understand the system and sent a .class (for Java) or an a.out (in C++) instead of their source, or at the end, when they’re throwing Hail Marys at us. There is a subtlety here, though – what about interpreted languages? It can be tough to differentiate between Compile-time and Runtime errors.

Runtime Error encompasses your division-by-zeroes, your array-index-out-of-bounds, and such. This is also what we’ll give if the program tries to open a file (instead of reading from stdio), or runs out of memory, which aren’t logic errors per se. This seems obvious, but it can be a little tricky. The judges ignore stderr – so how do they know if a program crashed? Moreover, Java can throw exceptions but keep on running, in which case we ignore the exceptions – so, if a Java program stops producing output, is it because it crashed? Or, did it just not print the last test cases, and the exception was incidental? Was it a fatal or a nonfatal exception? What if a team has their end-of-input sensing code wrong, produces correct output and then crashes? Is it Correct! or is it a Runtime Error? We try to look at the code and make our best judgment on a case-by-case basis. However, I would not be surprised if we let a few Runtime Errors through with Correct! because we trusted the PC2 autojudger on a “Correct” and didn’t check stderr.

Time Limit Exceeded is the most controversial. It means the program ran too long – but what it “too long”? The judges set a time limit for each problem. There is not a global time limit – it is set per problem. The time limit is based on the programs written by the judges, running on the judge data. We usually take the slowest of the programs, and multiply its time by ten,  but there can be exceptions.  I know that there’s going to be a lot of discussion on this topic, so I will soon post an article on this alone.

Incorrect Output and Incorrect Format are given if your output doesn’t match ours. The old, conventional wisdom is that Incorrect Output is given if your answers are wrong, and Incorrect Format is given if your answers are right, but don’t match our desired format. For example, if you print your floating point numbers to 2 decimal places when we ask for 3, you’ll get Incorrect Format. We’ll also give Format if the output is so messed up, we can’t tell if the right answers are buried in there somewhere or not. This can happen if the program messes up white space and CR/LFs (and outputs a number salad), or if it included lots of debugging prints that the competitor forgot to disable.

Incorrect- Contact Staff is a response we use rarely. We use it when there’s something that the team just isn’t getting, and we want to give them some help. If they repeatedly submit their a.out, or their .class file, or they read from a file instead of stdio, or for some other reason they just don’t get it, we’ll give them this response, and then call the staff at their site to give them a heads-up. We’ll only use this well into the contest, and only for teams that are clearly not competing for the top spots.

So, what if more than one thing is wrong with a program? You will get… whatever the judge sees first. That’s right, there’s no prescribed hierarchy. If more than one of the incorrect judgments holds, you could submit exactly the same program multiple times and get different kinds of “incorrect” responses. If it’s correct, it’s correct, of course, but if it has wrong output, wrong format, and it crashes, you could get any of those three. A crashing program tends to be obvious, so more often than not, you’ll get Runtime Error in that case. Likewise, when a program has  a compiler error, it produces no output, so you’ll get Compiler Error. But, if your program prints the wrong answers, and prints them to 2 decimal places when we asked for three, you could get either Incorrect Output or Incorrect Format, depending on which the judge noticed first.

Checking the World Finals rules, it looks like they have reduced their responses. They’ve combined Compile-time Error with Runtime Error, and just give Run-Time Error. They’ve combined Wrong Answer (Incorrect Output) with Presentation Error (Incorrect Format) and they just give Wrong Answer. They wouldn’t give Contact Staff at Finals, so that’s it. Maybe we’ll go that way at Regionals next year – at the very least, you’ll probably see the elimination of Incorrect Format.

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.

Problem Assessment table:

Here it is – the 2009 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.