IOI 2008 - Fish

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

const int MOD = 1e9 + 7;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

long long modinv(long long a, long long mod) {
    return power(a, mod - 2, mod);
}

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

    int N, K;
    cin >> N >> K;

    vector<long long> sz(N);
    vector<int> sp(N); // species (0-indexed)
    for (int i = 0; i < N; i++) {
        cin >> sz[i] >> sp[i];
        sp[i]--;
    }

    // Sort by size
    vector<int> order(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return sz[a] < sz[b];
    });

    // For each fish i (in sorted order), find the position of the first fish
    // of the same species with size > 2 * sz[i].
    // This determines which fish of the same species can coexist with i.

    // Group fish by species (sorted by size within each species)
    vector<vector<int>> bySpecies(K);
    for (int i = 0; i < N; i++) {
        bySpecies[sp[order[i]]].push_back(i); // position in sorted order
    }

    // For each fish at sorted position i, find how many fish of the same
    // species have size in (sz[order[i]], 2 * sz[order[i]]]
    // (these can coexist with fish i as part of species sp[order[i]]).

    // Count valid subsets:
    // A valid subset S has the property that for each species t,
    // max_size(S, t) <= 2 * min_size(S, t).

    // Approach: iterate over all possible "minimum fish" m.
    // For a given minimum fish m with size s_m and species t_m:
    // - All fish in S must have size >= s_m (m is the global minimum).
    // - For species t_m: fish in S must have size in [s_m, 2*s_m].
    // - For other species t: fish in S can have size in [s_m, 2*min_t]
    //   where min_t is the smallest fish of species t in S.
    //   But min_t >= s_m, so the constraint is within species.
    // Actually, the constraint is per-species: for each species,
    // the ratio max/min <= 2. The constraints are INDEPENDENT per species.

    // So the total number of valid subsets = product over species of
    // (number of valid subsets of that species) - but that overcounts
    // subsets where multiple species have fish.

    // Actually, since the constraints are independent per species:
    // Total valid subsets (including empty) = product over species of
    // (number of valid subsets of that species, including the empty subset for that species).

    // For species t with fish sizes s_1 < s_2 < ... < s_m:
    // A valid subset of species t is any subset {s_i, s_{i+1}, ..., s_j}
    // where s_j <= 2 * s_i. (Since the sizes are sorted and distinct,
    // and a valid subset can be non-contiguous as long as max <= 2*min.)

    // Wait: actually ANY subset with max <= 2*min is valid, not just contiguous.
    // So for species t, count subsets of {s_1, ..., s_m} where max/min <= 2.

    // For each possible minimum s_i, count subsets where min = s_i and
    // all other elements are in (s_i, 2*s_i]. Let f(i) = number of elements
    // in (s_i, 2*s_i] (not counting s_i itself). Then the number of subsets
    // with min = s_i is 2^f(i) (choose any subset of the f(i) elements,
    // plus s_i is included). But we also need to ensure s_i is actually the min,
    // meaning no element < s_i is included.

    // Since we're considering subsets of species t only, and s_i is the
    // i-th smallest:
    // Subsets with minimum exactly s_i and max <= 2*s_i:
    //   - Include s_i.
    //   - Include any subset of {s_{i+1}, ..., s_{j}} where s_j <= 2*s_i.
    //   - Exclude s_1, ..., s_{i-1} (they're smaller, not relevant since
    //     we're choosing from the species's fish).
    // Actually, since we're partitioning by minimum, the count for
    // species t = sum over i of 2^{f(i)} where f(i) = |{j > i : s_j <= 2*s_i}|.
    // Plus 1 for the empty subset.

    // Total answer = product over species of (1 + sum_i 2^f(i)) - 1
    // (subtract 1 for the all-empty case, which is the empty subset overall)

    long long ans = 1;

    for (int t = 0; t < K; t++) {
        vector<long long> sizes;
        for (int idx : bySpecies[t]) {
            sizes.push_back(sz[order[idx]]);
        }
        sort(sizes.begin(), sizes.end());

        int m = sizes.size();
        long long speciesCount = 1; // 1 for empty subset

        int j = 0;
        for (int i = 0; i < m; i++) {
            // Find how many elements in (sizes[i], 2*sizes[i]]
            // = elements at indices i+1, ..., j-1 where sizes[j-1] <= 2*sizes[i]
            while (j < m && sizes[j] <= 2 * sizes[i]) j++;
            int f = j - i - 1; // elements in (sizes[i], 2*sizes[i]]
            speciesCount = (speciesCount + power(2, f, MOD)) % MOD;
        }

        ans = ans * speciesCount % MOD;
    }

    ans = (ans - 1 + MOD) % MOD; // subtract empty subset

    cout << ans << "\n";
    return 0;
}

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

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

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

