Minimizing Rating Differences in a Chess Tournament

In an international chess tournament, there are N players, each with a unique positive integer rating. The tournament involves K matches. Each player can participate in at most two matches (possibly zero) and cannot play twice with the same color: a player may play at most once with the white pieces and at most once with the black pieces.

In every match the higher‐rated player must play black and the lower–rated player white. Note that a player who participates in two matches will play once with white and once with black. The organizers want to choose which pairs compete in order to minimize the total sum of rating differences over all K matches. For a match between a white player with rating \(a\) and a black player with rating \(b\) (with \(a < b\)), the cost is \(b - a\). Find the arrangement of matches that minimizes the total cost.

Note: In some matches the same player may appear twice (once as black and once as white) as long as the rules are satisfied.

Hint: After sorting the ratings, an optimal schedule can be obtained by selecting pairs from players that are as close in rating as possible. In addition, by allowing one player to participate in two games (chaining pairs) it is sometimes possible to reduce the number of distinct players used and further lower the cost.

The answer may be expressed in terms of a dynamic programming solution. One way to model the problem is to use a 3-dimensional DP state dp[i][j][c] representing the minimum cost considering the first i sorted players, with j matches already scheduled, and where c is the index of a player that is "active" – i.e. a player who has been chosen as the white candidate in a match but has not yet been paired (if no such candidate exists, we denote this state with c = N). The transitions are as follows:

• If no candidate is active (c = N):
  • Skip the current player.
  • Make the current player active (they will serve as white in a future match).
  • If possible, take the next player to form a disjoint pair with the current one. You have two options: finish the pair without chaining (leaving no active candidate) or finish the pair and let the second player serve as a candidate for chaining.
• If a candidate is active (c < N):
  • Skip the current player.
  • Pair the active candidate with the current player (completing a match) and finish the pair (active candidate becomes none).
  • Or pair them but then let the current player become the new active candidate (chaining the matches). In both cases, the cost incurred is \(r[i] - r[c]\) when the rating of the active candidate is \(r[c]\) and the current player’s rating is \(r[i]\).

The final answer is obtained as the minimum cost over all ways to form exactly K matches with no active candidate remaining.

For example, if N = 7 and the ratings are 30, 17, 26, 41, 19, 38, 18 (which when sorted become \(17, 18, 19, 26, 30, 38, 41\)) and K = 3, one optimal arrangement is:

• Match 1 (disjoint): Player with rating 17 (white) vs. player with rating 18 (black) with cost \(18-17=1\).
• Match 2 (chain): Reuse the player with rating 18 as white and pair with player with rating 19 (black) with cost \(19-18=1\).
• Match 3 (disjoint): Player with rating 38 (white) vs. player with rating 41 (black) with cost \(41-38=3\).

Total cost = \(1 + 1 + 3 = 5\), which is minimal.

inputFormat

The first line contains two integers N and K (2 ≤ N ≤ 200 and it is guaranteed that an arrangement exists to hold K matches under the rules). The second line contains N positive integers representing the unique ratings of the players.

Note: The ratings are not necessarily sorted.

outputFormat

Output a single integer: the minimum possible total cost (the sum of rating differences) to arrange exactly K matches under the tournament rules.

sample

7 3
30 17 26 41 19 38 18

5

</p>