Official Analysis

Video Solution

By David Li

Video Solution Code

Explanation

For the tandem kayaks, we want to minimize the difference between the people in each kayak. To do this, we can sort the weights of the people and place adjacent people into the same kayak.

For the two single kayaks, we can remove every possible pair of individuals and compute the differences in the tandem kayaks.

Implementation

Time Complexity: O(N3)\mathcal{O}(N^3)

C++

#include <bits/stdc++.h>
using namespace std;


int main() {
	int N;
	cin >> N;
	N *= 2;


	vector<int> people(N);
	for (int &p : people) { cin >> p; }

Java

import java.io.*;
import java.util.*;


public class Kayaking {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int N = io.nextInt() * 2;


		int[] people = new int[N];
		for (int x = 0; x < people.length; x++) { people[x] = io.nextInt(); }

Python

n = int(input()) * 2
people = sorted(int(i) for i in input().split())
assert len(people) == n


min_instability = float("inf")
for i in range(n):
	for j in range(i + 1, n):
		new_people = [people[p] for p in range(n) if p != i and p != j]
		total_instability = 0
		for p in range(0, n - 2, 2):
			total_instability += new_people[p + 1] - new_people[p]
		min_instability = min(min_instability, total_instability)


print(min_instability)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum