Task: A Game with the Joker – Solution and Explanation

In this game the users try to find the hidden interval [L, R] that the Joker has chosen. The Joker gives a number N (where 5 ≤ N ≤ 1000) and keeps two numbers L and R secret (0 ≤ L ≤ R ≤ N−1).

The rules of the game

  • The user can ask a question by sending the Joker an array a₀, a₁, …, aₙ₋₁.
  • The Joker then returns, at random, either the minimum or the maximum of the elements in the segment [L, R].
  • The Joker accepts every answer (L', R') that satisfies: |L − L'| + |R − R'| ≤ 1.

The goal is to find (L', R') as precisely as possible using as few questions (query calls) as possible.


Go back to the text of the task: Joker, go back to the page with the Joker task .

The competition environment vs. a local simulation

In a competition system (e.g. on an online platform) the functions query() and answer() are already defined by the system — the contestant implements only:

void solve(int N);

The system then calls query(a) itself and checks the result of answer(L, R).

In a local environment (on your own computer) you have to make a simulation of the Joker yourself, i.e. implement the functions query() and answer() too, in order to test the solution.


The idea of the solution

Since the Joker returns the minimum or the maximum at random, it is not possible to know directly where the interval [L, R] is. However, by repeating several queries with different arrays and analysing the results, we can estimate in which part of the array the interval is.

There are several possible approaches:

  • Narrowing the range recursively (similar to binary search)
  • Stochastic testing – several repetitions for a more stable result
  • Narrowing iteratively without recursion (a deterministic approach)

An educational solution (a local simulation)

The following code implements a complete simulation: it includes generating the secret interval, the functions query(), answer() and the recursive function search_interval(), which gradually narrows the range until it finds a solution.

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

// --- Joker simulation (local version) ---
int L_secret, R_secret;

// The function query – returns, at random, the minimum or the maximum of the segment [L,R]
int query(vector<int> a) {
    vector<int> segment(a.begin() + L_secret, a.begin() + R_secret + 1);
    if (rand() % 2 == 0)
        return *min_element(segment.begin(), segment.end());
    else
        return *max_element(segment.begin(), segment.end());
}

// The function answer – checks whether the solution is correct
void answer(int L, int R) {
    int error = abs(L - L_secret) + abs(R - R_secret);
    cout << "Error: " << error << endl;
    if (error <= 1)
        cout << "✅ Correct!  (The secret interval is [" << L_secret << ", " << R_secret << "])\n";
    else
        cout << "❌ Wrong!    (The secret interval is [" << L_secret << ", " << R_secret << "])\n";
}

// --- Recursive search for the interval ---
pair<int, int> search_interval(int l, int r, int N) {
    if (r - l <= 1)
        return {l, r};

    int mid = (l + r) / 2;
    vector<int> a(N);
    iota(a.begin(), a.end(), 1);

    int leftScore = 0, rightScore = 0;
    for (int i = 0; i < 5; i++) {
        int res = query(a);
        if (res <= a[mid]) leftScore++;
        else rightScore++;
    }

    if (leftScore >= rightScore)
        return search_interval(l, mid, N);
    else
        return search_interval(mid, r, N);
}

// --- The main function solve (as in the competition environment) ---
void solve(int N) {
    pair<int, int> result = search_interval(0, N - 1, N);
    answer(result.first, result.second);
}

// --- A local main for testing ---
int main() {
    srand(time(0));
    int N;
    cout << "Enter N (5 ≤ N ≤ 1000): ";
    cin >> N;

    L_secret = rand() % N;
    R_secret = L_secret + rand() % (N - L_secret);

    cout << "(DEBUG) The secret interval: [" << L_secret << ", " << R_secret << "]\n";
    solve(N);
    return 0;
}

Advantage: easy to understand, visually educational code that shows how an interactive task is "emulated" locally.
Disadvantage: the algorithm is not efficient, because it uses a simple binary search, and the Joker's random answers affect the accuracy.

Note: in our test (40 runs, N = 200) this solution found an acceptable interval only once. It is useful for understanding the simulation, but for the real task use the advanced solution below (binary search with probes), which was correct in all 40 runs.

Another solution — a probabilistic approach

The following example shows a simpler framework used in competition solutions. The idea is to check the stability of a candidate by repeating several queries (whether the expected answer is obtained on average).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// This is a "stub" function — in the real system the function query(a) would be called
int send_query(const vector<int>& a) {
    return 0; // simulation
}

