IOI 2013 - Cave

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

// Grader functions:
// int tryCombination(int S[]) - returns first closed door, or -1 if all open
// void answer(int S[], int D[]) - report solution
// S[i] = correct position (0/1) for switch i
// D[i] = which door switch i controls

int tryCombination(int S[]);
void answer(int S[], int D[]);

void exploreCave(int N){
    vector<int> switchPos(N, -1);  // correct position for each switch
    vector<int> switchDoor(N, -1); // which door each switch controls
    vector<bool> determined(N, false); // whether switch i is determined

    for(int door = 0; door < N; door++){
        // Collect undetermined switches
        vector<int> unknown;
        for(int i = 0; i < N; i++){
            if(!determined[i]) unknown.push_back(i);
        }

        // First, determine the "test value" for unknown switches
        // that makes door 'door' close (so we can detect it).
        // Try setting all unknown switches to 0:
        int *S = new int[N];
        for(int i = 0; i < N; i++){
            if(determined[i]){
                S[i] = switchPos[i]; // known correct value
            } else {
                S[i] = 0;
            }
        }
        int result = tryCombination(S);
        int testVal; // the value for unknown switches that closes door 'door'
        if(result == door){
            // All unknowns at 0 -> door is closed
            // So the controlling switch's correct value is 1 (currently at 0 = wrong)
            testVal = 0; // setting unknown to 0 closes the door
        } else {
            // Door is open with all unknowns at 0
            // So correct value is 0 for the controlling switch
            // Set unknowns to 1 to close it
            testVal = 1;
        }

        // Binary search on unknown switches
        int lo = 0, hi = (int)unknown.size() - 1;
        while(lo < hi){
            int mid = (lo + hi) / 2;
            // Set switches unknown[lo..mid] to testVal, rest to 1-testVal
            for(int i = 0; i < N; i++){
                if(determined[i]){
                    S[i] = switchPos[i];
                } else {
                    S[i] = 1 - testVal; // default: opposite of testVal
                }
            }
            for(int i = lo; i <= mid; i++){
                S[unknown[i]] = testVal;
            }

            result = tryCombination(S);
            if(result == door){
                // The controlling switch is in [lo..mid] (with testVal, door closes)
                hi = mid;
            } else {
                // Door is open -> controlling switch NOT in [lo..mid]
                lo = mid + 1;
            }
        }

        // Switch unknown[lo] controls door 'door'
        int sw = unknown[lo];
        switchDoor[sw] = door;
        switchPos[sw] = 1 - testVal; // testVal closes it, so correct = opposite
        determined[sw] = true;

        delete[] S;
    }

    int *S = new int[N], *D = new int[N];
    for(int i = 0; i < N; i++){
        S[i] = switchPos[i];
        D[i] = switchDoor[i];
    }
    answer(S, D);
    delete[] S; delete[] D;
}

int main(){
    int N;
    cin >> N;
    exploreCave(N);
    return 0;
}

int tryCombination(int S[]){ return -1; }
void answer(int S[], int D[]){}

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

\begin{document}
\maketitle

\section{Problem Summary}
There is a cave with $N$ doors (numbered $0$ to $N-1$) and $N$ switches (numbered $0$ to $N-1$). Each switch controls exactly one door (a permutation), and each switch has a correct position (0 or 1) that opens its corresponding door. You can query the system by providing a switch configuration (array of 0s and 1s) and observing which door is the first closed door (or all open). Determine the mapping (which switch controls which door) and the correct position for each switch, using at most $70000$ queries.

\section{Solution Approach}
Use binary search to determine each switch-door mapping:

\begin{enumerate}
    \item Process doors in order $0, 1, \ldots, N-1$.
    \item For door $d$, we know the correct settings for switches controlling doors $0, \ldots, d-1$ (so those doors are open). The remaining switches are ``unknown.''
    \item Binary search on the set of unknown switches to find which one controls door $d$:
    \begin{itemize}
        \item Set the known switches to their correct values (doors 0..d-1 open).
        \item For unknown switches: set the first half to 0 and the rest to 1 (or vice versa).
        \item Query. If door $d$ is open, the controlling switch is in one half; if closed, it's in the other half.
        \item Recurse on the correct half until one switch remains.
    \end{itemize}
    \item Then determine the correct position for that switch by toggling it.
\end{enumerate}

\section{Complexity}
\begin{itemize}
    \item \textbf{Queries:} $O(N \log N)$ --- for each of $N$ doors, $O(\log N)$ binary search queries.
    \item For $N = 5000$: $5000 \times 13 \approx 65000 < 70000$. Fits within budget.
\end{itemize}

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

// Grader functions:
// int tryCombination(int S[]) - returns first closed door, or -1 if all open
// void answer(int S[], int D[]) - report solution
// S[i] = correct position (0/1) for switch i
// D[i] = which door switch i controls

int tryCombination(int S[]);
void answer(int S[], int D[]);

void exploreCave(int N){
    vector<int> switchPos(N, -1);  // correct position for each switch
    vector<int> switchDoor(N, -1); // which door each switch controls
    vector<bool> determined(N, false); // whether switch i is determined

    for(int door = 0; door < N; door++){
        // Collect undetermined switches
        vector<int> unknown;
        for(int i = 0; i < N; i++){
            if(!determined[i]) unknown.push_back(i);
        }

        // First, determine the "test value" for unknown switches
        // that makes door 'door' close (so we can detect it).
        // Try setting all unknown switches to 0:
        int *S = new int[N];
        for(int i = 0; i < N; i++){
            if(determined[i]){
                S[i] = switchPos[i]; // known correct value
            } else {
                S[i] = 0;
            }
        }
        int result = tryCombination(S);
        int testVal; // the value for unknown switches that closes door 'door'
        if(result == door){
            // All unknowns at 0 -> door is closed
            // So the controlling switch's correct value is 1 (currently at 0 = wrong)
            testVal = 0; // setting unknown to 0 closes the door
        } else {
            // Door is open with all unknowns at 0
            // So correct value is 0 for the controlling switch
            // Set unknowns to 1 to close it
            testVal = 1;
        }

        // Binary search on unknown switches
        int lo = 0, hi = (int)unknown.size() - 1;
        while(lo < hi){
            int mid = (lo + hi) / 2;
            // Set switches unknown[lo..mid] to testVal, rest to 1-testVal
            for(int i = 0; i < N; i++){
                if(determined[i]){
                    S[i] = switchPos[i];
                } else {
                    S[i] = 1 - testVal; // default: opposite of testVal
                }
            }
            for(int i = lo; i <= mid; i++){
                S[unknown[i]] = testVal;
            }

            result = tryCombination(S);
            if(result == door){
                // The controlling switch is in [lo..mid] (with testVal, door closes)
                hi = mid;
            } else {
                // Door is open -> controlling switch NOT in [lo..mid]
                lo = mid + 1;
            }
        }

        // Switch unknown[lo] controls door 'door'
        int sw = unknown[lo];
        switchDoor[sw] = door;
        switchPos[sw] = 1 - testVal; // testVal closes it, so correct = opposite
        determined[sw] = true;

        delete[] S;
    }

    int *S = new int[N], *D = new int[N];
    for(int i = 0; i < N; i++){
        S[i] = switchPos[i];
        D[i] = switchDoor[i];
    }
    answer(S, D);
    delete[] S; delete[] D;
}

int main(){
    int N;
    cin >> N;
    exploreCave(N);
    return 0;
}

int tryCombination(int S[]){ return -1; }
void answer(int S[], int D[]){}
\end{lstlisting}

\end{document}