ICPC 2019 - J. Miniature Golf

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

namespace {

long long floor_div(long long a, long long b) {
    if (a >= 0) {
        return a / b;
    }
    return -((-a + b - 1) / b);
}

void add_interval(long long A, long long B, int L, int R, vector<pair<int, int>>& events) {
    if (L > R) {
        return;
    }

    long long lo = L;
    long long hi = R;
    if (B == 0) {
        if (A >= 0) {
            return;
        }
    } else if (B > 0) {
        hi = min<long long>(hi, floor_div(-A - 1, B));
    } else {
        long long C = -B;
        lo = max<long long>(lo, floor_div(A, C) + 1);
    }

    if (lo > hi) {
        return;
    }
    events.push_back({static_cast<int>(lo), +1});
    events.push_back({static_cast<int>(hi + 1), -1});
}

void solve() {
    int p, h;
    cin >> p >> h;
    vector<vector<int>> scores(p, vector<int>(h));
    int max_score = 0;
    for (int i = 0; i < p; ++i) {
        for (int j = 0; j < h; ++j) {
            cin >> scores[i][j];
            max_score = max(max_score, scores[i][j]);
        }
        sort(scores[i].begin(), scores[i].end());
    }

    vector<int> answer(p, p);
    for (int i = 0; i < p; ++i) {
        vector<pair<int, int>> events;
        events.reserve(4 * p * h);

        for (int j = 0; j < p; ++j) {
            if (i == j) {
                continue;
            }

            const vector<int>& a = scores[i];
            const vector<int>& b = scores[j];
            vector<int> breaks;
            breaks.reserve(2 * h);
            breaks.insert(breaks.end(), a.begin(), a.end());
            breaks.insert(breaks.end(), b.begin(), b.end());
            sort(breaks.begin(), breaks.end());
            breaks.erase(unique(breaks.begin(), breaks.end()), breaks.end());

            int pa = 0;
            int pb = 0;
            long long sum_a = 0;
            long long sum_b = 0;
            int current = 1;

            for (int s : breaks) {
                if (current <= s - 1) {
                    long long A = sum_a - sum_b;
                    long long B = static_cast<long long>(h - pa) - static_cast<long long>(h - pb);
                    add_interval(A, B, current, s - 1, events);
                }

                while (pa < h && a[pa] == s) {
                    sum_a += a[pa];
                    ++pa;
                }
                while (pb < h && b[pb] == s) {
                    sum_b += b[pb];
                    ++pb;
                }
                current = s;
            }

            if (current <= max_score) {
                long long A = sum_a - sum_b;
                long long B = static_cast<long long>(h - pa) - static_cast<long long>(h - pb);
                add_interval(A, B, current, max_score, events);
            }
        }

        sort(events.begin(), events.end());
        int active = 0;
        int best = 0;
        int idx = 0;
        while (idx < static_cast<int>(events.size())) {
            int x = events[idx].first;
            if (x > max_score) {
                break;
            }
            while (idx < static_cast<int>(events.size()) && events[idx].first == x) {
                active += events[idx].second;
                ++idx;
            }
            best = max(best, active);
        }

        answer[i] = p - best;
    }

    for (int x : answer) {
        cout << x << '\n';
    }
}

}  // namespace

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

    solve();
    return 0;
}

\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{enumitem}

\title{ICPC World Finals 2019\\J. Miniature Golf}
\author{}
\date{}

\begin{document}
\maketitle

\section*{Problem Summary}

For one unknown positive integer cap $\ell$, each hole score $a$ is replaced by $\min(a,\ell)$.
For every player we must choose the cap that gives that player the best possible rank, where rank is
the number of players whose adjusted total score is at most theirs.

\section*{Key Observations}

\begin{itemize}[leftmargin=*]
    \item For a fixed player $i$, minimizing their rank is the same as maximizing the number of other
    players $j$ with adjusted total $S_i(\ell) < S_j(\ell)$.
    \item For one player, $S(\ell)=\sum_k \min(a_k,\ell)$ is a piecewise-linear function of $\ell$.
    Its slope only changes when $\ell$ reaches one of that player's raw hole scores.
    \item Therefore, for a fixed pair $(i,j)$, the difference
    $D_{ij}(\ell)=S_i(\ell)-S_j(\ell)$ is also piecewise linear, and the breakpoints are exactly the
    scores of players $i$ and $j$.
    \item Between two consecutive breakpoints, the inequality $D_{ij}(\ell)<0$ is just a linear
    inequality on an interval of integers, so it becomes either empty or one integer interval.