bool verify_candidate(int l, int r, int K) {
    int ok = 0;
    for (int t = 0; t < K; ++t) {
        vector<int> a;
        int res = send_query(a);
        if (false) ++ok; // placeholder
    }
    return ok * 2 > K;
}

int main() {
    vector<pair<int,int>> candidates;
    int K = 5;
    for (auto [l, r] : candidates) {
        if (verify_candidate(l, r, K)) {
            cout << "Candidate found: " << l << " " << r << "\n";
            break;
        }
    }
    return 0;
}

This solution shows the basic framework of a probabilistic search: it does not give the correct solution, but it explains how the logic of checking several candidates through repeated queries can be implemented.


Conclusion

This task is a typical example of an interactive problem — it needs a combination of logic, probability and careful planning of queries. For educational purposes, the simulation above lets the user see how the Joker "thinks" and learn how to develop a more efficient algorithm before submitting the solution on the official platform.

An advanced idea – binary search with multiple probes

In this part we explain a more advanced approach to solving the task "A game with the Joker". The idea is to combine binary search and repeating queries in order to reduce the effect of the Joker's random answers.

The idea of the algorithm

  • The Joker returns the MIN or the MAX, but we do not know which.
  • To reduce the effect of randomness, we repeat the same query several times (M times).
  • With specially built arrays a we can find out:
    • ➤ whether the whole segment is to the left of a given point (R ≤ k),
    • ➤ to the right of it (L > k),
    • ➤ or crosses it (L ≤ k < R).

This information lets us find L and R with binary search, with a small error.


The implementation of the algorithm

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

/*
   ============================================
   JOKER SIMULATION (for local testing)
   ============================================

   In a real interactive task the functions `query` and `answer`
   would be provided by the system (the judge),
   and the programmer implements only the function `solve(int N)`.

   Here we simulate them so that we can test the algorithm locally.
*/

// Secret interval (unknown to the player)
int L_secret, R_secret;

// query(a): returns, AT RANDOM, the minimum or the maximum of the segment [L_secret, R_secret]
int query(vector<int> a) {
    int mn = INT_MAX, mx = INT_MIN;
    for (int i = L_secret; i <= R_secret; ++i) {
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }
    // returns either the min or the max at random
    return (rand() % 2 == 0) ? mn : mx;
}

// answer(L, R): checks whether the answer is correct
void answer(int L, int R) {
    int error = abs(L - L_secret) + abs(R - R_secret);
    cout << "\nAnswer: (" << L << ", " << R << ")";
    if (error <= 1)
        cout << " ✅ Correct! (The real interval: [" << L_secret << ", " << R_secret << "])\n";
    else
        cout << " ❌ Wrong! (The real interval: [" << L_secret << ", " << R_secret << "])\n";
}

/*
   ============================================
   THE ALGORITHM – BINARY SEARCH WITH PROBES
   ============================================

   The idea:
   - The Joker returns the MIN or the MAX, but we do not know which.
   - To reduce the effect of randomness, we repeat the same query M times.
   - With specially built arrays "a" we find out:
        ➤ whether the whole segment is to the left of a given point (R ≤ k),
        ➤ to the right of it (L > k),
        ➤ or crosses it (L ≤ k < R).

   This information lets us find L and R with binary search
   with a small error.
*/

// The number of repetitions per query (increases the accuracy)
const int M = 25;

// A helper function – tests the position of the R boundary relative to the index k
int probe_R(int N, int k) {
    vector<int> a(N);
    for (int i = 0; i < N; ++i)
        a[i] = (i <= k ? 0 : 1); // 0 up to k, 1 after k

    int zeros = 0;
    for (int t = 0; t < M; ++t) {
        int res = query(a);
        if (res == 0) zeros++;
    }

    if (zeros == M) return +1;  // all 0 → the whole segment is on the left (R ≤ k)
    if (zeros == 0) return -1;  // all 1 → the segment is on the right (L > k)
    return 0;                   // mixed → the segment "crosses" k
}

