Prize
There are several prize types, numbered by value. Type 1 is the unique diamond. If there are k prizes of type t-1, then there are strictly more than k^2 prizes of type t. For a query on position i, the grader returns...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
There are several prize types, numbered by value. Type 1 is the unique diamond. If there are $k$ prizes of type $t-1$, then there are strictly more than $k^2$ prizes of type $t$.
For a query on position $i$, the grader returns two numbers:
$L_i$: how many boxes to the left contain a more expensive prize,
$R_i$: how many boxes to the right contain a more expensive prize.
We must find the unique position whose prize is the diamond.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Main Observation
Define \[ S_i = L_i + R_i. \] Then $S_i$ is exactly the number of prizes in the whole array that are more expensive than the prize in box $i$.
Therefore:
$S_i = 0$ if and only if box $i$ contains the diamond,
two boxes contain the same prize type if and only if they have the same value of $S$.
Lemma.
Let $i < j$ be two queried boxes with $S_i = S_j$. Then the number of boxes in the interval $(i, j)$ whose prizes are more expensive than the prizes in boxes $i$ and $j$ is exactly $L_j - L_i$.
Proof.
Both queries count prizes of the same set of more expensive types. The only difference between $L_j$ and $L_i$ comes from boxes between $i$ and $j$.
Binary-Search Style Exploration
We recursively split unresolved segments exactly as in ordinary binary search: query the midpoint, then continue on the left and right halves.
The key pruning rule is the following. Suppose a segment lies strictly between two already queried boxes $i < j$ with the same value $S_i = S_j = s$. If we have already queried exactly $L_j - L_i$ boxes between them whose $S$-value is smaller than $s$, then every box between $i$ and $j$ that is more expensive than type $s$ has already been identified. Hence any still-unqueried segment inside $(i, j)$ cannot contain the diamond and may be discarded.
So for each pending segment we first check whether some same-value pair around it already certifies that the segment is empty. If not, we query its midpoint. Whenever we see $S=0$, we have found the answer.
Why This Works Well
Because prize multiplicities grow quadratically from one type to the next, the number of distinct prize types is tiny. This means equal-$S$ boxes appear very quickly, and the pruning rule becomes effective after relatively few queries. This is the same idea as the official editorial's optimized solution.
Complexity
The official editorial states that this strategy can be implemented within the query limit, with at most 4759 queries. The local work per query is small because we only maintain queried positions grouped by their value $S$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
// Grader-provided function.
pair<int, int> ask(int i);
namespace {
vector<pair<int, int>> cached;
map<int, vector<int>> positions_by_sum;
pair<int, int> query(int idx) {
if (cached[idx].first != -1) {
return cached[idx];
}
pair<int, int> res = ask(idx);
cached[idx] = res;
int sum = res.first + res.second;
vector<int>& positions = positions_by_sum[sum];
positions.insert(lower_bound(positions.begin(), positions.end(), idx), idx);
return res;
}
int count_between(const vector<int>& positions, int left, int right) {
auto it_left = upper_bound(positions.begin(), positions.end(), left);
auto it_right = lower_bound(positions.begin(), positions.end(), right);
return int(it_right - it_left);
}
bool can_skip_segment(int left, int right) {
for (const auto& [sum, positions] : positions_by_sum) {
if (sum == 0) {
continue;
}
auto it_right = upper_bound(positions.begin(), positions.end(), right);
if (it_right == positions.end()) {
continue;
}
int outer_right = *it_right;
auto it_left = lower_bound(positions.begin(), positions.end(), left);
if (it_left == positions.begin()) {
continue;
}
--it_left;
int outer_left = *it_left;
const auto [left_a, left_b] = cached[outer_left];
const auto [right_a, right_b] = cached[outer_right];
(void)left_b;
(void)right_b;
int identified_more_expensive = 0;
for (const auto& [smaller_sum, smaller_positions] : positions_by_sum) {
if (smaller_sum >= sum) {
break;
}
identified_more_expensive += count_between(smaller_positions, outer_left, outer_right);
}
if (identified_more_expensive == right_a - left_a) {
return true;
}
}
return false;
}
} // namespace
int find_best(int n) {
cached.assign(n, {-1, -1});
positions_by_sum.clear();
vector<pair<int, int>> segments;
segments.push_back({0, n - 1});
while (!segments.empty()) {
auto [left, right] = segments.back();
segments.pop_back();
if (left > right) {
continue;
}
if (can_skip_segment(left, right)) {
continue;
}
int mid = left + (right - left) / 2;
auto [a, b] = query(mid);
if (a + b == 0) {
return mid;
}
segments.push_back({mid + 1, right});
segments.push_back({left, mid - 1});
}
return -1;
}
int main() {
// Grader handles interaction.
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.