ECNA 2001 Programming Contest
Post-Contest Comments and Hints on Problems
After the contest completed, a possible error in the judges' solution for
Problem A was brought to our attention. We found that our solution was indeed
incorrect and hence those teams that were judged to having solved Problem A
correctly were in fact incorrect. (But in the same way the judges' were
incorrect!) Two teams that had programs judged incorrect were, in fact correct. Since it is now impossible to return the programs originally judged correct,
it would be unfair to change those judgements. However, all runs judged
incorrect have been rejudged and the two new correct runs have been added to
the scoreboard. Note this does not change the ranking of the top three teams.
However, it does boost one team to fourth place.
The judges regret this mistake and take full responsibility. We believe this
resolution is the fairest.
After each problem heading, statistics for that problem are given in the form:
number of submissions/number of correct submissions/time (in minutes) of the
first correct submission
What's in A Name?
28/7/92
Correct solution:
In this problem, you are given a log from which you can deduce which
person have used which ID. When a message is sent by the ID "id",
anyone not currently in the hideout are eliminated as a potential
match for "id".
After we processed the complete log, we have a list of the potential
matches between criminal names and ID's. Now what we have to do is to
examine all possible ways of assigning criminal names to unique ID's
such that the logs are not violated, and see if some criminal names
are always assigned to the same ID's.
If we view this as a bipartite graph in which the left vertices are
the criminal names and the right vertices are the ID's, such that
there is an edge between a criminal name and an ID if the assignment
does not directly violate the log. Then a valid assignment is simply
a perfect matching in the bipartite graph. To check if a particular
criminal name can be assigned to an ID in a valid assignment, we
determine if there is a perfect matching with the particular
assignment fixed. This can be done by fixing the edge and then
computing a maximum matching and see how many edges are in the
matching. Once we have done this for all the possible criminal
name-ID assignments, it is easy to obtain the final answer.
Judges' solutions:
Unfortunately, all three judges' solutions were incorrect (in
different ways) but agreed on all test cases. In all three cases, we
missed some assignments that can be made because we either did not
examine all possible matchings or did not do so correctly. This
resulted in the judges' expected output giving "???" instead of actual
ID's for some of the criminal names in two of the test cases (A.7.dat,
A.15.dat).
Contestants' submissions:
The submissions originally judged correct agreed with the judges'
expected output, and hence they were also incorrect. Two teams with
submissions judged incorrect were in fact correct: Waterloo Black and
Waterloo Gold. All other submissions originally judged incorrect were
still incorrect.
Acknowledgements:
We thank the Waterloo's coach Gordon Cormack and their teams for
pointing out our mistake.
Problem B: Sorting It All Out
110/11/39
Keep track of the set of letters greater than and less than each letter.
You must recognize when you're sorted and when you're inconsistent.
Problem C: Web Navigation
197/94/9
This was intended to be the easiest problem. All that was required was
maintaining two stacks.
Problem D: Trees Made To Order
10/6/124
One of the two "hard" problems. You needed to generate the left and right
subtrees
recursively, as the bounds on n were too large to store all subtrees.
Finding the recurrence that gives number of the left and right subtrees
is the heart of the problem.
Problem E: Space Station Shielding
69/6/80
The first difficulty is to translate the input numbers to the
3-dimensional grid. Then a flood fill, starting at a square outside the
station and counting every
time you hit a face, will correctly count the number of exterior faces.
Care must be taken not to seep inside.
Problem F: Roads Scholar
32/7/50
Once the weighted graph is built, you need to use the shortest path algorithm,
or the all-pairs shortest path, algorithm, to find the shortest paths. You could
keep track of the actual paths (but it's not really necessary),
not just the lengths.
Problem G: Robots
2/0/
The other "hard" problem. Not conceptually hard, but there are many things
to keep track of and simulate correctly. Pushing debris is one trickier part of
the program. Looking one move ahead is useful.
Problem H: Square Ice
70/19/96
An easier problem. Probably you'll store the displayed ice in an array of
characters. First filling in the vertical and horizontal molecules and then
the angled ones can only fit in one way. (Start in the upper left corner.)