USACO 2026 Second Contest Silver Division - Farmer John Loves Rotations#
Problem link: here
Solution Author: Stefan Dascalescu
Problem Solution#
Think of the array as circular. If the favorite index is \(j\), then after several cyclic shifts Farmer John has seen exactly the values located at the positions that the fixed index \(j\) has visited. Therefore, the problem is equivalent to:
\(\textbf{Starting from position \(j\) on a circle, move left or right by one step each time, and visit at least one occurrence of every distinct value. Minimize the number of moves.}\)
Duplicate the array, obtaining positions \(0,\ldots,2N-1\), so every circular interval of length at most \(N\) becomes an ordinary interval.
Smallest Valid Intervals#
For every left endpoint \(l\in[0,N-1]\), let \(r_l\) be the smallest position such that the interval \([l,r_l]\) contains every distinct value. All \(r_l\) can be found in \(O(N)\) with the standard two-pointer method: extend the right endpoint until every value is present, record it, then remove the old left endpoint. Now consider any starting position \(x\) lying inside a valid interval \([l,r]\). To visit the entire interval, we have only two useful possibilities:
- go first to \(l\), then traverse to \(r\), costing $(x-l)+(r-l)=x+r-2l $;
- go first to \(r\), then traverse to \(l\), costing $ (r-x)+(r-l)=2r-l-x $.
Thus the best cost contributed by \([l,r]\) is \(\min(x+r-2l,\;2r-l-x).\) The first expression is better on the left half of the interval, and the second on the right half.
Computing All Starting Positions#
We must take the minimum over all valid intervals for every \(x\). For the left half, each interval contributes \(x+(r-2l).\) While sweeping \(x\) from left to right, maintain in a min-priority queue all intervals whose left half currently contains \(x\). The heap stores the constant \(r-2l\), so the best answer of this form is obtained immediately. Similarly, on the right half each interval contributes \((2r-l)-x.\)
Create an event when an interval's right half begins, insert the constant \(2r-l\) into another min-priority queue, and remove intervals after their right endpoint is passed.
There is also the case where the whole valid interval lies on only one side of \(x\). Then no turn is necessary: we simply walk from \(x\) to the farther endpoint. The implementation handles this with another linear sweep over the intervals whose right endpoint is already reached.
Because the array was duplicated, position \(i\) in the original circle may correspond to either \(i\) or \(i+N\). The answer for index \(i\) is therefore the minimum value computed for these two positions.
The two-pointer computation is \(O(N)\). Each interval is inserted into and removed from a priority queue only a constant number of times, giving total complexity \(O(N\log N)\) and memory usage \(O(N)\).
Source code#
The source code for the solution in C++ can be seen below.
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
const int MAX_N = 500000;
const long long INF = (1LL << 60);
int a[2 * MAX_N + 5];
int frequency[MAX_N + 5];
int right_end[MAX_N + 5];
long long plus_answer[2 * MAX_N + 5];
long long minus_answer[2 * MAX_N + 5];
long long extended_answer[2 * MAX_N + 5];
struct Event {
int start;
int end;
long long value;
};
vector<Event> minus_events;
void solve() {
int n;
cin >> n;
set<int> distinct_values;
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i + n] = a[i];
distinct_values.insert(a[i]);
}
int needed = distinct_values.size();
int right = -1;
int have = 0;
for (int left = 0; left < n; left++) {
while (right + 1 < left + n && have < needed) {
right++;
frequency[a[right]]++;
if (frequency[a[right]] == 1) {
have++;
}
}
right_end[left] = right;
frequency[a[left]]--;
if (frequency[a[left]] == 0) {
have--;
}
}
for (int i = 0; i < 2 * n; i++) {
plus_answer[i] = INF;
minus_answer[i] = INF;
extended_answer[i] = INF;
}
priority_queue<pair<long long, int>,vector<pair<long long, int>>,greater<pair<long long, int>>> plus_heap;
for (int position = 0; position < 2 * n; position++) {
if (position < n) {
int left = position;
int right = right_end[left];
int middle = (left + right) / 2;
long long value = right - 2LL * left;
plus_heap.push({value, middle});
}
while (!plus_heap.empty() && plus_heap.top().second < position) {
plus_heap.pop();
}
if (!plus_heap.empty()) {
plus_answer[position] = position + plus_heap.top().first;
}
}
minus_events.clear();
for (int left = 0; left < n; left++) {
int right = right_end[left];
int middle = (left + right) / 2;
int start = middle + 1;
if (start <= right) {
Event event;
event.start = start;
event.end = right;
event.value = 2LL * right - left;
minus_events.push_back(event);
}
}
priority_queue<pair<long long, int>, vector<pair<long long, int>>,greater<pair<long long, int>>> minus_heap;
int event_index = 0;
for (int position = 0; position < 2 * n; position++) {
while (event_index < (int)minus_events.size() && minus_events[event_index].start == position) {
minus_heap.push({minus_events[event_index].value,minus_events[event_index].end});
event_index++;
}
while (!minus_heap.empty() && minus_heap.top().second < position) {
minus_heap.pop();
}
if (!minus_heap.empty()) {
minus_answer[position] = minus_heap.top().first - position;
}
}
int best_left = -1;
for (int position = 0; position < 2 * n; position++) {
while (best_left + 1 < n && right_end[best_left + 1] <= position) {
best_left++;
}
if (best_left != -1 && position <= best_left + n - 1) {
extended_answer[position] = position - best_left;
}
}
for (int i = 0; i < n; i++) {
long long answer = INF;
answer = min(answer, plus_answer[i]);
answer = min(answer, minus_answer[i]);
answer = min(answer, extended_answer[i]);
answer = min(answer, plus_answer[i + n]);
answer = min(answer, minus_answer[i + n]);
answer = min(answer, extended_answer[i + n]);
if (i > 0) {
cout << " ";
}
cout << answer;
}
cout << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
while (t--) {
solve();
}
return 0;
}