// A helper function – tests the position of the L boundary relative to the index k
int probe_L(int N, int k) {
    vector<int> a(N);
    for (int i = 0; i < N; ++i)
        a[i] = (i >= k ? 0 : 1); // 0 from k upwards, 1 before it

    int zeros = 0;
    for (int t = 0; t < M; ++t) {
        int res = query(a);
        if (res == 0) zeros++;
    }

    if (zeros == M) return +1;   // all 0 → L ≥ k
    if (zeros == 0) return -1;   // all 1 → R < k
    return 0;                    // mixed → L < k ≤ R
}

// Finds R with binary search
int findR(int N) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        int p = probe_R(N, mid);
        if (p == +1) r = mid;    // the segment is on the left → R ≤ mid
        else l = mid + 1;        // the segment goes further right → R > mid
    }
    return l;
}

// Finds L with binary search
int findL(int N) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        int p = probe_L(N, mid);
        if (p == +1) l = mid;    // the segment is on the right → L ≥ mid
        else r = mid - 1;        // the segment starts further left → L < mid
    }
    return l;
}

/*
   ============================================
   THE FUNCTION TO IMPLEMENT (solve)
   ============================================

   - This would be the only function that the system (the judge)
     calls directly in the interactive task.
   - In this local test we simulate `query()` and `answer()`.
*/
void solve(int N) {
    cout << "\nStarting the search for the interval...\n";

    // first we look for R, then for L
    int R = findR(N);
    int L = findL(N);

    cout << "➡️  Found: L = " << L << ", R = " << R << endl;
    answer(L, R);
}

/*
   ============================================
   MAIN (local test)
   ============================================
   Here we set a random secret interval and call solve().
*/

int main() {
    srand(time(0));
    int N;

    cout << "Enter N (5 ≤ N ≤ 1000): ";
    cin >> N;

    // set a random secret interval [L_secret, R_secret]
    L_secret = rand() % N;
    R_secret = L_secret + rand() % (N - L_secret);

    cout << "(DEBUG) The secret interval: [" << L_secret << ", " << R_secret << "]\n";

    solve(N);
    return 0;
}

A sample run (the interval is random, so the numbers differ from run to run):

Enter N (5 ≤ N ≤ 1000): 200
(DEBUG) The secret interval: [61, 108]

Starting the search for the interval...
➡️  Found: L = 61, R = 108

Answer: (61, 108) ✅ Correct! (The real interval: [61, 108])

Explanation of the algorithm

Step Explanation
1. We make an array a with two values (0 and 1) — it is a "sensor" for left/right of a boundary.
2. The function query(a) returns the min or the max of the segment [L, R], but at random — that is why we repeat it several times (M) and look at the pattern of the results.
3. If all results are 0 → the whole segment is inside the zeros → R ≤ k.
4. If all results are 1 → the whole segment is on the right → L > k.
5. If there are both 0 and 1 → the segment "crosses" k → L ≤ k < R.
6. Binary search makes it possible to find R (where the zeros end) and L (where the zeros start) precisely.
7. At the end we call answer(L, R) — success if the error is ≤ 1.

Advantages of the approach

  • Robust — it does not depend on the randomness of a single query (repetitions reduce the noise). If the segment crosses k, all M answers are the same only with probability 2·(1/2)25.
  • Efficient — complexity O(log N × M) queries, which is very fast even for N ≤ 1000.
  • Clear logic — it uses a clean binary search over the indices.

The idea of the algorithm – binary search with repeated queries

This approach uses a combination of binary search and repeated queries to reduce the effect of the Joker's random answers (the Joker returns the min or the max as it likes).

  • The Joker returns the MIN or the MAX, but we do not know which.
  • To reduce the effect of randomness, the same query is repeated several times (M).
  • Specially built arrays a let us find out:
    • whether the segment is completely to the left of a point (R ≤ k),
    • completely to the right of it (L > k),
    • or crosses it (L ≤ k < R).

We use this information in a binary search to gradually narrow the range and find the boundaries L and R.

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

/*
   ============================================
   JOKER SIMULATION (for local testing)
   ============================================

   In a real interactive task the functions `query` and `answer`
   would be provided by the system (the judge),
   and the programmer implements only the function `solve(int N)`.

   Here we simulate them so that we can test the algorithm locally.
*/

// Secret interval (unknown to the player)
int L_secret, R_secret;

// query(a): returns, AT RANDOM, the minimum or the maximum of the segment [L_secret, R_secret]
int query(vector<int> a) {
    int mn = INT_MAX, mx = INT_MIN;
    for (int i = L_secret; i <= R_secret; ++i) {
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }
    // returns either the min or the max at random
    return (rand() % 2 == 0) ? mn : mx;
}

