IOI 2014 - Game

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

struct DSU {
    vector<int> parent, rank_;
    int components;

    void init(int n) {
        parent.resize(n);
        rank_.resize(n, 0);
        iota(parent.begin(), parent.end(), 0);
        components = n;
    }

    int find(int x) {
        while (parent[x] != x) x = parent[x] = parent[parent[x]];
        return x;
    }

    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b]) rank_[a]++;
        components--;
        return true;
    }
};

// For IOI grader interface:
// void initialize(int n) - called once
// int hasEdge(int u, int v) - called for each query, return 0 or 1

DSU dsu;
// remaining[i][j] = number of unqueried edges between component i and j
// Since components merge, we use a map
// Actually, we use a different approach: count remaining edges per component pair
// This is complex with merging. Simpler: maintain for each component pair,
// the count of unqueried edges.

// Better approach: use the DSU and a 2D counter.
// But n can be large. Use map<pair<int,int>, int>.

map<pair<int,int>, int> remaining;
int N;

pair<int,int> makeKey(int a, int b) {
    if (a > b) swap(a, b);
    return {a, b};
}

void initialize(int n) {
    N = n;
    dsu.init(n);
    remaining.clear();
    // Initially, between each pair of nodes, there's 1 unqueried edge
    // Between component {i} and component {j}: 1 edge
    // We initialize lazily: remaining edges between comp a and comp b
    // = (size_a * size_b) - (edges already queried between them)
    // Lazy init: if key not in map, compute it.
}

// We need sizes for lazy init
vector<int> comp_size;

void initialize2(int n) {
    N = n;
    dsu.init(n);
    remaining.clear();
    comp_size.assign(n, 1);
}

int hasEdge(int u, int v) {
    int a = dsu.find(u), b = dsu.find(v);
    if (a == b) return 0; // same component, say NO

    auto key = makeKey(a, b);
    if (remaining.find(key) == remaining.end()) {
        // Lazy init: total edges = size_a * size_b
        remaining[key] = comp_size[a] * comp_size[b];
    }
    remaining[key]--;

    if (remaining[key] == 0) {
        // This is the last edge between these components, must say YES
        remaining.erase(key);
        // Merge components, update remaining counts
        int sa = comp_size[a], sb = comp_size[b];

        // For all other components c, merge remaining[a,c] and remaining[b,c]
        // Collect all entries involving a or b
        map<int, int> neighbors;
        vector<pair<int,int>> to_erase;
        for (auto &[k, val] : remaining) {
            if (k.first == a || k.second == a) {
                int other = k.first == a ? k.second : k.first;
                if (other != b) neighbors[other] += val;
                to_erase.push_back(k);
            } else if (k.first == b || k.second == b) {
                int other = k.first == b ? k.second : k.first;
                if (other != a) neighbors[other] += val;
                to_erase.push_back(k);
            }
        }
        for (auto &k : to_erase) remaining.erase(k);

        dsu.unite(a, b);
        int root = dsu.find(a);
        comp_size[root] = sa + sb;

        for (auto &[c, cnt] : neighbors) {
            int rc = dsu.find(c);
            remaining[makeKey(root, rc)] = cnt;
        }

        return 1;
    }
    return 0;
}

int main() {
    // This problem uses grader interaction.
    // Standalone test:
    int n;
    scanf("%d", &n);
    initialize2(n);

    // Simulate all possible queries
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int res = hasEdge(i, j);
            printf("Edge (%d, %d): %d\n", i, j, res);
        }
    }
    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{gray},
  stringstyle=\color{red},
  numbers=left,
  numberstyle=\tiny\color{gray},
  breaklines=true,
  frame=single,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2014 -- Game}
\author{}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}

You play the role of an interactor. A player asks queries of the form ``Is there an edge between $u$ and $v$?'' about a hidden graph on $n$ nodes. You must answer each query consistently (there must exist \emph{some} valid graph matching all your answers) and the final graph must be \textbf{connected}. Your goal is to \emph{maximise} the number of queries before the player can determine all edges, i.e., answer in a way that forces the player to ask all $\binom{n}{2}$ possible queries.

