APIO 2016 - Gap
Author: Andi Qu
We can find the minimum and maximum elements of in some range by
MinMax(l, r, &mn, &mx). This lets us "whittle down" the range
and reconstruct with .
We can then sweep throught and find the largest gap.
We don't necessarily need to reconstruct entirely to find the largest gap. Notice how if we know a lowerbound on the answer and the range of all , then we can simply query the range in blocks of size to find the answer. This works because the largest gap will always span at least two blocks.
So what is the lowerbound on the answer? If there are elements that span a range of size , then the lowerbound is by the pigeonhole principle. (This is a similar idea to the solution for IMO 2020 P6).
Our algorithm thus looks like:
- Find the range that spans in 1 query. This contributes to .
- Find (the lowerbound on the answer) from the formula above.
- Query the range in blocks of size . Since there are of these blocks and each is included in exactly 1 of these blocks, this contributes to .
This allows us to find the largest gap with .
#include "gap.h"#include <bits/stdc++.h>using namespace std;typedef long long ll;const ll MAXN = 1e18;ll a, j = 0;
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!