Find the Global Minimum by Queries
National Olympiad — National round (2017 season)
Submission name: findminimum.cpp
Problem summary
A hidden integer array changes by exactly ±1 between neighbors and has exactly K direction changes. Implement the official play(N,K) callback to return its global minimum while respecting the strongest 35-query limit.
Input
Grader callback long long play(long long N,int K); query(index) returns the hidden value. There is no contestant standard-input program.
Output
Return the minimum from play.
Constraints
3 ≤ N ≤ 10¹⁸; 1 ≤ K ≤ 30; values fit long long; strongest query budget 35; play may be called repeatedly.
Worked example
The official example hides this five-element array and returns 3; different valid query sequences are permitted.
Input
Hidden array: 6 5 4 3 4 Grader call: play(5,1)
Output
3
Solution analysis
- Query both endpoints. If an interval has endpoint values a,b and length d in edges, every interior value is at least the lower envelope of the two unit-slope cones. Its lowest possible point is x=left+(d+a−b)/2, with lower bound a−(x−left). Neighbor parity guarantees an integral intersection.
- Keep unresolved intervals in a priority queue ordered by this lower bound. Always query the interval capable of the smallest value, then split it at the queried point. Stop when the smallest remaining lower bound is no smaller than the smallest value already observed. Unit-slope intervals need no further query.
- For hidden 6,5,4,3,4 the endpoints give a=6,b=4,d=4. The next queried index is 3, whose value 3 attains the global lower bound. Thus the callback returns 3 after three calls, while the official illustrative transcript uses five linear queries. The best-bound strategy has the K+4 query bound, at most 34 for K≤30.
Why it works
The endpoint cones are valid lower bounds because each step can decrease a value by at most one. Their intersection minimizes their maximum, so querying there gives the strongest unresolved candidate. Pruning an interval whose lower bound is at least the best observed value cannot hide an improvement. For the query bound, an interior nonextreme answer splits an interval into two that each contain a direction change, with equal new lower bounds. Queries attaining the lower cone finish the global search. Queries attaining the upper cone discard a mountain interval; consecutive such discarded mountains require intervening turns and consume the same turn budget as a split. Charging splits and discarded mountains to distinct turns, with the two endpoint queries and at most two final cone confirmations, gives K+4 queries. Therefore the returned observed minimum is exact within the strongest budget.
Watch out. Submit a callback without main and include findminimum.h. Reset all state per play call. Endpoint values can be near long-long limits, so avoid adding them together. Prefer the smallest lower bound globally, not a depth-first recursive search.
Commented C++17 solution
Official grader callback, not a standard-input program. Compile this file with the provided findminimum.h and grader. The local tests supply a labeled mock query implementation.
#include"findminimum.h"
#include<algorithm>
#include<limits>
#include<queue>
#include<vector>
// Algorithm: Query both endpoints.
using namespace std;
struct Interval{
long long left,right,first,last,lower,middle;
bool operator<(const Interval&other)const{
return lower>other.lower;
}
};
long long play(long long n,int k){
(void)k;
long long first=query(0);
long long last=query(n-1);
long long best=min(first,last);
priority_queue<Interval>pending;
auto insert=[&](long long left,long long right,long long a,long long b){
long long distance=right-left;
long long middle=left+(distance+(a-b))/2;
if(middle==left||middle==right){
return;
}
long long decrease=middle-left;
long long lowest=numeric_limits<long long>::min();
long long lower=a<lowest+decrease?lowest:a-decrease;
pending.push({left,right,a,b,lower,middle});
};
insert(0,n-1,first,last);
while(!pending.empty()&&pending.top().lower<best){
Interval interval=pending.top();
pending.pop();
long long value=query(interval.middle);
best=min(best,value);
insert(interval.left,interval.middle,interval.first,value);
insert(interval.middle,interval.right,value,interval.last);
}
return best;
}