Radio Towers
Characterization A set S = \ s_1 < s_2 < < s_m\ [L,R] is mutually communicating with parameter D if and only if every consecutive pair (s_i, s_ i+1) can communicate. The ``only if'' direction is trivial. For ``if'': t...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
There are $N$ towers at positions $0, 1, \ldots, N{-}1$ with distinct heights $H[0], \ldots, H[N{-}1]$. Towers $i < j$ can communicate with parameter $D$ if there exists $k$ with $i < k < j$ and $H[k] \ge \max(H[i], H[j]) + D$.
Given queries $(L, R, D)$, find the maximum number of towers in $[L, R]$ such that every pair can communicate.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Characterization
Lemma.
lem:consec A set $S = \{s_1 < s_2 < \cdots < s_m\} \subseteq [L,R]$ is mutually communicating with parameter $D$ if and only if every consecutive pair $(s_i, s_{i+1})$ can communicate.
Proof.
The ``only if'' direction is trivial. For ``if'': take any $s_a < s_b$ in $S$. For each consecutive pair $(s_i, s_{i+1})$ there is a peak $p_i$ with $H[p_i] \ge \max(H[s_i], H[s_{i+1}]) + D$. Let $p^* = \arg\max_i H[p_i]$ among the peaks for pairs between $s_a$ and $s_b$. Then $H[p^*] \ge \max(H[s_a], H[s_b]) + D$ because the maximum among intermediate peaks dominates both endpoints.
By Lemma lem:consec, the problem reduces to: find the longest subsequence of $[L,R]$ such that between every two consecutive selected towers there is a peak exceeding both by at least $D$.
Greedy algorithm
Scan left to right. Greedily select a tower if:
There exists a peak of sufficient height between it and the previously selected tower, and
its height is low enough to be ``reachable'' from the next peak.
More precisely: maintain the last selected tower. For a candidate tower $i$, check (using a sparse table for range-max queries) whether $\max_{k \in (\mathrm{last}, i)} H[k] \ge \max(H[\mathrm{last}], H[i]) + D$. If so, select $i$. If not, and $H[i] < H[\mathrm{last}]$, replace the last selection with $i$ (a lower tower is strictly more flexible as a chain endpoint).
Correctness
Theorem.
The greedy algorithm produces an optimal set.
Proof (Proof sketch).
Suppose the greedy selects towers $g_1, g_2, \ldots, g_m$ and an optimal solution selects $o_1, o_2, \ldots, o_k$ with $k > m$. By an exchange argument, we can show $H[g_i] \le H[o_i]$ for all $i$: if the greedy tower is no taller, it is at least as good a ``continuation point.'' The greedy never misses a valid extension since it always holds the lowest feasible endpoint, so $k \le m$, a contradiction.
Complexity
Preprocessing: $O(N \log N)$ for the sparse table.
Per query: $O(R - L)$ --- each tower is visited once; range-max queries take $O(1)$.
Space: $O(N \log N)$.
For full marks, a more sophisticated approach using the Cartesian tree structure and offline/online segment-tree techniques can achieve $O(\log N)$ or $O(\sqrt{N} \log N)$ per query.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> H;
// Sparse table for range maximum queries
vector<vector<int>> sparse; // sparse[k][i] = index of max in [i, i+2^k-1]
int LOG;
void init(int _N, vector<int> _H) {
N = _N;
H = _H;
LOG = 1;
while ((1 << LOG) <= N) LOG++;
sparse.assign(LOG, vector<int>(N));
for (int i = 0; i < N; i++) sparse[0][i] = i;
for (int k = 1; k < LOG; k++)
for (int i = 0; i + (1 << k) <= N; i++) {
int a = sparse[k-1][i], b = sparse[k-1][i + (1 << (k-1))];
sparse[k][i] = (H[a] >= H[b]) ? a : b;
}
}
int range_max_idx(int l, int r) {
int k = __lg(r - l + 1);
int a = sparse[k][l], b = sparse[k][r - (1 << k) + 1];
return (H[a] >= H[b]) ? a : b;
}
int max_towers(int L, int R, int D) {
if (L == R) return 1;
// Greedy: find maximum set of towers in [L, R] such that between any two
// consecutive selected towers, there exists a peak >= max(H[selected]) + D.
// Strategy: select towers greedily as valleys.
// A tower can be selected if there's a high enough separator from the previous selection.
// Find the global maximum in [L, R]
int peak_idx = range_max_idx(L, R);
// Try selecting towers: scan and greedily pick
// Track the minimum height selected so far and ensure separators exist.
// Simple approach: for each tower, check if it can be part of the set.
// A tower at position i with height H[i] can be selected if:
// - There exists j in [last_selected+1, i-1] with H[j] >= H[i] + D
// AND H[j] >= H[last_selected] + D
int count = 0;
int last = -1; // index of last selected tower
for (int i = L; i <= R; i++) {
if (last == -1) {
// First selection: check if there's a peak to the right
// that's high enough (will be verified when selecting the second)
// For now, tentatively select
// Actually, we should select the lowest possible towers.
// Let's try: select if i is a local minimum in [L, R]
bool is_valley = true;
if (i > L && H[i] > H[i-1]) is_valley = false;
if (i < R && H[i] > H[i+1]) is_valley = false;
if (is_valley || i == L || i == R) {
// Check feasibility: is there a separator available?
// For the first one, just select tentatively
if (count == 0) {
last = i;
count = 1;
} else {
// Check separator between last and i
if (last + 1 <= i - 1) {
int mx = range_max_idx(last + 1, i - 1);
if (H[mx] >= H[last] + D && H[mx] >= H[i] + D) {
last = i;
count++;
} else if (H[i] < H[last]) {
// Replace last with i (lower is better)
last = i;
}
}
}
}
} else {
// Try to select i
if (i == last) continue;
if (last + 1 <= i - 1) {
int mx = range_max_idx(last + 1, i - 1);
if (H[mx] >= H[last] + D && H[mx] >= H[i] + D) {
last = i;
count++;
} else if (H[i] < H[last] && count == 1) {
// Replace: lower tower is better as starting point
last = i;
}
}
}
}
if (count == 0) count = 1; // at least one tower can be selected
return count;
}
int main() {
int n, q;
scanf("%d", &n);
vector<int> h(n);
for (int i = 0; i < n; i++) scanf("%d", &h[i]);
init(n, h);
scanf("%d", &q);
while (q--) {
int l, r, d;
scanf("%d %d %d", &l, &r, &d);
printf("%d\n", max_towers(l, r, d));
}
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.