On 21 October 2006, the
Benelux Algorithm Programming Contest 2006
(BAPC 2006) was held at Leiden University, the Netherlands.
Problem C of this contest was called High Spies, and dealt with
transports of goods over a tree-shape network.
As for all problems, the jury of the contest had to write solutions
for this problem to determine the desired output for all test cases.
The problem was far from trivial, but different jury members came up
with the same algorithm for solving it. Although, intuitively,
this algorithm seemed to be correct, we wanted to be sure.
Therefore, the jury members André Deutz, Rudy van Vliet
and Hendrik Jan Hoogeboom proved that a crucial assumption that was made
in the algorithm was valid.
After the contest, we wrote a paper about our research on this problem,
which we submitted to
FUN 2007, the Fourth International Conference on FUN WITH ALGORITHMS.
This conference was held in Castiglioncello, Tuscany, Italy, from
3-5 June 2007. The paper was accepted.
The final version of the paper has been included in the conference
proceedings, which has appeared as
volume 4475 of Lecture Notes in Computer Science (LNCS).
The paper is available here in PDF
and in postscript.
You can also find the paper at the LNCS-website,
when you follow
this link.
You may refer to the paper as
A. Deutz, R. van Vliet, H.J. Hoogeboom:
High spies (or how to win a programming contest),
Fun with algorithms --
4th International conference, Fun 2007 --
Castiglioncello, Italy, June 3-5, 2007 --
Proceedings,
Lecture Notes in Computer Science 4475
(P. Creszenzi, G. Prencipe, G. Pucci, eds.),
Springer-Verlag, Berlin (2007), 93-107.
Presentation
The paper has been presented at Fun 2007 by Rudy van Vliet
on Monday, June 4, 2007.
The presentation (including some additional, unused slides)
is available here.
It has been produced with Microsoft Powerpoint 2002 SP3.
There is also a PDF-version of the slides.
Technical report
Due to space limitations, we could not include all proofs of the
results in the paper, nor could we elaborate on ways to generate test cases
for the problem. We plan to do this in a forthcoming technical report.
Questions and comments can be sent to
Rudy van Vliet:
rvvliet@liacs.nl.
Last modified:
2 July 2007 - http://www.liacs.nl/home/rvvliet/highspies/index.html