High Spies

(or How to Win a Programming Contest)

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.


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