CF - Kayaking

Authors: Danh Ta Chi Thanh, Brad Ma, David Li

Official Analysis

Video Solution

By David Li

Video Solution Code

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!