IOI Photos have been posted
Posted first Newsletter
IOI Program
Schedule updated including information about new Evening Lectures.
Rules, competition environment and sample tasks added to site.
Registration activated and many ioi2010.org web updates.
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:
- Subtask 1:
You can send the entire adjacency matrix "as is";
this information is naturally expressed in terms of bits,
other encodings are imaginable as well.
All that the encoder and decoder need to agree upon is
the order of the bits.
Since there are 1000 cities,
this requires no more than 1000*1000=1 000 000 bits.
Other approaches using more bits also work in this subtask.
- Subtask 2:
You can send the entire table with all hop counts directly.
Since there are no more than 1000 cities,
the maximum hop count is less than 1000,
and thus can be encoded in 10 bits.
The size of the table is at most 1000*36=36 .
Hence, not more than 360 000 bits are needed.
- Subtask 3:
One needs a new idea to improve the communication efficiency further.
The crux is to come up with the idea of considering a spanning tree;
any spanning tree will do.
The distance from v1 to v2 is one of
- distance from parent(v1) to v2
- 1 + distance of parent(v1) to v2
- -1 + distance of parent(v1) to v2
- Subtask 4: Using two bits to record a one-of-three choice is excessive. It is possible to map 3 ternary decisions (27 choices) to 5 bits (32 possibilities). This improves the communication further.