TopCoder Asia-Pacific 2012 解题思路

上月偶然看到网上有提到TopCoder Asia-Pacific 2012 (TopCoder亚太2012),比赛形式为马拉松,题目和传感器定位问题有些类似。因为我今年比较忙,没报名KDD CUP,也没报名TCO,GCJ,这次感觉应该有时间把这个题目做完,就尝试了一下。
题目在此 http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15137&pm=11942
题目大致是说有$n (100 \le n \le 2000)$ 个10维空间上的点,每一维坐标从[0, 1000]的整数中随机选取。对于每一个点,你知道到它最近和最远的点的距离,也知道其他点到这个点距离的远近排序。每个点的每个维度都有一定概率已知,需要算出不知道的维度。

Continue reading »