// answer(L, R): checks whether the answer is correct
void answer(int L, int R) {
    int error = abs(L - L_secret) + abs(R - R_secret);
    cout << "\nAnswer: (" << L << ", " << R << ")";
    if (error <= 1)
        cout << " ✅ Correct! (The real interval: [" << L_secret << ", " << R_secret << "])\n";
    else
        cout << " ❌ Wrong! (The real interval: [" << L_secret << ", " << R_secret << "])\n";
}

/*
   ============================================
   THE ALGORITHM – BINARY SEARCH WITH PROBES
   ============================================

   The idea:
   - The Joker returns the MIN or the MAX, but we do not know which.
   - To reduce the effect of randomness, we repeat the same query M times.
   - With specially built arrays "a" we find out:
        ➤ whether the whole segment is to the left of a given point (R ≤ k),
        ➤ to the right of it (L > k),
        ➤ or crosses it (L ≤ k < R).

   This information lets us find L and R with binary search
   with a small error.
*/

// The number of repetitions per query (increases the accuracy)
const int M = 25;

// A helper function – tests the position of the R boundary relative to the index k
int probe_R(int N, int k) {
    vector<int> a(N);
    for (int i = 0; i < N; ++i)
        a[i] = (i <= k ? 0 : 1); // 0 up to k, 1 after k

    int zeros = 0;
    for (int t = 0; t < M; ++t) {
        int res = query(a);
        if (res == 0) zeros++;
    }

    if (zeros == M) return +1;  // all 0 → the whole segment is on the left (R ≤ k)
    if (zeros == 0) return -1;  // all 1 → the segment is on the right (L > k)
    return 0;                   // mixed → the segment "crosses" k
}

// A helper function – tests the position of the L boundary relative to the index k
int probe_L(int N, int k) {
    vector<int> a(N);
    for (int i = 0; i < N; ++i)
        a[i] = (i >= k ? 0 : 1); // 0 from k upwards, 1 before it

    int zeros = 0;
    for (int t = 0; t < M; ++t) {
        int res = query(a);
        if (res == 0) zeros++;
    }

    if (zeros == M) return +1;   // all 0 → L ≥ k
    if (zeros == 0) return -1;   // all 1 → R < k
    return 0;                    // mixed → L < k ≤ R
}

// Finds R with binary search
int findR(int N) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        int p = probe_R(N, mid);
        if (p == +1) r = mid;    // the segment is on the left → R ≤ mid
        else l = mid + 1;        // the segment goes further right → R > mid
    }
    return l;
}

// Finds L with binary search
int findL(int N) {
    int l = 0, r = N - 1;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        int p = probe_L(N, mid);
        if (p == +1) l = mid;    // the segment is on the right → L ≥ mid
        else r = mid - 1;        // the segment starts further left → L < mid
    }
    return l;
}

/*
   ============================================
   THE FUNCTION TO IMPLEMENT (solve)
   ============================================

   - This would be the only function that the system (the judge)
     calls directly in the interactive task.
   - In this local test we simulate `query()` and `answer()`.
*/
void solve(int N) {
    cout << "\nStarting the search for the interval...\n";

    // first we look for R, then for L
    int R = findR(N);
    int L = findL(N);

    cout << "➡️  Found: L = " << L << ", R = " << R << endl;
    answer(L, R);
}

/*
   ============================================
   MAIN (local test)
   ============================================
   Here we set a random secret interval and call solve().
*/

int main() {
    srand(time(0));
    int N;

    cout << "Enter N (5 ≤ N ≤ 1000): ";
    cin >> N;

    // set a random secret interval [L_secret, R_secret]
    L_secret = rand() % N;
    R_secret = L_secret + rand() % (N - L_secret);

    cout << "(DEBUG) The secret interval: [" << L_secret << ", " << R_secret << "]\n";

    solve(N);
    return 0;
}

Explanation of the algorithm

Step Explanation
1. We make an array a with the values 0 and 1 — it serves as a "sensor" for the boundaries.
2. query(a) returns the min or the max at random, so we repeat it several times (M).
3. If all results are 0 → the whole segment is inside the zeros → R ≤ k.
4. If all are 1 → the segment is on the right → L > k.
5. If there are both 0 and 1 → the segment "crosses" k.
6. Binary search finds the points where the transition happens and finds L and R.
7. At the end answer(L, R) is called — correct if the error is ≤ 1.

