tag:blogger.com,1999:blog-786333285568106173.post485402006672803615..comments2024-01-25T01:05:59.968-05:00Comments on WebDiarios de Motocicleta: IOI: The Hard ProblemMihaihttp://www.blogger.com/profile/11599372864611039927noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-786333285568106173.post-21926873854212782122010-08-26T04:52:01.771-04:002010-08-26T04:52:01.771-04:00the following note may be related (they encode all...the following note may be related (they encode all the distances though)<br /><br />On compact representations of All-Pairs-Shortest-Path-Distance matrices<br /> Paolo Ferragina, Igor Nitto, and Rossano Venturini<br />Theoretical Computer Science<br />Volume 411, Issues 34-36, 17 July 2010, Pages 3293-3300Christianhttp://dx.doi.org/10.1016/j.tcs.2010.05.021noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-34137557108608194002010-08-23T13:51:36.790-04:002010-08-23T13:51:36.790-04:00Indeed, the lower bound is ridiculously simple :) ...Indeed, the lower bound is ridiculously simple :) Very nice!Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-38467384978589769292010-08-23T13:26:34.393-04:002010-08-23T13:26:34.393-04:00I think I can show that the answer is log(3) n^1.5...I think I can show that the answer is log(3) n^1.5 + O(n log n), within tight upper and lower bounds. For the upper bound, pick a spanning tree (or forest) of the graph on n points. Then, for each node, and each edge of the tree, we encode the +1, 0, or -1 indicating how the distance to that node changes as we traverse the edge (away from the root).<br /><br />For the lower bound, I can encode log(3) k m bits in a graph with 2k + m vertices, and recover them from the distances from k vertices to all the others. Let a_1, ... , a_k be the nodes, b_1, ... , b_k be connected to the nodes with edges (a_i, b_i) for all i.<br />The m vertices x_1, ..., x_m can each be placed at distance 1, 2, or >2 from each a_i independently by placing an edge from x_j to a_i, from x_j to b_i, or neither edge. This encodes mk independent choices from three possibilities. If we let k = n^{1/2} and m = n - 2 n^[1/2}, then I think we get log 3 n^1.5 - O(n) bits encoded in the distances from a_i to x_j.Bill Hessehttps://www.blogger.com/profile/13162885630027119791noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-90151230357140104602010-08-22T11:07:54.958-04:002010-08-22T11:07:54.958-04:00So, this solution gives you log(3)*n^{1.5} bits of...So, this solution gives you log(3)*n^{1.5} bits of space, plus smaller order terms.<br /><br />The open research question is whether one can do c*n^{1.5} bits, for any constant c<log(3).<br /><br />Any ideas?Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-48989960351687803032010-08-20T23:32:12.163-04:002010-08-20T23:32:12.163-04:00I wonder if anyone managed to solve the non-asympt...<i>I wonder if anyone managed to solve the non-asymptotic version by constructing the trivial encoding then compressing it by Huffman etc.</i><br /><br />No. (People looked at the winning solutions so I can say this with certainty.)<br /><br />The committee has, over the years, become quite adept at making test cases, and theory makes a very good predictor for reality.<br /><br /><br />ilyaraz: Yes, that works. But it seems to be a non-obvious idea :) 7 people solved it by the official count.Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-67093033784959781222010-08-20T23:11:42.399-04:002010-08-20T23:11:42.399-04:00Probably, I'm missing something, but...
Let&#...Probably, I'm missing something, but...<br /><br />Let's consider some spanning tree T. For root, let's encode all sqrt(N) distances explicitly. Then for each node, let's encode its parent in T, and differences between its and parent's distances. All differences are 0, +-1, so we do it by spending O(sqrt(N)) bits.ilyarazhttps://www.blogger.com/profile/05104799447222642052noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-27575935287817119882010-08-20T11:39:25.394-04:002010-08-20T11:39:25.394-04:00This site (blogger/blogspot) is run by Google.This site (blogger/blogspot) is run by Google.rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-77659100161931829452010-08-20T10:18:32.035-04:002010-08-20T10:18:32.035-04:00None of the competitors who tried data compression...None of the competitors who tried data compression (alone) achieved more than 50 points. The data were designed to be difficult to crack with statistical compression methods.<br /><br />Gordon Cormack<br />IOI 2010 Scientific Director<br /><br />[P.S. to whomever runs this site. I don't think you should ask people to enter their google password.]Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-786333285568106173.post-5033769585093415632010-08-20T09:44:36.887-04:002010-08-20T09:44:36.887-04:00I wonder if anyone managed to solve the non-asympt...I wonder if anyone managed to solve the non-asymptotic version by constructing the trivial encoding then compressing it by Huffman etc.Anonymousnoreply@blogger.com