USACO 2026 First Contest Silver Division - Sliding Window Summation

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We are given a hidden binary array \(b_1,\dots,b_N\) and the parity array \(r_1,\dots,r_{N-K+1}\) where \(r_i = (b_i + b_{i+1} + \dots + b_{i+K-1}) \bmod 2.\)

A key observation is that two consecutive windows differ only at their endpoints, which implies \(r_i \oplus r_{i+1} = b_i \oplus b_{i+K}.\)

Therefore, indices with the same remainder modulo \(K\) are connected by XOR constraints: the indices \(j,, j+K,, j+2K,\dots\) form one independent chain. Once we choose the first bit in a chain, the rest are forced.

For a chain starting at position \(j\), let its length be \(t\). There are only two possible assignments for the chain: one starting with \(0\) and one starting with \(1\). We can simulate both by walking along the chain using the XOR differences derived from \(r_i \oplus r_{i+1}\), and count how many ones each assignment induces. Let \(v0[j]\) be the count if the first bit is \(0\) and \(v1[j]\) if the first bit is \(1\). Across all \(K\) chains, the total number of ones is the sum of selected \(v0[j]\) or \(v1[j]\) options.

If we want the minimum possible total, we would greedily pick \(\min(v0[j],,v1[j])\) for each chain; similarly, for the maximum total, we pick \(\max(v0[j],,v1[j])\). However, these choices must satisfy a global constraint from the first window: since the first window covers exactly one starting element from each chain, its parity implies that \(\((\text{XOR of first bits of all } K \text{ chains}) = r_1.\)\) After greedy choices, this XOR might be wrong. To fix it optimally, we flip exactly one chain’s choice. The cost of flipping chain \(j\) is \(|v1[j]-v0[j]|\), so we choose the chain with minimal such cost. Subtracting (for maximum) or adding (for minimum) this penalty enforces the correct parity while preserving optimality.

This yields the minimum and maximum numbers of ones consistent with the input. The solution runs in \(O(N)\) time per test case and satisfies the full constraints.

Source code

The source code for the solution in C++ can be seen below.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

using ll = long long;
const ll INF = (ll)4e18;

void solve() {
    int N, K;
    cin >> N >> K;

    string b_str;
    cin >> b_str;

    vector<int> r(N - K + 2);
    for (int i = 1; i <= N - K + 1; ++i) {
        r[i] = b_str[i - 1] - '0';
    }

    vector<ll> v0(K + 1), v1(K + 1);

    for (int j = 1; j <= K; ++j) {
        int curr = 0;
        int ones = 0;
        int total = 0;

        int idx = j;
        ones += curr;
        total++;

        while (idx + K <= N) {
            curr ^= (r[idx] ^ r[idx + 1]);
            ones += curr;
            total++;
            idx += K;
        }

        v0[j] = ones;
        v1[j] = total - ones;
    }

    ll min_sum = 0;
    int min_parity = 0;
    ll min_diff_val = INF;

    for (int j = 1; j <= K; ++j) {
        if (v1[j] < v0[j]) {
            min_sum += v1[j];
            min_parity ^= 1;
        } 
        else {
            min_sum += v0[j];
        }
        min_diff_val = min(min_diff_val, llabs(v1[j] - v0[j]));
    }

    if (min_parity != r[1]) {
        min_sum += min_diff_val;
    }

    ll max_sum = 0;
    int max_parity = 0;
    ll max_diff_val = INF;

    for (int j = 1; j <= K; ++j) {
        if (v1[j] > v0[j]) {
            max_sum += v1[j];
            max_parity ^= 1;
        } 
        else {
            max_sum += v0[j];
        }
        max_diff_val = min(max_diff_val, llabs(v1[j] - v0[j]));
    }

    if (max_parity != r[1]) {
        max_sum -= max_diff_val;
    }

    cout << min_sum << " " << max_sum << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}