Editorial for IOI '00 P5 - Post Office
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
The exact solution can be obtained by dynamic programming based on a 2-dimensional table. The entire table must be stored ( space), and each entry can be computed in
time worst case. This yields an algorithm of
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.
Comments