Editorial for IOI '17 P2 - Wiring
Submitting an official solution before solving the problem yourself is a bannable offence.
Subtask 1
There are many different Dynamic Programming (DP) solutions with
Subtask 2
This subtask is to find the pattern of wiring. A simple solution to this subtask is to calculate:
Subtask 3
Consider the consecutive clusters of points with the same color. The idea is that each wire will have endpoints in two consecutive clusters, so the
Subtask 4
This subtask could be solved by a greedy algorithm that divides each cluster into two halves and connects the left half to the left cluster and the right half to the right cluster. The middle point of a cluster with an odd number of points should be considered separately.
Optimal solution
There is an
Comments
https://cgm.cs.mcgill.ca/~godfried/publications/akiyama-chvatal-festschrift.pdf