IOI 2009 - Archery

// IOI 2009 - Archery
// Binary search on starting position; simulate tournament rounds.
// O(N^2 log N) for full binary search, O(N^3) brute-force below.
#include <bits/stdc++.h>
using namespace std;

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

    int N, R;
    cin >> N >> R;

    // Our rank among all 2N+1 archers (1-indexed; lower = stronger)
    int myRank;
    cin >> myRank;

    vector<int> s(2 * N);
    for (int i = 0; i < 2 * N; i++) {
        cin >> s[i];
    }

    // After at most 2N rounds the system is periodic.
    int R_eff = min(R, 2 * N);
    int me = 2 * N; // our internal id

    // Simulate tournament with us starting at target 'startPos' (0-indexed).
    // Returns the target we end up at after R_eff rounds.
    auto simulate = [&](int startPos) -> int {
        vector<vector<int>> targets(N);

        // Place archers: 2 per target, except at startPos we replace one slot.
        int idx = 0;
        for (int t = 0; t < N; t++) {
            if (t == startPos) {
                targets[t].push_back(me);
                targets[t].push_back(idx++);
            } else {
                targets[t].push_back(idx++);
                targets[t].push_back(idx++);
            }
        }

        // Returns true if archer x beats archer y.
        auto stronger = [&](int x, int y) -> bool {
            int sx = (x == me) ? myRank : (x + 1);
            int sy = (y == me) ? myRank : (y + 1);
            return sx < sy;
        };

        int myTarget = startPos;
        for (int r = 0; r < R_eff; r++) {
            vector<vector<int>> newTargets(N);
            for (int t = 0; t < N; t++) {
                int a = targets[t][0], b = targets[t][1];
                int winner, loser;
                if (stronger(a, b)) { winner = a; loser = b; }
                else                { winner = b; loser = a; }

                // Winner moves towards target 0, loser towards target N-1.
                int wDest = max(0, t - 1);
                int lDest = min(N - 1, t + 1);
                newTargets[wDest].push_back(winner);
                newTargets[lDest].push_back(loser);
            }
            targets = newTargets;

            // Locate ourselves.
            for (int t = 0; t < N; t++) {
                for (int x : targets[t]) {
                    if (x == me) myTarget = t;
                }
            }
        }
        return myTarget;
    };

    // Try every starting position; pick the one giving the best (lowest) target.
    int bestTarget = N, bestStart = 0;
    for (int p = 0; p < N; p++) {
        int result = simulate(p);
        if (result < bestTarget) {
            bestTarget = result;
            bestStart = p;
        }
    }

    cout << bestStart + 1 << "\n"; // 1-indexed output
    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{green!60!black},
  stringstyle=\color{red!70!black},
  numbers=left,
  numberstyle=\tiny\color{gray},
  breaklines=true,
  frame=single,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2009 -- Archery}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Statement}
There are $2N$ archers at $N$ targets (2 per target). In each round, at each target the stronger archer moves to the next lower-numbered target (or stays at target~1) and the weaker moves to the next higher-numbered target (or stays at target~$N$). You are an additional archer choosing a starting target. After $R$ rounds, determine which starting target minimizes your final target number.

\section{Solution}

\subsection{Binary Search on Starting Position}
The key observation is that your final position after $R$ rounds is a function of your starting target, and this function has structure that allows binary search (or a direct $O(N \log N)$ approach).

After at most $N$ rounds, the configuration becomes periodic. So we simulate $\min(R, 2N)$ rounds. For each candidate starting position, the simulation runs in $O(N)$ time.

\subsection{Efficient Simulation}
For a fixed starting target $p$:
\begin{enumerate}
    \item Place yourself at target $p$; distribute the other $2N$ archers into the targets.
    \item Simulate $\min(R, 2N)$ rounds, tracking your position.
    \item The simulation can be optimized by noting that after entering target~1, you either stay there (if you keep winning) or get pushed to target~2.
\end{enumerate}

\subsection{Complexity}
\begin{itemize}
    \item \textbf{Binary search + simulation:} $O(N^2)$ in the worst case (trying $O(N)$ starting positions with $O(N)$ simulation each), or $O(N \log N)$ with binary search on the starting position.
    \item \textbf{Space:} $O(N)$.
\end{itemize}

\section{C++ Solution}

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

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

    int N, R;
    cin >> N >> R;

    // Read 2N archer strengths (lower rank = stronger)
    // Archers are 0-indexed; we are archer 2N (id = 2*N)
    int myRank;
    cin >> myRank;

    vector<int> strength(2 * N);
    for(int i = 0; i < 2 * N; i++) cin >> strength[i];

    int R_eff = min(R, 2 * N);
    int me = 2 * N;

    // Compare strengths: lower rank = stronger
    auto stronger = [&](int a, int b) -> bool {
        int sa = (a == me) ? myRank : strength[a];
        int sb = (b == me) ? myRank : strength[b];
        return sa < sb;
    };

    auto simulate = [&](int startPos) -> int {
        // Place archers: 2 per target, we replace one at startPos
        vector<array<int,2>> targets(N);
        int idx = 0;
        for(int t = 0; t < N; t++){
            if(t == startPos){
                targets[t] = {me, idx};
                idx++;
            } else {
                targets[t] = {idx, idx + 1};
                idx += 2;
            }
        }

        int myTarget = startPos;
        for(int r = 0; r < R_eff; r++){
            vector<vector<int>> newTargets(N);
            for(int t = 0; t < N; t++){
                int a = targets[t][0], b = targets[t][1];
                int winner, loser;
                if(stronger(a, b)){ winner = a; loser = b; }
                else { winner = b; loser = a; }
                newTargets[max(0, t - 1)].push_back(winner);
                newTargets[min(N - 1, t + 1)].push_back(loser);
            }
            for(int t = 0; t < N; t++){
                targets[t] = {newTargets[t][0], newTargets[t][1]};
                for(int x : newTargets[t])
                    if(x == me) myTarget = t;
            }
        }
        return myTarget;
    };

    int bestTarget = N, bestStart = 0;
    for(int p = 0; p < N; p++){
        int result = simulate(p);
        if(result < bestTarget){
            bestTarget = result;
            bestStart = p;
        }
    }

    cout << bestStart + 1 << "\n";
    return 0;
}
\end{lstlisting}

\section{Notes}
The solution above is a direct simulation, correct for small inputs. For the full IOI constraints ($N$ up to $200\,000$), the intended $O(N \log N)$ solution exploits the following: binary search on the starting position combined with an efficient check that uses the observation that after entering target~1, the archer's subsequent behavior is periodic and predictable. The binary search works because the function mapping starting position to final position is structured (piecewise monotone).

\end{document}