AOI Study Hub

Appearance

Train ​

Problem Statement ​

Full Solution ​

Let be the weights of the cargo, sorted from largest to smallest. Extend this sequence by adding zeros until we have terms, i.e.,

Then the minimum imbalance, , is

which corresponds to the imbalance resulting from putting in the th cargo, for . (If , the spot is left empty.)

We now show that this partition gives the minimum. Suppose two cargos contain in some partition, with

Let

Then the total imbalance is

Notice that this function, as a function of , is increasing for . Therefore, the smaller is, the smaller the imbalance. It is clear that the partition

minimizes .

Proof of minimization ​

There are three possible partitions of four elements:

,
,
.

These give

Hence, is minimized by the last partition, seeing as .

Taking any two wagons, we can improve the total imbalance by adjusting the partition of the four elements in according to the lemma. Consider the wagon containing and the wagon containing . If they are distinct, applying the partition lemma shows it is optimal for the wagon with to contain . Otherwise, we skip this step.

Induction step ​

Assume the wagons containing already contain as their second cargo, respectively. If the wagon containing does not contain , we swap contents with the wagon that does. By the partition lemma, this is optimal. By induction, we reach the proposed initial partition, which is unique.

Algorithm ​

  1. Create a vector containing all cargo weights and add zeros until its length is .

  2. Sort the vector.

  3. Compute the average

  4. Initialize . For to , increase by

  5. Output as the minimum imbalance.

This algorithm runs in , which can be optimized to by sorting first and then adding zeros in reverse order.

Subtasks ​

  • Subtask 1: Using backtracking, iterate through all possible distributions and find the one with minimum imbalance.
    Complexity: .

Implementation ​

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int W, C;
    cin >> W >> C;
    vector<long long> M;
    M.reserve(2 * W);
    long long sum = 0;
    for (int i = 0; i < C; ++i) {
        long long x;
        cin >> x;
        M.push_back(x);
        sum += x;
    }
    // Pad with zeros to have exactly 2W elements
    while ((int)M.size() < 2 * W) {
        M.push_back(0);
    }
    sort(M.begin(), M.end());

    long long A = sum / W;
    long long imbalance = 0;
    for (int i = 0; i < W; ++i) {
        long long load = M[i] + M[2 * W - 1 - i];
        imbalance += llabs(load - A);
    }

    cout << imbalance << '\n';
    return 0;
}