Find the Infinity Stone

Author: Speedster1010

Required Knowledge : Interactive, Implementation

Time Complexity : $\mathcal{O}(N)$

Editorialist : Speedster1010

Approach:

This problem might sound complex with all the “timelines” and “Infinity Stones,” but it’s actually about exploring a binary tree interactively. Each junction can branch left (L) or right (R), and one hidden junction contains the stone.

At every junction, we can ask TVA whether the stone lies in its left or right branch. TVA responds with:

$\bullet$ The next junction (or $-1$ if it doesn’t exist), and

$\bullet$ $YES$ if the stone is somewhere in that branch, $NO$ otherwise.

We start at junction $1$ and keep following whichever branch says $YES$. If both branches return $NO$, it means the stone is at the current junction.

The algorithm is simple:

$1.$ Begin at node $1$.

$2.$ Ask about the left branch — if $YES$, move there.

$3.$ Otherwise, ask about the right branch — if $YES$, move there.

$4.$ If both return $NO$, print the current node as the answer.

This guarantees the correct junction in at most $2 \cdot N$ queries, as we only explore each branch once.

Setter's Code:

#include <iostream>
#include <string>
#include <vector>
#include <utility>

using namespace std;

pair<int, string> ask(int junction, char direction) {
    cout << "? " << junction << " " << direction << endl;
    int next_junction;
    string response;
    cin >> next_junction >> response;
    return { next_junction, response };
}

void solve() {
    int n;
    cin >> n;

    int node = 1;

    while(true) {
        int next_junction;
        string response;

        auto result_left = ask(node, 'L');
        
        next_junction = result_left.first;
        response = result_left.second;

        if(response == "YES") {
            node = next_junction;
            continue;
        }
        
        auto result_right = ask(node, 'R');

        next_junction = result_right.first;
        response = result_right.second;

        if(response == "YES") {
            node = next_junction;
            continue;
        }

        cout << "! " << node << endl;
        break;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}