\section{Solution}

\begin{theorem}
The following greedy strategy forces the player to ask all $\binom{n}{2}$ queries: answer \textbf{NO} to every query unless doing so would make it impossible to connect the graph using remaining unqueried edges; in that case, answer \textbf{YES}.
\end{theorem}

\begin{proof}[Proof sketch]
After all queries are answered, the graph must be connected. At each query $(u,v)$:
\begin{itemize}
  \item If $u$ and $v$ are already in the same connected component, answering NO is always safe (removing an edge within a connected component cannot disconnect it), and the player gains no new information about cross-component edges.
  \item If $u$ and $v$ are in different components, answering NO is safe \emph{unless} $(u,v)$ is the last unqueried edge between these two components. In that case we must answer YES to preserve the possibility of connecting them.
\end{itemize}
Since the player cannot determine any edge without asking it (both answers remain consistent with some connected graph until the query is forced), the player must ask all $\binom{n}{2}$ queries.
\end{proof}

\textbf{Implementation.} Maintain a union-find and, for each pair of components, a count of unqueried inter-component edges.  When components merge, aggregate the counts.  Use lazy initialisation: the initial count between components of sizes $s_a$ and $s_b$ is $s_a \cdot s_b$.

\section{C++ Implementation}

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

struct DSU {
    vector<int> parent, rank_;
    void init(int n) {
        parent.resize(n);
        rank_.assign(n, 0);
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) x = parent[x] = parent[parent[x]];
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) swap(a, b);
        parent[b] = a;
        if (rank_[a] == rank_[b]) rank_[a]++;
        return true;
    }
};

DSU dsu;
vector<int> comp_size;
map<pair<int,int>, int> remaining;

pair<int,int> makeKey(int a, int b) {
    return a < b ? make_pair(a, b) : make_pair(b, a);
}

void initialize(int n) {
    dsu.init(n);
    comp_size.assign(n, 1);
    remaining.clear();
}

int hasEdge(int u, int v) {
    int a = dsu.find(u), b = dsu.find(v);
    if (a == b) return 0;

    auto key = makeKey(a, b);
    if (remaining.find(key) == remaining.end())
        remaining[key] = comp_size[a] * comp_size[b];
    remaining[key]--;

    if (remaining[key] == 0) {
        // Last unqueried edge between a and b: must answer YES
        remaining.erase(key);
        int sa = comp_size[a], sb = comp_size[b];

        // Merge remaining-edge counts for all other components
        map<int, int> neighbours;
        vector<pair<int,int>> to_erase;
        for (auto &[k, val] : remaining) {
            if (k.first == a || k.second == a) {
                int other = (k.first == a) ? k.second : k.first;
                if (other != b) neighbours[other] += val;
                to_erase.push_back(k);
            } else if (k.first == b || k.second == b) {
                int other = (k.first == b) ? k.second : k.first;
                if (other != a) neighbours[other] += val;
                to_erase.push_back(k);
            }
        }
        for (auto &k : to_erase) remaining.erase(k);

        dsu.unite(a, b);
        int root = dsu.find(a);
        comp_size[root] = sa + sb;

        for (auto &[c, cnt] : neighbours)
            remaining[makeKey(root, dsu.find(c))] = cnt;

        return 1;
    }
    return 0;
}
\end{lstlisting}

\section{Complexity Analysis}

\begin{itemize}
  \item \textbf{Queries answered}: all $\binom{n}{2}$, which is optimal.
  \item \textbf{Time per query}: $O(\alpha(n))$ for DSU operations. Component merges are $O(n)$ in the worst case but occur at most $n-1$ times, giving $O(n^2)$ total across all merges.
  \item \textbf{Total time}: $O(n^2)$.
  \item \textbf{Space}: $O(n^2)$ worst case for the map entries.
\end{itemize}

\end{document}