USACO 2026 Third Contest Silver Division - Clash!

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

The important observation is that if Farmer John wants to maximize the number of win-condition cards played by time \(t\), his choices are essentially greedy.

Whenever at least one win-condition is in hand, the rules force the next played card to be a win-condition. Among all available win-condition cards, playing the cheapest one is always optimal, because it gives the same gain of one win while spending the least possible time.

If there is no win-condition in hand, Farmer John should similarly play the cheapest normal card, since the only purpose is to advance the draw queue and reveal new cards as quickly as possible.

Thus the whole process is deterministic if we always choose the cheapest allowed card.

Simulating the Process

Maintain two min-priority queues for the current hand: one for win-condition cards, one for normal cards.

The remaining cards are kept in the draw queue. When a card with cost \(a_i\) is played, the earliest possible playing time increases by exactly \(a_i\). Then the front card of the draw queue enters the hand, while the played card goes to the back of the queue. We record the time whenever the played card is a win-condition.

Why a Cycle Appears

After some initial steps, the configuration starts repeating periodically. The hand has size \(H\), while the queue has size \(N-H\). After playing one card, that card moves to the back of the queue. Once the process has stabilized, the same sequence of choices repeats after \(L=N-H+1\) plays. It is enough to simulate a safe prefix of \(2N\) plays. After that, simulate one more block of \(L\) plays and record the following: the total time of one cycle, how many win-condition cards are played in one cycle, the relative times inside the cycle when those wins occur.

For a query time \(t\): if \(t\) lies inside the simulated prefix, binary search the recorded win times. Otherwise, subtract the prefix time. Let the cycle cost be \(T\) and the number of wins per cycle be \(W\). We can skip \(\lfloor t/T\rfloor\) full cycles at once, gaining that many multiples of \(W\) wins. For the remaining time, binary search the win times inside one cycle.

The simulation performs \(O(N)\) card plays, each using priority queues, so preprocessing takes \(O(N\log N)\) time and \(O(N)\) memory. Each query is answered with a constant number of binary searches, hence in \(O(\log N)\) time. Therefore the total complexity is \(O((N+Q)\log N)\).

Source code

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

#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>

using namespace std;

const int MAX_N = 200000;

long long cost[MAX_N + 1];
bool is_win[MAX_N + 1];

priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> win_cards;
priority_queue<pair<long long, int>,vector<pair<long long, int>>, greater<pair<long long, int>>> normal_cards;

deque<int> draw_queue;

int play_card(long long &current_time) {
    int card;

    if (!win_cards.empty()) {
        card = win_cards.top().second;
        win_cards.pop();
    }
    else {
        card = normal_cards.top().second;
        normal_cards.pop();
    }

    current_time += cost[card];

    int new_card = draw_queue.front();
    draw_queue.pop_front();

    if (is_win[new_card]) {
        win_cards.push({cost[new_card], new_card});
    }
    else {
        normal_cards.push({cost[new_card], new_card});
    }

    draw_queue.push_back(card);

    return card;
}

void solve() {
    int n, h;
    cin >> n >> h;

    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
        is_win[i] = false;
    }

    int k;
    cin >> k;

    for (int i = 0; i < k; i++) {
        int card;
        cin >> card;

        is_win[card] = true;
    }

    while (!win_cards.empty()) {
        win_cards.pop();
    }

    while (!normal_cards.empty()) {
        normal_cards.pop();
    }

    draw_queue.clear();

    for (int i = 1; i <= h; i++) {
        if (is_win[i]) {
            win_cards.push({cost[i], i});
        }
        else {
            normal_cards.push({cost[i], i});
        }
    }

    for (int i = h + 1; i <= n; i++) {
        draw_queue.push_back(i);
    }

    int cycle_length = n - h + 1;
    int warmup = 2 * n;

    long long current_time = 0;

    vector<long long> first_win_times;

    for (int i = 0; i < warmup; i++) {
        int card = play_card(current_time);

        if (is_win[card]) {
            first_win_times.push_back(current_time);
        }
    }

    long long warmup_time = current_time;
    long long wins_before_cycle = first_win_times.size();

    vector<long long> cycle_win_times;

    for (int i = 0; i < cycle_length; i++) {
        int card = play_card(current_time);

        if (is_win[card]) {
            cycle_win_times.push_back(current_time - warmup_time);
        }
    }

    long long cycle_cost = current_time - warmup_time;
    long long wins_per_cycle = cycle_win_times.size();

    int q;
    cin >> q;

    while (q--) {
        long long t;
        cin >> t;

        if (t <= warmup_time) {
            long long answer = upper_bound(first_win_times.begin(), first_win_times.end(), t) - first_win_times.begin();
            cout << answer << "\n";
            continue;
        }

        long long remaining = t - warmup_time;
        long long full_cycles = remaining / cycle_cost;
        long long answer = wins_before_cycle + full_cycles * wins_per_cycle;

        remaining %= cycle_cost;

        answer += upper_bound(cycle_win_times.begin(), cycle_win_times.end(), remaining)- cycle_win_times.begin();

        cout << answer << "\n";
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;

    while (t--) {
        solve();
    }

    return 0;
}