B: The Heart of the Country
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]