Some information about task POST
The exact solution can be obtained by dynamic programming
based on a 2-dimensional table. The entire table must be
stored (O(P*V) space), and each entry can be computed in
O(V) time worst case. This yields an algorithm of O(P*V^2)
time complexity.
Many approximate solutions based on various heuristics exist
(spread post offices evenly or based on gap size between villages,
local search, simulated annealing, genetic programming, ...).
Because of the rules for partial credit these programs can
also score some points in some cases.
The 10 test cases POST#.IN have the following characteristics:
# V P X1 XV Gn Gx Answer Kind of data
-- --- -- -- ---- -- ---- ------- ------------
1 5 1 1 5 1 1 6 Manual, one post office
2 10 2 1 10 1 1 12 Manual, small
3 10 5 1 50 1 22 9 The example
4 284 30 56 9985 1 209 18394 Random, large
5 290 55 7 9897 1 162 24780 Random, large
6 300 30 44 9249 1 202 18153 Random, largest
7 300 1 1 9996 1 3700 1428420 Random, longint answer
8 100 9 92 996 1 37 2134 Random, medium size
9 259 15 2 9899 1 1701 3595 Random, villages in 10 clusters
10 19 3 1 6765 1 2584 5026 Villages at Fibonacci coordinates
where
V = number of villages (input)
P = number of post offices (input)
X1 = smallest village X coordinate
XV = greatest village X coordinate
Gn = minimum gap between neighboring villages
Gx = maximum gap between neighboring villages
Answer = sum of distances for optimal post office locations