Chopsticks
Time limit2sMemory limit128 MB
Given N chopstick lengths, pick 3K of them and group into K triples to minimize the sum of squared differences between the two smallest lengths in each triple.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Sorting, Greedy
- Solved
- No attempts yet
Problem
People normally use two chopsticks for a meal. In this setting, each person instead receives three chopsticks: the usual pair plus one larger chopstick used for a separate purpose.
For one person, let the three assigned lengths be A, B, and C with A <= B <= C. The large chopstick C does not affect the discomfort. The penalty for that person is (A-B)×(A-B), based only on the two shorter chopsticks.
There will be K(1 <= K <= 1000) people at the meal. From N(3×K <= N <= 5000) available chopsticks, choose exactly 3×K chopsticks and give three to each person. Compute the minimum possible total penalty.
Input
The first line contains two integers K and N. The following input contains the lengths of the N chopsticks. The lengths may be separated by spaces or newlines, and each length is an integer from 1 to 32767.
Output
Print the minimum possible total penalty.