The International Olympiad in Informatics (IOI 2010) is taking part this week at the University of Waterloo, Canada.
The olympiad often features a hard problem, which is intended to be solved by a handful of contestants. This year, the problem was solved by about 6 people. Read the problem below and give it a shot! :)
I will describe the problem in both TCS and IOI fashion.
Asymptotic version. You are given an unweighted, undirected graph on N vertices. Some sqrt(N) vertices are designated as "hubs". You have to encode the pairwise distances between all hubs and all vertices in O(N1.5) bits of space.
The encoder and decoder may run in polynomial time. Of course, the decoder does not see the original graph; it receives the output of the encoder and must output the explicit distances between any hub and any other vertex. (This list of explicit distances takes O(N1.5lg N) bits.)
Non-asymptotic version. You are given a graph on 1000 nodes and 36 designated hubs. You have to encode the distances between all hubs and all vertices in 70,000 bits of space.
The non-asymptotic version is a bit harder, since you have to pay more attention to some details.
The research version. Prove or disprove that the distances can be encoded using (1+o(1)) N1.5 bits of space. I don't know the answer to this question (but I find the question intriguing.)