Task Information for Saveit

Task Author: Mihai Patrascu (ROM)

This task also is innovative for the IOI. In general, for most IOI tasks efficiency matters. However, in this case it is not execution time or memory usage but rather communication efficiency: how to represent some complex data in as few bits as possible, without losing information.

This difference in focus makes the tasks possibly somewhat harder to understand. Furthermore, it is technically more complicated, because the contestant has to program two independent procedures that are inverses to each other. The communication format is not prescribed; all that matters is that the decoder programmed by the contestant can decode the data from the encoder that is also programmed by the contestant. The grading server then connects these two procedures to verify that the decoder can indeed "understand" what the encouder produced.

Two things are important. First, find a way to encode adjacency information about Xedef's package transportation network. Second, to transmit that information with communication efficiency.

Briefly stated, the subtasks could be tackled as follows: