IOI 2020 - Tickets

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

// IOI 2020 - Tickets
// n colors, m tickets each (sorted), k rounds. Each round picks one ticket
// per color. Prize = sum of top n/2 values minus sum of bottom n/2 values.
// Maximize total prize across all rounds.
//
// Greedy: start with all tickets used negatively (smallest k tickets).
// Incrementally convert tickets to positive (largest) to maximize gain.
// Use priority queue on marginal gain of each conversion.

long long find_maximum(int k, vector<vector<int>> x) {
    int n = (int)x.size(), m = (int)x[0].size();
    int half = n / 2;

    // p[i] = number of "positive" (top-half) uses for color i
    vector<int> p(n, 0);

    // Initial total with all k tickets used negatively per color
    ll total_prize = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++)
            total_prize -= x[i][j];

    // Priority queue: (marginal gain, color_index)
    // Gain of incrementing p[i] from t to t+1:
    //   x[i][m-t-1] + x[i][k-1-t]
    priority_queue<pair<ll, int>> pq;
    for (int i = 0; i < n; i++) {
        ll gain = (ll)x[i][m - 1] + x[i][k - 1];
        pq.push({gain, i});
    }

    int total_positive = k * half;
    while (total_positive > 0) {
        auto [gain, i] = pq.top();
        pq.pop();
        total_prize += gain;
        p[i]++;
        total_positive--;

        if (p[i] < k) {
            int t = p[i];
            ll new_gain = (ll)x[i][m - t - 1] + x[i][k - 1 - t];
            pq.push({new_gain, i});
        }
    }

    // Assign tickets to rounds ensuring each round has exactly n/2 positive
    vector<vector<int>> s(n, vector<int>(m, -1));
    vector<vector<int>> pos_rounds(n), neg_rounds(n);

    // Greedy round assignment: process colors by decreasing p[i],
    // assign each to the rounds with fewest positive slots filled
    vector<pair<int, int>> color_order;
    for (int i = 0; i < n; i++)
        color_order.push_back({p[i], i});
    sort(color_order.rbegin(), color_order.rend());

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> round_pq;
    for (int r = 0; r < k; r++) round_pq.push({0, r});

    for (auto [pi, i] : color_order) {
        vector<pair<int, int>> tmp;
        for (int t = 0; t < pi; t++) {
            auto [cnt, r] = round_pq.top();
            round_pq.pop();
            pos_rounds[i].push_back(r);
            tmp.push_back({cnt + 1, r});
        }
        for (auto& pr : tmp) round_pq.push(pr);
    }

    // Negative rounds: all rounds not assigned as positive
    for (int i = 0; i < n; i++) {
        set<int> pos_set(pos_rounds[i].begin(), pos_rounds[i].end());
        for (int r = 0; r < k; r++)
            if (!pos_set.count(r))
                neg_rounds[i].push_back(r);
    }

    // Fill the allocation matrix
    for (int i = 0; i < n; i++) {
        sort(pos_rounds[i].begin(), pos_rounds[i].end());
        for (int t = 0; t < p[i]; t++) {
            int ticket = m - p[i] + t;   // largest tickets
            s[i][ticket] = pos_rounds[i][t];
        }
        sort(neg_rounds[i].begin(), neg_rounds[i].end());
        for (int t = 0; t < k - p[i]; t++) {
            int ticket = t;               // smallest tickets
            s[i][ticket] = neg_rounds[i][t];
        }
    }

    // Output allocation
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            printf("%d ", s[i][j]);
        printf("\n");
    }

    return total_prize;
}

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<vector<int>> x(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &x[i][j]);
    printf("%lld\n", find_maximum(k, x));
    return 0;
}

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{listings}
\usepackage{geometry}
\usepackage{hyperref}
\geometry{margin=2.5cm}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\bfseries,
  breaklines=true,
  numbers=left,
  numberstyle=\tiny,
  frame=single,
  tabsize=2
}

\title{IOI 2020 -- Tickets}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}
There are $n$ colors and $m$ tickets per color. Ticket $j$ of color $i$ has value $x[i][j]$ (sorted in non-decreasing order within each color). There are $k$ rounds. In each round, exactly one ticket from each color is used (each ticket is used in at most one round). The prize for a round is the sum of absolute differences from the median of the chosen tickets' values.

More precisely, if tickets with values $v_0, v_1, \ldots, v_{n-1}$ are chosen ($n$ is even), the game master picks a value $b$ that minimizes $\sum |v_i - b|$, which is achieved by the median. The prize equals $\sum |v_i - \text{median}|$, which equals the sum of the top $n/2$ values minus the sum of the bottom $n/2$ values.

Maximize the total prize across all $k$ rounds.

\section{Solution Approach}

\subsection{Key Observation}
Since $n$ is even, the prize for a round with sorted values $v_0 \le v_1 \le \cdots \le v_{n-1}$ is:
\[ \text{prize} = \sum_{i=n/2}^{n-1} v_i - \sum_{i=0}^{n/2-1} v_i \]

So we want to maximize the total prize. Each color contributes $k$ tickets across rounds: some are ``positive'' (among the top $n/2$ in their round, contributing $+v$) and some are ``negative'' (among the bottom $n/2$, contributing $-v$).

For each color, exactly $k$ tickets are used. Among these $k$ tickets, some number $p_i$ are positive and $k - p_i$ are negative. The constraint is $\sum_i p_i = k \cdot n/2$ (each round needs exactly $n/2$ positive tickets).

