IOI 2015 - Boxes

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

long long delivery(int N, int K, int L, int p[]) {
    // p[] is sorted in non-decreasing order
    // leftCost[i] = min cost to deliver boxes 0..i-1 going clockwise
    // rightCost[i] = min cost to deliver boxes n-i..n-1 going counterclockwise

    vector<ll> leftCost(N + 1, 0), rightCost(N + 1, 0);

    for (int i = 1; i <= N; i++) {
        // Deliver box i-1 (0-indexed) going clockwise
        int groupStart = max(0, i - K);
        leftCost[i] = leftCost[groupStart] + 2LL * p[i - 1];
    }

    for (int i = 1; i <= N; i++) {
        int groupStart = max(0, i - K);
        rightCost[i] = rightCost[groupStart] + 2LL * (L - p[N - i]);
    }

    ll ans = LLONG_MAX;
    for (int i = 0; i <= N; i++) {
        // i boxes delivered from left, N-i from right
        ll cost = leftCost[i] + rightCost[N - i];
        ans = min(ans, cost);
    }

    // Also consider combining: some groups go all the way around
    // For each split, the overlapping group costs L instead of 2*left + 2*right
    // This is already handled if we consider mixed groups.
    // Actually, we need to also try: for each (i, j) where i from left, j from right,
    // and some group goes around. The around trip costs L and delivers K boxes.
    // Simpler: for each i from 0..N, and then take min(leftCost[i] + rightCost[N-i])
    // But we also need: leftCost[i] + rightCost[j] + (number of round trips) * L
    // where i + j + roundTrips * K >= N.
    // The above DP already handles non-overlapping. For round trips:
    // We can also compute: for each i, rightCost[j]:
    //   If we combine the last group from left and first group from right into a round trip
    //   cost = leftCost[i-k1] + rightCost[j-k2] + L, where k1+k2 <= K

    // Alternative simpler formulation:
    // The standard approach handles the "go around" case by noting:
    // min over i of leftCost[i] + rightCost[N-i] already works if we also
    // allow the "around" option per group.

    // Let's also try the round-trip version:
    // For each split point i, the last left group and first right group can
    // be merged into a single round trip of cost L (saving 2*p[i-1] + 2*(L-p[i]) - L)
    // if beneficial.
    for (int i = 0; i <= N; i++) {
        // Take i from left, N-i from right, but the boundary groups share a round trip
        int li = i, ri = N - i;
        // Groups from left: ceil(li / K) groups, from right: ceil(ri / K) groups
        // If both > 0, we can merge the last left group and first right group into one
        // round trip if it saves cost.
        // The saved cost per such merge: the last left group costs 2*p[i-1],
        // the first right group costs 2*(L - p[i]), replace both with L.
        if (li > 0 && ri > 0) {
            // Last left group starts at max(0, li-K)
            // First right group starts at max(0, ri-K)
            ll leftPart = leftCost[max(0, li - K)];
            ll rightPart = rightCost[max(0, ri - K)];
            ll cost = leftPart + rightPart + L;
            ans = min(ans, cost);
        }
    }

    return ans;
}

int main() {
    int n, k, l;
    scanf("%d %d %d", &n, &k, &l);
    int p[n];
    for (int i = 0; i < n; i++) scanf("%d", &p[i]);
    sort(p, p + n);
    printf("%lld\n", delivery(n, k, l, p));
    return 0;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{hyperref}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{gray},
  stringstyle=\color{red},
  numbers=left,
  numberstyle=\tiny\color{gray},
  breaklines=true,
  frame=single,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2015 -- Boxes}
\author{}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}

You are at position~0 on a circular track of length $L$ with $n$ boxes at sorted positions $p_0 \le p_1 \le \cdots \le p_{n-1}$. You can carry at most $K$ boxes at a time and must return to position~0 after each trip. Minimise the total distance travelled to deliver all boxes.

\section{Solution}

\subsection{Key Observations}

For each trip, the deliverer goes clockwise (cost $= 2 \cdot p_{\max}$ for the farthest box in the group) or counter-clockwise (cost $= 2(L - p_{\min})$), or goes all the way around (cost $= L$).

Group the boxes into consecutive batches of at most $K$, delivered from the left (clockwise) or from the right (counter-clockwise).

\subsection{DP Formulation}

Define prefix and suffix cost arrays:
\begin{align*}
  \textit{leftCost}[i] &= \textit{leftCost}[\max(0, i-K)] + 2 \cdot p_{i-1}, \\
  \textit{rightCost}[j] &= \textit{rightCost}[\max(0, j-K)] + 2 \cdot (L - p_{n-j}).
\end{align*}

The answer is:
\[
  \min_{0 \le i \le n} \min\!\big(\textit{leftCost}[i] + \textit{rightCost}[n-i],\;
  \textit{leftCost}[\max(0,i-K)] + \textit{rightCost}[\max(0,n-i-K)] + L\big).
\]

The second term handles the case where the last left-group and first right-group are merged into a single round trip of cost $L$.

\section{C++ Implementation}

\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

long long delivery(int N, int K, int L, int p[]) {
    vector<ll> leftCost(N + 1, 0), rightCost(N + 1, 0);

    for (int i = 1; i <= N; i++) {
        int groupStart = max(0, i - K);
        leftCost[i] = leftCost[groupStart] + 2LL * p[i - 1];
    }
    for (int i = 1; i <= N; i++) {
        int groupStart = max(0, i - K);
        rightCost[i] = rightCost[groupStart] + 2LL * (L - p[N - i]);
    }

    ll ans = LLONG_MAX;
    for (int i = 0; i <= N; i++) {
        int ri = N - i;
        // Option 1: separate left and right trips
        ans = min(ans, leftCost[i] + rightCost[ri]);
        // Option 2: merge boundary groups into a round trip
        if (i > 0 && ri > 0) {
            ll lp = leftCost[max(0, i - K)];
            ll rp = rightCost[max(0, ri - K)];
            ans = min(ans, lp + rp + (ll)L);
        }
    }
    return ans;
}
\end{lstlisting}

\section{Complexity Analysis}

\begin{itemize}
  \item \textbf{Time}: $O(n)$ (input is pre-sorted).
  \item \textbf{Space}: $O(n)$.
\end{itemize}

\end{document}