If you have ever been responsible for the problem set of a programming
contest, you know what a tremendous amount of time is needed to get people
to send you their problems, to have them reviewed, to have alternative sample
solutions and test programs coded, to bring them to a uniform format, and
to come up with good test cases. Even if you manage to delegate some of
these tasks to other people, there is still a lot of work left for you (including
the preparation of a judging system).
Fortunately I had several kind souls to help me prepare the problem set
and the judging system, without whose help the SWERC'96 would not have been
the success it turned out to be. I would like to thank Matthias Ruhl, Robin
O'Leary, Manuel Bleichenbacher, Rolf Strebel, Erwin Achermann, Berni Seybold,
Emil Zeller, Jacques Supcik, Miguel Revilla, and Hans Domjan for their efforts.
The rest of this document contains statistics about problem submission during
the contest and descriptions of each problem and how to solve them.
Please direct any comments or questions directly to oswald@inf.ethz.ch.
Erich Oswald, Chief Judge
As indicated in the statistics, the problem set consisted of the following eight problems.
I didn't expect a team to solve all of them but hoped that most teams would solve at least two problems and the best team to solve five or six problems. Well, this didn't happen and the best team only solved four problems, followed by a team that solved three and several teams that solved two problems. The rest of the teams solved one problem, except for one team that never even submitted a single run.
A reason why less problems were solved than expected may have been the difficulty level of the problem set. I've been told the problem set was too difficult, which may be true, but I don't think it was unsolvable. Although we included several difficult problems, there were also a very easy and a rather easy one, so at least half of the teams should have been able to solve at least two or three problems. My guess is that many teams didn't read the problem set carefully enough and went straight to difficult problems instead of first solving the easier ones. This shows that it's important to have a rough estimate of the individual problem difficulties early in the contest.
A look at the statistics shows that only 18% of all submissions were accepted, which at first seems to be a poor rate but at second glance is almost the same as last year's acceptance rate. The number of submissions is only slightly lower than last year (where the problem set consisted of nine problems). The only real difference is that the variance in the number of problems solved is smaller than last year because practically all teams solved at least one problem.
Let's now look at the individual problems:
(Description; Author: Matthias Ruhl; reviewed by Emil Zeller and Erich Oswald)
A problem we thought was of average difficulty. It came as a surprise that only three teams tried to solve it and none succeeded. But then again, it involves some mathematics and geometry, which may have made it difficult for many teams. All submissions resulted in wrong answers; usually the number of occurrences was wrong.
Since the problem text mentions that constellations may be arbitrarily scaled and rotated, a first step is to reduce this infinite number of orientations to a manageable set. A simple way is suggested by the sample solution: take two points in the constellation and map them to every pair of stars in the map. The actual occurrences will be a (possibly empty) subset of these orientations. Of course this only works for constellations with more than two stars, but constellations with only one star are special cases which are very easy to handle.
The next step is to transform all other points in the constellation the same way as the two points that were initially mapped to existing stars. This requires some knowledge about affine transformations. You can model the transformation as a composition of a scale, a rotation, and a translation or you can calculate the transformation matrix by solving a set of two linear equations. This is probably the hairiest part of the problem.
Most orientations can be rejected early because some of their points are not mapped to integer coordinates (within a small tolerance), otherwise you have to check whether there is a star in the map at that position. If all points in the constellation are mapped to existing stars you have found an occurrence. Calculating its average brightness and managing a brightest solution should then be easy.
There's one last pitfall: if the constellation occurs within itself (imagine a square), the number of occurrences will be wrong because the same occurrence will be counted more than once. The sample solution therefore first counts the number of occurrences if the constellation is used as a star map itself and divides the number of occurrences by that number before printing it.
(Description; Author: Manuel Bleichenbacher; reviewed by Matthias Ruhl, Robin O' Leary, Berni Seybold and Erich Oswald)
Solving Hexagon involves a lot of programming but is not really difficult. Only one team submitted a run, which was immediately accepted.
The basic strategy is to generate all possible constellations, calculate their score and compare it to the best score so far. The first difficulties are the complex formula for computing the score and the not-so-regular game board which require some non-trivial data structures.
In order to beat the time limit and keep the search space limited, the sample solution calculates the maximal score that can still be achieved from a partially covered game board before it puts the next piece on the board. With the clarification that was given in the last minute announcements (only consider rows with a non-zero score), many partially covered boards can be eliminated early because at least one of their row scores becomes zero.
The sample solution also contains a function that calculates the maximal score using a closed formula. If you'd had that formula you could have had Hexagon accepted after fifteen minutes..
(Description; Author: Matthias Ruhl; reviewed by Erwin Achermann and Erich Oswald)
An easy problem that several teams were able to solve. Surprisingly many submitted runs failed because they didn't correctly handle the case where the whole domino system consists of only one stone which of course falls after 0 seconds. Another surprise was that more than one third of all teams didn't even try to submit a run.
The sample solution maps the problem to a graph whose nodes are the key dominos and whose edges are the rows between them. For each key domino it computes the time when the domino will fall, which is achieved by propagating falling times across the graph until no more changes occur. Then the maximal time among key dominoes is calculated. What is then left is to go through all rows and check whether one of their inner dominoes falls later than the key dominoes at their end points and might become the new last domino.
(Description; Author: Matthias Ruhl; reviewed by Rolf Strebel and Erich Oswald)
Another geometry problem that no team solved although there were numerous submissions. Matthias regards this as the most difficult problem in the whole set, nevertheless many teams preferred Pendulum to the probably easier Stars. Personally I think there were more difficult problems than Pendulum. A significant amount of runs resulted in run-time errors, presumably because of floating-point errors.
What you have to do is to simulate the movement of the pendulum, keeping track of which hook the pendulum is currently circling around (the center) and how long the remaining string is. Find the next hook where the string will bend by finding the hook whose angular distance from the current position of the pendulum is minimal and whose distance from the center is shorter than the remaining length of the string. Do this until you find no appropriate hook or until the pendulum would have to rise over the x-axis to bend around the next hook and return the perimeter of the resulting circular orbit or twice the sum of the circular arc lengths that were traversed to reach the x-axis.
Although easy in principle, many details have to be taken care when coding a solution, e.g. to choose the right hook if several hooks have the same angular distance from the current position of the pendulum.
(Description; Author: Manuel Bleichenbacher; reviewed by Berni Seybold and Erich Oswald)
Definitely the easiest problem in the whole set, as you can see from the number of submissions and the high acceptance rate. Only one team never even tried to submit a solution and only one of the remaining teams failed to submit an accepted run. Runs resulting in wrong answers typically had trouble with the test case whose input was a spiral or didn't take into account that the path runs between pixels and not from pixel center to pixel center.
If you look at the sample solution, you will find that is more complicated than necessary because in the original problem description there was no reference to the fact that the outside is always to the right of the path (we included that later to make the problem even simpler). The sample solution therefore stores all vertical segments in a matrix and then scans the matrix row by row, setting the pixel to the left of the first, third, ... segment and the pixel to the right of the second, fourth, ... segment. Horizontal segments are treated in a similar manner.
Of course an even simpler solution is to traverse the path and always set the pixel to the right of the current segment. No wonder the first run was accepted after less than 20 minutes...
(Description; Author: Matthias Ruhl; reviewed by Erich Oswald)
Only six teams submitted runs to Villa, of which two were successful. The acceptance rate is thus comparable to that of Domino, which indicates that the problem was only of average difficulty. A significant amount of runs was rejected because the time limit was exceeded, probably due to inefficient algorithms. Other teams seemed to have problems with the fact that doors can be used from both sides, which makes one wonder about the kind of building they live in.
The sample solution is based on a breadth-first search. It starts in the entrance hall, considers all legal actions that can be done there (switching on/off lights in the house or moving through a door to another lighted room) and appends the resulting situations to a large FIFO queue before taking the next situation from the queue and doing the same with that situation. This process stops as soon as the final situation is reached or when there are no more situations in the queue.
Situations are encoded into integers, where one bit per room is reserved to model the state of the light in each room (on/off) and some more bits are used to store the number of the room Mr. Black is in. This is necessary because it is well possible that Mr. Black has to return to a room after switching on/off lights in other rooms. The code is then used as an index into an array that contains the number of steps to reach the corresponding situation, which allows you to detect whether you have been in the same situation before and don't have to append the current situation to the queue again.
Another array stores for each situation the number of the room that Mr. Black came from or the number of the light that was switched on or off. This allows reconstructing Mr. Black's actions to reach his bedroom and is needed for printing the solution.
(Description; Author: Rolf Strebel; reviewed by Robin O' Leary and Erich Oswald)
In my opinion the most difficult problem in our set. Only one team submitted runs but without success.
To solve the problem the sample solution first generates all possible ship arrangements and keeps those that don't contradict the given input data. It then tries to eliminate them one by one, according to the following idea: if there is a square on the board where all arrangements have a ship square except for one who doesn't, then that square could be uncovered. If you hit an `o', you'd have one miss but would know where the remaining ships are. If you hit an `x', you wouldn't know the exact arrangement but could rule out the arrangement that had no ship there and could continue uncovering. If all but one solution can thus be ruled out, the answer is yes, otherwise no.
Another idea allows to stop generating further ship distributions as soon as 30 feasible distributions have been found: all ships together cover 7*4=28 squares on the board. The elimination procedure described above cannot work with more than 29 squares because every solution would have to leave at least two of these squares unoccupied by ships. With 30 solutions distributed over 30 squares and each solution occupying 28 of these squares there must be at least one square that more than one solution leave unoccupied, making it impossible to tell them apart. (I'm not very happy with this explanation; if you find a better one, please send it to me.)
(Description; Author: Matthias Ruhl; reviewed by Erich Oswald)
This problem was often submitted but never accepted, so it was probably more difficult than most teams thought, the main reason being the time limit that ruled out all brute-force algorithms. I wrote a simple solution that just checked all possible selections but had to terminate it prematurely because it wouldn't finish the last few test cases within 20 minutes.
Matthias uses dynamic programming in his sample solution to reduce the exponential time of the brute-force solution to polynomial time. For every possible difference between prosecution and defence value, the maximal sum of the two values is stored in a table, first for only one juror, then successively for 2, 3,.., m jurors. In another array the last juror taken for each optimal difference is stored to later reconstruct the solution. If you're familiar with dynamic programming, the solution is pretty straightforward (except that you have make sure that every jury member is included at most once), if not, you'd better grab the nearest book on algorithms to enlighten you.
The following table shows how often each problem was submitted, how often it was accepted, and what the main reasons were why runs were rejected.
Problem |
Submit | Accept | CTE | CRV | PE | RTE | TLE | WA | Teams |
|---|---|---|---|---|---|---|---|---|---|
| Stars | 6 | - | - | - | - | - | - | 6 (100%) | 3 |
| Hexagon | 1 | 1 (100%) | - | - | - | - | - | - | 1 |
| Domino | 66 | 8 (12%) | - | - | - | 1 (1%) | 6 (9%) | 51 (77%) | 18 |
| Pendulum | 22 | - | - | - | - | 6 (27%) | - | 16 (73%) | 7 |
| Border | 59 | 28 (47%) | - | - | 3 (5%) | 4 (7%) | - | 24 (41%) | 29 |
| Villa | 19 | 2 (11%) | - | - | - | 1 (5%) | 8 (42%) | 8 (42%) | 6 |
| Ships | 5 | - | - | - | - | 2 (40%) | - | 3 (50%) | 1 |
| Jury | 36 | - | 1 (3%) | - | - | 9 (25%) | 15 (42%) | 11 (31%) | 11 |
| Total | 214 | 39 (18%) | 1 (0%) | - | 3 (1%) | 23 (11%) | 29 (14%) | 119 (56%) | 29* |
| Average | 26.8 | 4.9 | 0.1 | - | 0.8 | 2.9 | 3.6 | 14.9 | 9.5 |
* total number of distinct teams
| Submit | Number of times the problem was submitted |
| Accept | Number (percentage) of accepted submissions |
| CTE | Number (percentage) of submissions rejected due to a Compile-time Error |
| CRV | Number (percentage) of submissions rejected due to a Contest Rule Violation |
| PE | Number (percentage) of submissions rejected due to a Presentation Error |
| RTE | Number (percentage) of submissions rejected due to a Run-time Error |
| TLE | Number (percentage) of submissions rejected due to a Time Limit Exceeded error |
| WA | Number (percentage) of submissions rejected due to a Wrong Answer error |
| Teams | Number of teams that submitted the problem at least once |