Ricehub
There are R rice fields at sorted positions x_1 < x_2 < < x_R along a line. A hub can be placed at any integer position. The cost of connecting field i to a hub at position h is |x_i - h|. Given budget B, find the max...
Problem Statement
Rendered from the "Problem Summary" section in the LaTeX write-up.
There are $R$ rice fields at sorted positions $x_1 < x_2 < \cdots < x_R$ along a line. A hub can be placed at any integer position. The cost of connecting field $i$ to a hub at position $h$ is $|x_i - h|$. Given budget $B$, find the maximum number of fields connectable to a single hub.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Key Observations
Lemma.
The optimal hub for a contiguous set of fields $\{x_l, \ldots, x_r\}$ is at the median $x_m$ where $m = \lfloor(l+r)/2\rfloor$.
Proof.
The sum of absolute deviations $\sum_{i=l}^{r} |x_i - h|$ is minimized when $h$ is the median of the set, a standard result.
Lemma.
The optimal set of fields is a contiguous subarray of the sorted positions.
Proof.
If two fields $x_a$ and $x_b$ with $x_a < x_b$ are connected, then every field between them has cost $\le \max(|x_a - h|, |x_b - h|)$, so including it cannot increase the cost.
Algorithm: Two Pointers with Prefix Sums
Use a sliding window $[l, r]$. For each right endpoint $r$, expand while the cost is within budget $B$, and shrink $l$ when it exceeds $B$. The cost for window $[l, r]$ with median at $m = \lfloor(l+r)/2\rfloor$: \[ \text{cost} = x_m(m - l + 1) - S_m + S_r - x_m(r - m) \] where $S_k = \sum_{i=0}^{k} x_i$ is the prefix sum (using appropriate indexing).
Complexity
Time: $O(R)$ with two pointers.
Space: $O(R)$.
Code
C++ solution used for this page.
#include <bits/stdc++.h>
using namespace std;
int besthub(int R, int L, int X[], long long B){
// X is sorted, 0-indexed
vector<long long> prefix(R + 1, 0);
for(int i = 0; i < R; i++){
prefix[i + 1] = prefix[i] + X[i];
}
// Cost of connecting fields [l..r] to median position X[m], m = (l+r)/2
auto cost = [&](int l, int r) -> long long {
int m = (l + r) / 2;
// Left part: X[m] * (m - l + 1) - sum(X[l..m])
long long leftCost = (long long)X[m] * (m - l + 1) - (prefix[m + 1] - prefix[l]);
// Right part: sum(X[m..r]) - X[m] * (r - m + 1)
long long rightCost = (prefix[r + 1] - prefix[m]) - (long long)X[m] * (r - m + 1);
return leftCost + rightCost;
};
int ans = 0;
int l = 0;
for(int r = 0; r < R; r++){
while(cost(l, r) > B){
l++;
}
ans = max(ans, r - l + 1);
}
return ans;
}
int main(){
int R, L;
long long B;
cin >> R >> L >> B;
int *X = new int[R];
for(int i = 0; i < R; i++) cin >> X[i];
cout << besthub(R, L, X, B) << "\n";
delete[] X;
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.