EP Ethan Pham AI/ML engineer publishing Project Euler proofs, ICPC and IOI archives, and theory-heavy engineering notes.
All IOI entries
Competitive Programming

IOI 2009 - POI

Compute solvers[j] for each task j. For each contestant i: score[i] = _ j:solved (N - solvers[j]), tasks[i] = number of tasks solved. Sort by the given criteria and find P 's rank. Complexity Time: O(NT + N N). Space:...

Source sync Apr 19, 2026
Track IOI
Year 2009
Files TeX and C++
Folder competitive_programming/ioi/2009/poi
IOI2009TeXC++
Source of truth

Source-first archive entry

This page is built from the copied files in competitive_programming/ioi/2009/poi. Edit competitive_programming/ioi/2009/poi/solution.tex to update the written solution and competitive_programming/ioi/2009/poi/solution.cpp to update the implementation.

The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.

Raw TeX Raw C++
Problem statement

Problem Statement

Rendered from the "Problem Statement" section inside solution.tex because this entry has no separate statement file.

Raw TeX

$N$ contestants solve $T$ tasks. The score for a task equals the number of contestants who did not solve it. Each contestant's total score is the sum of scores of tasks they solved. Rank contestants by score (descending), breaking ties by number of tasks solved (descending), then by contestant number (ascending). Output the score and rank of contestant $P$.

Editorial

Editorial

Rendered from the copied solution.tex file. The original TeX source remains available below.

Raw TeX

Solution

  1. Compute $\text{solvers}[j]$ for each task $j$.

  2. For each contestant $i$: $\text{score}[i] = \sum_{j:\text{solved}} (N - \text{solvers}[j])$, $\text{tasks}[i] = $ number of tasks solved.

  3. Sort by the given criteria and find $P$'s rank.

Complexity

  • Time: $O(NT + N \log N)$.

  • Space: $O(NT)$.

C++ Solution

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

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

    int N, T, P;
    cin >> N >> T >> P;
    P--;

    vector<vector<int>> solved(N, vector<int>(T));
    vector<int> solvers(T, 0);

    for(int i = 0; i < N; i++)
        for(int j = 0; j < T; j++){
            cin >> solved[i][j];
            solvers[j] += solved[i][j];
        }

    vector<int> score(N, 0), taskCount(N, 0);
    for(int i = 0; i < N; i++)
        for(int j = 0; j < T; j++)
            if(solved[i][j]){
                score[i] += N - solvers[j];
                taskCount[i]++;
            }

    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b){
        if(score[a] != score[b]) return score[a] > score[b];
        if(taskCount[a] != taskCount[b]) return taskCount[a] > taskCount[b];
        return a < b;
    });

    int rank = 0;
    for(int i = 0; i < N; i++)
        if(order[i] == P){ rank = i + 1; break; }

    cout << score[P] << " " << rank << "\n";
    return 0;
}
Source code

Code

Exact copied C++ implementation from solution.cpp.

C++ competitive_programming/ioi/2009/poi/solution.cpp

Exact copied implementation source.

Raw file 
// IOI 2009 - POI
// Compute scores (harder tasks = more points), rank contestants, output P's info.
// O(NT + N log N) time.
#include <bits/stdc++.h>
using namespace std;

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

    int N, T, P;
    cin >> N >> T >> P;
    P--; // convert to 0-indexed

    vector<vector<int>> solved(N, vector<int>(T));
    vector<int> solvers(T, 0);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < T; j++) {
            cin >> solved[i][j];
            solvers[j] += solved[i][j];
        }
    }

    // Task j is worth (N - solvers[j]) points.
    vector<int> score(N, 0), taskCount(N, 0);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < T; j++) {
            if (solved[i][j]) {
                score[i] += N - solvers[j];
                taskCount[i]++;
            }
        }
    }

    // Sort: score desc, tasks solved desc, contestant number asc.
    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        if (score[a] != score[b]) return score[a] > score[b];
        if (taskCount[a] != taskCount[b]) return taskCount[a] > taskCount[b];
        return a < b;
    });

    int rank = -1;
    for (int i = 0; i < N; i++) {
        if (order[i] == P) {
            rank = i + 1;
            break;
        }
    }

    cout << score[P] << " " << rank << "\n";
    return 0;
}
Source files

Source Files

Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.

TeX write-up competitive_programming/ioi/2009/poi/solution.tex

Exact copied write-up source.

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

\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 -- POI}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Statement}
$N$ contestants solve $T$ tasks. The score for a task equals the number of contestants who did \emph{not} solve it. Each contestant's total score is the sum of scores of tasks they solved. Rank contestants by score (descending), breaking ties by number of tasks solved (descending), then by contestant number (ascending). Output the score and rank of contestant~$P$.

\section{Solution}
\begin{enumerate}
    \item Compute $\text{solvers}[j]$ for each task $j$.
    \item For each contestant $i$: $\text{score}[i] = \sum_{j:\text{solved}} (N - \text{solvers}[j])$, $\text{tasks}[i] = $ number of tasks solved.
    \item Sort by the given criteria and find $P$'s rank.
\end{enumerate}

\subsection{Complexity}
\begin{itemize}
    \item \textbf{Time:} $O(NT + N \log N)$.
    \item \textbf{Space:} $O(NT)$.
\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, T, P;
    cin >> N >> T >> P;
    P--;

    vector<vector<int>> solved(N, vector<int>(T));
    vector<int> solvers(T, 0);

    for(int i = 0; i < N; i++)
        for(int j = 0; j < T; j++){
            cin >> solved[i][j];
            solvers[j] += solved[i][j];
        }

    vector<int> score(N, 0), taskCount(N, 0);
    for(int i = 0; i < N; i++)
        for(int j = 0; j < T; j++)
            if(solved[i][j]){
                score[i] += N - solvers[j];
                taskCount[i]++;
            }

    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b){
        if(score[a] != score[b]) return score[a] > score[b];
        if(taskCount[a] != taskCount[b]) return taskCount[a] > taskCount[b];
        return a < b;
    });

    int rank = 0;
    for(int i = 0; i < N; i++)
        if(order[i] == P){ rank = i + 1; break; }

    cout << score[P] << " " << rank << "\n";
    return 0;
}
\end{lstlisting}

\end{document}