\title{IOI 2008 -- Fish}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Statement}
In a lake there are $N$ fish of distinct sizes, each belonging to one of $K$ species. A subset $S$ is \textbf{valid} if, for every species~$t$, the largest and smallest fish of species~$t$ in $S$ satisfy $\max \le 2 \cdot \min$. Count the number of non-empty valid subsets modulo a prime~$p$.

\section{Solution}

\subsection{Independence Across Species}
\begin{lemma}
The validity constraint is independent across species: for each species, we require $\max / \min \le 2$ within that species, regardless of other species. Therefore:
\[
\text{(valid subsets including empty)} = \prod_{t=1}^{K} (\text{valid subsets of species } t \text{, including empty}).
\]
\end{lemma}

\subsection{Counting Per-Species Valid Subsets}
For species~$t$ with fish sizes $s_1 < s_2 < \cdots < s_m$ (sorted), a valid subset is any subset $\{s_i, \ldots\}$ with $\max \le 2 \cdot \min$. We partition by the choice of minimum element.

For minimum element $s_i$, the eligible elements are those with size in $[s_i, 2s_i]$. Let $f(i) = |\{j > i : s_j \le 2s_i\}|$ (elements strictly larger than $s_i$ but within the $2\times$ bound). The number of subsets with minimum exactly $s_i$ is $2^{f(i)}$ (include $s_i$ and choose any subset of the $f(i)$ eligible larger elements).

Using two pointers (since $f(i)$ is non-decreasing in $i$), we compute $\sum_i 2^{f(i)}$ for each species in total $O(m)$ time.

\subsection{Final Answer}
\[
\text{Answer} = \left(\prod_{t=1}^{K} \Bigl(1 + \sum_{i} 2^{f_t(i)}\Bigr)\right) - 1,
\]
where the $-1$ removes the global empty subset.

\subsection{Complexity}
\begin{itemize}
    \item \textbf{Time:} $O(N \log N)$ for sorting, $O(N)$ for the two-pointer computation.
    \item \textbf{Space:} $O(N)$.
\end{itemize}

\section{C++ Solution}

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

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

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

    int N, K;
    long long MOD;
    cin >> N >> K >> MOD;

    vector<long long> sz(N);
    vector<int> sp(N);
    for (int i = 0; i < N; i++) {
        cin >> sz[i] >> sp[i];
        sp[i]--;
    }

    // Group fish by species, sorted by size
    vector<vector<long long>> bySpecies(K);
    for (int i = 0; i < N; i++)
        bySpecies[sp[i]].push_back(sz[i]);
    for (int t = 0; t < K; t++)
        sort(bySpecies[t].begin(), bySpecies[t].end());

    long long ans = 1;
    for (int t = 0; t < K; t++) {
        auto& sizes = bySpecies[t];
        int m = sizes.size();
        if (m == 0) continue;

        long long speciesCount = 1; // empty subset of this species
        int j = 0;
        for (int i = 0; i < m; i++) {
            while (j < m && sizes[j] <= 2 * sizes[i]) j++;
            int f = j - i - 1; // elements in (sizes[i], 2*sizes[i]]
            speciesCount = (speciesCount + power(2, f, MOD)) % MOD;
        }
        ans = ans * speciesCount % MOD;
    }

    ans = (ans - 1 + MOD) % MOD; // subtract the global empty subset
    cout << ans << "\n";
    return 0;
}
\end{lstlisting}

\section{Notes}
The per-species independence is the key structural insight. Within each species, the two-pointer technique efficiently counts valid subsets by tracking the rightmost element within the $2\times$ ratio bound. The pointer $j$ is monotonically non-decreasing, giving amortized $O(1)$ per element.

\end{document}