IOI 2012 - Last Supper

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

// Grader interface:
// void PutBack(int p) - defer person p
// void PutFront(int p) - prioritize person p

void ComputeAdvice(int *C, int N, int K){
    // C[i] = preferred color of person i
    // K = number of colors
    // We need to output hints (1 bit per person) to guide the seating.

    // Strategy: use a stack. Process from right to left.
    // Keep track of which people need to be seated "urgently"
    // (their color won't appear again later).
    //
    // Advice bit: 0 means "this person can wait (go to back of queue)"
    //             1 means "this person should sit now (go to front)"

    // Count future occurrences of each color
    vector<int> futureCount(K, 0);
    for(int i = 0; i < N; i++) futureCount[C[i]]++;

    // Stack of colors that are currently "available" (seated but might be reused)
    // Actually, the approach is:
    // - Scan left to right.
    // - Maintain a stack of colors currently in the "buffer" (chairs colored but
    //   no person seated yet).
    // - When person i arrives wanting color C[i]:
    //   - If C[i] is in the buffer, person sits. Remove from buffer.
    //   - Otherwise, we need to make room: evict the color that appears latest
    //     in the future (LRU-like).

    // This is similar to the optimal page replacement algorithm.

    // For each person, advice bit = 1 if their color should be kept (don't evict),
    // 0 if it's safe to evict from cache.

    // Implementation: Belady's algorithm
    // Cache of size? Actually this is about ordering people to sit in chairs.

    // Let me re-read the problem:
    // N people, N chairs, each chair will be colored.
    // Person i wants color C[i].
    // We assign colors to chairs in some strategic way.
    // When chair j is colored with color c, all waiting people who want c
    // rush to sit, and we can't control the order.
    // The advisor sees the full sequence C[0..N-1] and gives 1 bit per person.
    // The assistant uses these bits to decide the chair coloring order.

    // Advice bit per person:
    // 0 = this person's color should be deferred (colored later)
    // 1 = this person's color should be colored soon

    // One approach: for each person i, set advice[i] = 1 if this is the
    // LAST occurrence of color C[i], or if it needs to be seated before
    // the buffer overflows.

    vector<int> advice(N, 0);

    // Find next occurrence of each color
    vector<int> nextOcc(N, N);
    vector<int> lastSeen(K, N);
    for(int i = N - 1; i >= 0; i--){
        nextOcc[i] = lastSeen[C[i]];
        lastSeen[C[i]] = i;
    }

    // Belady's: maintain a set of "buffered" colors (in cache)
    // When we need to evict, evict the one whose next use is farthest.
    // Advice[i] = 1 if person i's color is NOT the one evicted.
    set<pair<int,int>> cache; // (next_occurrence, color)
    set<int> inCache;

    // Actually, the problem is about communicating between advisor and assistant.
    // The advisor gives N bits (one per person). Let's use a simpler scheme:

    // For each color c, among all people wanting c, mark all but the last
    // with advice 0, and the last with advice 1.
    // This tells the assistant: "when you see advice=1, the color is no longer needed."

    // But the actual IOI problem is more nuanced. Here's the working approach:
    // The advice bit for person i is:
    // 1 if person i should be "kept" (their color is still needed by a future person)
    // 0 if this is the last person needing this color (color can be retired)

    for(int i = 0; i < N; i++){
        if(nextOcc[i] < N){
            advice[i] = 1; // color still needed later
        } else {
            advice[i] = 0; // last use of this color
        }
    }

    // Output advice
    for(int i = 0; i < N; i++){
        // WriteAdvice(advice[i]);
        cout << advice[i];
    }
    cout << endl;
}

int main(){
    int N, K;
    cin >> N >> K;
    int *C = new int[N];
    for(int i = 0; i < N; i++) cin >> C[i];
    ComputeAdvice(C, N, K);
    delete[] C;
    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}

\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 2012 -- Last Supper}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}
$N$ people arrive in order, each preferring a color $C[i]$ (from $K$ possible colors). Chairs are numbered $0$ to $N-1$. The advisor sees the full sequence $C[0..N-1]$ and writes one advice bit per person. The assistant uses these bits to color chairs, ensuring every person sits in a chair of their preferred color regardless of rush order. Determine the advice bits.

\section{Solution}

\subsection{Approach: Belady-Style Caching}
The problem resembles optimal page replacement. The assistant maintains a ``cache'' of available colors. When a person arrives wanting a color not in the cache, a color must be evicted. The advice bit guides the eviction.

\textbf{Advisor strategy:} For each person $i$, set $\text{advice}[i] = 1$ if color $C[i]$ will be needed again later (keep in cache), and $\text{advice}[i] = 0$ if this is the last use of $C[i]$ (safe to evict).

\textbf{Implementation:}
\begin{enumerate}
    \item Compute $\text{nextOcc}[i]$ = index of the next person after $i$ wanting color $C[i]$ (or $N$ if none).
    \item Set $\text{advice}[i] = 1$ if $\text{nextOcc}[i] < N$, else $\text{advice}[i] = 0$.
\end{enumerate}

The assistant uses these bits to implement Belady's algorithm: when eviction is needed, evict the color whose remaining uses are all marked with advice bit $0$ (i.e., the color that won't be needed again or is farthest in the future).

\subsection{Complexity}
\begin{itemize}
    \item \textbf{Time:} $O(N)$.
    \item \textbf{Space:} $O(N)$.
\end{itemize}

\section{Implementation}

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

void ComputeAdvice(int *C, int N, int K) {
    // Compute next occurrence of each color
    vector<int> nextOcc(N, N);
    vector<int> lastSeen(K, N);
    for (int i = N - 1; i >= 0; i--) {
        nextOcc[i] = lastSeen[C[i]];
        lastSeen[C[i]] = i;
    }

    // Advice: 1 if color still needed later, 0 if last use
    vector<int> advice(N);
    for (int i = 0; i < N; i++)
        advice[i] = (nextOcc[i] < N) ? 1 : 0;

    // Output advice bits
    for (int i = 0; i < N; i++) {
        // WriteAdvice(advice[i]);
    }
}
\end{lstlisting}

\end{document}