HMMT 二月 2007 · 冲刺赛 · 第 35 题

HMMT February 2007 — Guts Round — Problem 35

[ ≤ 25 ] The Algorithm. There are thirteen broken computers situated at the following set S of thirteen points in the plane: A = (1 , 10) B = (976 , 9) C = (666 , 87) D = (377 , 422) E = (535 , 488) F = (775 , 488) G = (941 , 500) H = (225 , 583) I = (388 , 696) J = (3 , 713) K = (504 , 872) L = (560 , 934) M = (22 , 997) At time t = 0, a repairman begins moving from one computer to the next, traveling continuously in straight lines at unit speed. Assuming the repairman begins and A and fixes computers instantly, what path does he take to minimize the total downtime of the computers? List the points he visits in order. N Your score will be b c , where 40 N = 1000 + b the optimal downtime c − b your downtime c , or 0, whichever is greater. By total downtime we mean the sum ∑ t , P P ∈ S where t is the time at which the repairman reaches P . P

解析

[ ≤ 25 ] The Algorithm. There are thirteen broken computers situated at the following set S of thirteen points in the plane: A = (1 , 10) B = (976 , 9) C = (666 , 87) D = (377 , 422) E = (535 , 488) F = (775 , 488) G = (941 , 500) H = (225 , 583) I = (388 , 696) J = (3 , 713) K = (504 , 872) L = (560 , 934) M = (22 , 997) At time t = 0, a repairman begins moving from one computer to the next, traveling continuously in straight lines at unit speed. Assuming the repairman begins and A and fixes computers instantly, what path does he take to minimize the total downtime of the computers? List the points he visits in order. N Your score will be b c , where 40 N = 1000 + b the optimal downtime c − b your downtime c , or 0, whichever is greater. By total downtime we mean the sum ∑ t , P P ∈ S 12 where t is the time at which the repairman reaches P . P Answer: ADHIKLEFGBCJM . This is an instance of the minimum-latency problem, which is at least NP-hard. There is an easy O ( n !) algorithm, but this is unavailable to teams on computational grounds (100MHz calculators used to seem fast...) The best strategy may be drawing an accurate picture and exercising geometric intuition. The distribution of the points somewhat resembles a short, four-pronged fork with its outermost prongs bent apart; it is plausible to assume that the optimal order respects this shape. The optimal downtime is 24113.147907, realized by ADHIKLEFGBCJM, though a number of others also receive positive marks.