Advantages of this approach

  • Robust — it reduces the effect of randomness by repeating queries.
  • Efficient — complexity O(log N × M), which is very fast for N ≤ 1000.
  • Didactically clear — it nicely shows the principle of binary search and of reducing noise.

A stochastic approach – the "probabilistic detective"

This approach does not use an explicit binary search, but relies on repeated random experiments to estimate statistically the position of the secret interval [L, R].

The idea is to generate several random arrays a and look at the results of the function query(a) — which returns the min or the max of the segment at random. If we look at enough results, we can conclude where the interval probably is.

Key ideas

  • Instead of narrowing systematically as in binary search, we use many random queries and analyse the distribution of the answers.
  • If the same minimum or maximum appears often, it suggests that the segment includes that position.
  • From the statistics per index we estimate the most likely boundaries L and R.
#include <bits/stdc++.h>
using namespace std;

// ============================================
// JOKER SIMULATION (as before)
// ============================================
int L_secret, R_secret;

int query(vector<int> a) {
    int mn = INT_MAX, mx = INT_MIN;
    for (int i = L_secret; i <= R_secret; ++i) {
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }
    return (rand() % 2 == 0) ? mn : mx;
}

void answer(int L, int R) {
    int error = abs(L - L_secret) + abs(R - R_secret);
    cout << "\nAnswer: (" << L << ", " << R << ")";
    if (error <= 1)
        cout << " ✅ Correct! (The real interval: [" << L_secret << ", " << R_secret << "])\n";
    else
        cout << " ❌ Wrong! (The real interval: [" << L_secret << ", " << R_secret << "])\n";
}

// ============================================
// THE STOCHASTIC APPROACH
// ============================================
// The idea: we watch which positions of the array most often give the extreme values.
// This gives us a statistical estimate of where the interval [L, R] is.

void solve(int N) {
    const int T = 300; // the number of experiments
    vector<int> score(N, 0);

    for (int t = 0; t < T; ++t) {
        vector<int> a(N);
        for (int i = 0; i < N; ++i)
            a[i] = rand() % 1000; // random values

        int res = query(a);
        // We record which positions have a value equal to the result
        for (int i = 0; i < N; ++i) {
            if (a[i] == res)
                score[i]++;  // increase the "probability of belonging to the segment"
        }
    }

    // We find the longest run of consecutive positions with a high score
    int threshold = *max_element(score.begin(), score.end()) * 0.7;
    int bestL = 0, bestR = -1, start = -1;

    for (int i = 0; i <= N; ++i) {
        if (i < N && score[i] >= threshold) {
            if (start == -1) start = i;      // a new run starts
        } else if (start != -1) {            // a run [start, i-1] has ended
            if (i - 1 - start > bestR - bestL) {
                bestL = start;
                bestR = i - 1;
            }
            start = -1;
        }
    }

    answer(bestL, bestR);
}

// ============================================
// MAIN (local testing)
// ============================================
int main() {
    srand(time(0));
    int N;
    cout << "Enter N (5 ≤ N ≤ 1000): ";
    cin >> N;

    L_secret = rand() % N;
    R_secret = L_secret + rand() % (N - L_secret);

    cout << "(DEBUG) The secret interval: [" << L_secret << ", " << R_secret << "]\n";
    solve(N);
    return 0;
}

Explanation of the approach

Step Explanation
1. Many random arrays are generated (T experiments).
2. For every array, the Joker returns the min or the max of the segment [L, R].
3. For the indices whose values are equal to the result, the counter score[i] is increased.
4. After many repetitions, the largest score values gather in the region [L, R].
5. We find the run of consecutive positions where score is above a threshold (e.g. 70% of the maximum).
6. We take that region as the estimate of the secret segment and pass it to answer().

✅ Advantages and disadvantages

  • Advantages: simple to implement, intuitive.
  • Disadvantages: it needs many queries (O(N × T)), it is less efficient for large N, and it is not reliable: the minimum or the maximum of the segment is a single position, so the scores do not really "fill" the whole interval – in our test (40 runs, N = 200) it found an acceptable interval only twice.

This approach is useful when we want to show a statistical way of reasoning — useful for educational purposes. For the real task, use binary search with probes.


Previous
​|<Interactive algorithms