APIO 2016 - Gap

Author: Andi Qu

Subtask 1

We can find the minimum and maximum elements of aa in some range [l,r][l, r] by simply querying MinMax(l, r, &mn, &mx). This lets us "whittle down" the range and reconstruct aa with MN+12M \leq \frac{N + 1}{2}.

We can then sweep throught aa and find the largest gap.

Subtask 2

We don't necessarily need to reconstruct aa entirely to find the largest gap. Notice how if we know a lowerbound xx on the answer and the range of all aia_i, then we can simply query the range in blocks of size x1x - 1 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 NN elements that span a range of size LL, then the lowerbound is L+N1N1\frac{L + N - 1}{N - 1} by the pigeonhole principle. (This is a similar idea to the α=1/2\alpha = 1/2 solution for IMO 2020 P6).

Our algorithm thus looks like:

  • Find the range that aa spans in 1 query. This contributes N+1N + 1 to MM.
  • Find xx (the lowerbound on the answer) from the formula above.
  • Query the range in blocks of size x1x - 1. Since there are N1N - 1 of these blocks and each aia_i is included in exactly 1 of these blocks, this contributes 2N12N - 1 to MM.

This allows us to find the largest gap with M3NM \leq 3N.


#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1e18;
ll a[100000], 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!