\end{itemize}

\section*{Algorithm}

\begin{enumerate}[leftmargin=*]
    \item Sort each player's $h$ scores.
    \item Fix a player $i$. For every other player $j$, merge the sorted score lists of $i$ and $j$.
    Sweep the distinct breakpoint values in increasing order.
    \item During this sweep maintain, for both players, how many scores are already at most the current
    cap and the sum of those scores. On any integer interval $[L,R]$ between consecutive breakpoints,
    both adjusted totals have the form $A+B\ell$, so $S_i(\ell)<S_j(\ell)$ can be converted into one
    integer interval inside $[L,R]$.
    \item Add this interval to an event list for player $i$ using a difference sweep: $+1$ at its left
    endpoint and $-1$ after its right endpoint.
    \item After all opponents $j$ are processed, sweep the events in order. The maximum number of active
    intervals is the maximum number of players that $i$ strictly beats for some cap.
    \item Output $p-\text{best}$ for player $i$, because rank counts all players with score at most theirs.
\end{enumerate}

\section*{Correctness Proof}

We prove that the algorithm returns the correct answer.

\paragraph{Lemma 1.}
For a fixed player $i$ and cap $\ell$, the rank of player $i$ equals
$p - |\{j \neq i : S_i(\ell) < S_j(\ell)\}|$.

\paragraph{Proof.}
Exactly the players not counted in the set are those whose adjusted total is at most $S_i(\ell)$.
This includes player $i$ themself. Hence the rank is the total number of players minus the number of
players strictly beaten by $i$. \qed

\paragraph{Lemma 2.}
For any fixed pair of players $(i,j)$, the set of integer caps $\ell \ge 1$ such that
$S_i(\ell) < S_j(\ell)$ is a union of $O(h)$ integer intervals, and the algorithm enumerates all of them.

\paragraph{Proof.}
The only values where either $S_i$ or $S_j$ can change slope are the raw scores of players $i$ and $j$,
so there are $O(h)$ maximal integer intervals on which both functions are linear.
On one such interval we have
$S_i(\ell)=\alpha_i+\beta_i \ell$ and $S_j(\ell)=\alpha_j+\beta_j \ell$, hence
$S_i(\ell)-S_j(\ell)=A+B\ell$ for constants $A,B$.
The strict inequality $A+B\ell<0$ over integers is either false everywhere on that interval,
true everywhere, or true on one suffix/prefix of the interval. Therefore it yields exactly one integer
interval, which the algorithm adds. Doing this for every linear piece enumerates the full solution set.
\qed

\paragraph{Lemma 3.}
For a fixed player $i$, after processing all other players, the maximum active event count equals the
maximum possible number of opponents that $i$ strictly beats for some cap.

\paragraph{Proof.}
By Lemma 2, each opponent $j$ contributes exactly the caps where $S_i(\ell) < S_j(\ell)$.
Thus, at any cap $\ell$, the active event count is precisely the number of opponents beaten by $i$.
Taking the maximum over the sweep gives the maximum possible number of beaten opponents. \qed

\paragraph{Theorem.}
The algorithm outputs the minimum possible rank for every player.

\paragraph{Proof.}
Fix a player $i$. By Lemma 3, the event sweep finds the largest number of opponents that $i$ can
strictly beat for some cap. By Lemma 1, subtracting this value from $p$ gives exactly the best rank
attainable by player $i$. Since the algorithm does this independently for every player, all outputs are
correct. \qed

\section*{Complexity Analysis}

For a fixed ordered pair of players, merging the two sorted score lists and generating intervals takes
$O(h)$ time. Repeating this for all pairs takes $O(p^2 h)$ time.
For each player we then sort $O(ph)$ sweep events, so the total sorting time is
$O(p^2 h \log(ph))$.
The memory usage is $O(ph)$ for the scores and one player's event list.

\section*{Implementation Notes}

\begin{itemize}[leftmargin=*]
    \item It is enough to consider caps $\ell \in [1, M]$, where $M$ is the largest raw score in the input.
    For $\ell \ge M$, no score changes any more.
    \item The totals can be as large as $50 \cdot 10^9$, so all arithmetic for adjusted sums and linear
    coefficients should use 64-bit integers.
\end{itemize}

\end{document}