\subsection{Greedy Strategy}
To maximize total prize:
\begin{itemize}
  \item For positive contributions, use the largest tickets: tickets $x[i][m-1], x[i][m-2], \ldots, x[i][m-p_i]$.
  \item For negative contributions, use the smallest tickets: tickets $x[i][0], x[i][1], \ldots, x[i][k-p_i-1]$.
  \item Total contribution of color $i$: $\sum_{j=0}^{k-p_i-1} (-x[i][j]) + \sum_{j=m-p_i}^{m-1} x[i][j]$.
\end{itemize}

\subsection{Optimal $p_i$ Values}
Start with $p_i = 0$ for all $i$ (all negative). Then greedily increase $p_i$ values to maximize marginal gain. Increasing $p_i$ from $t$ to $t+1$: gain = $x[i][m-t-1] + x[i][k-t-1]$ (add a large positive and remove a small negative). Use a priority queue to select the best increments until $\sum p_i = k \cdot n/2$.

\section{C++ Solution}

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

long long find_maximum(int k, vector<vector<int>> x) {
    int n = x.size(), m = x[0].size();
    int half = n / 2;

    // p[i] = number of "positive" uses for color i
    vector<int> p(n, 0);
    // Initially all p[i] = 0: all k tickets used negatively
    // Marginal gain of incrementing p[i] from t to t+1:
    //   gain = x[i][m - t - 1] + x[i][k - 1 - t]
    //   (add top ticket as positive, remove bottom ticket from negative)

    // Priority queue: (gain, color_index)
    priority_queue<pair<ll, int>> pq;
    for (int i = 0; i < n; i++) {
        ll gain = (ll)x[i][m - 1] + x[i][k - 1];
        pq.push({gain, i});
    }

    int total_positive = k * half;
    ll total_prize = 0;

    // Initial total with all negative:
    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++)
            total_prize -= x[i][j];

    while (total_positive > 0) {
        auto [gain, i] = pq.top(); pq.pop();
        total_prize += gain;
        p[i]++;
        total_positive--;

        if (p[i] < k) {
            int t = p[i];
            ll new_gain = (ll)x[i][m - t - 1] + x[i][k - 1 - t];
            pq.push({new_gain, i});
        }
    }

    // Now assign tickets to rounds
    // For color i: positive tickets are x[i][m-p[i]], ..., x[i][m-1]
    //              negative tickets are x[i][0], ..., x[i][k-p[i]-1]

    // Build the allocation matrix s[i][j] = round number or -1
    vector<vector<int>> s(n, vector<int>(m, -1));

    // Assign rounds: each round needs exactly n/2 positive and n/2 negative
    // Collect (color, ticket_index, is_positive) and assign to rounds

    // Simple assignment: sort colors by p[i], assign positive tickets round by round
    // Use a greedy matching.

    // For each color, create a list of (round assignments)
    // Positive tickets: assign to rounds 0..p[i]-1 (will fix later)
    // Negative tickets: assign to rounds p[i]..k-1

    // Actually, we need each round to have exactly n/2 positive colors.
    // This is a bipartite matching problem, but can be solved greedily.

    // Create a list of (color, round_index) for positive assignments
    // Each color i has p[i] positive assignments.

    // Use a round-robin approach:
    vector<vector<int>> pos_rounds(n), neg_rounds(n);

    // Assign positive rounds: distribute using priority queue
    // Each round needs exactly half colors as positive
    vector<int> pos_count(k, 0);
    vector<pair<int,int>> color_order; // (p[i], i) sorted descending
    for (int i = 0; i < n; i++)
        color_order.push_back({p[i], i});
    sort(color_order.rbegin(), color_order.rend());

    // Greedy: for each color (in order of most positive), assign to rounds with fewest positive
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> round_pq;
    for (int r = 0; r < k; r++) round_pq.push({0, r});

    for (auto [pi, i] : color_order) {
        vector<pair<int,int>> tmp;
        for (int t = 0; t < pi; t++) {
            auto [cnt, r] = round_pq.top(); round_pq.pop();
            pos_rounds[i].push_back(r);
            tmp.push_back({cnt + 1, r});
        }
        for (auto& pr : tmp) round_pq.push(pr);
    }

    // Assign negative rounds: remaining rounds for each color
    for (int i = 0; i < n; i++) {
        set<int> pos_set(pos_rounds[i].begin(), pos_rounds[i].end());
        for (int r = 0; r < k; r++)
            if (!pos_set.count(r))
                neg_rounds[i].push_back(r);
    }

    // Fill allocation
    for (int i = 0; i < n; i++) {
        // Positive: largest tickets -> sort positive rounds doesn't matter
        sort(pos_rounds[i].begin(), pos_rounds[i].end());
        for (int t = 0; t < p[i]; t++) {
            int ticket = m - p[i] + t;
            int round = pos_rounds[i][t];
            s[i][ticket] = round;
        }
        // Negative: smallest tickets
        sort(neg_rounds[i].begin(), neg_rounds[i].end());
        for (int t = 0; t < k - p[i]; t++) {
            int ticket = t;
            int round = neg_rounds[i][t];
            s[i][ticket] = round;
        }
    }

    // allocate_tickets(s); // IOI grader call
    // For local testing:
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            printf("%d ", s[i][j]);
        printf("\n");
    }

    return total_prize;
}

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<vector<int>> x(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &x[i][j]);
    printf("%lld\n", find_maximum(k, x));
    return 0;
}
\end{lstlisting}

\section{Complexity Analysis}
\begin{itemize}
  \item \textbf{Time complexity:} $O(nk \log(nk))$ for the priority queue operations during greedy selection and round assignment.
  \item \textbf{Space complexity:} $O(nm)$ for the allocation matrix.
\end{itemize}

\end{document}