USACO 2026 Second Contest Silver Division - Cow-libi 2

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Represent Farmer John by \(0\) and Farmer Nhoj by \(1\). For every cow, consider its two answers as a directed edge: the left claim is the starting vertex and the right claim is the ending vertex. Thus every cow becomes one of the four edge types \(JJ\), \(JN\), \(NJ\), or \(NN\).

The goal is to arrange all cows in a circle. If cow \(a\) is immediately followed by cow \(b\), then \(a\)'s right claim and \(b\)'s left claim must refer consistently to the same owner. Therefore, the cows must form an \textbf{Eulerian cycle} in this graph with only two vertices, \(J\) and \(N\): every cow is an edge, and every edge must be used exactly once.

For an Eulerian cycle to exist, the following conditions are necessary and sufficient here:

• The number of \(JN\) edges must equal the number of \(NJ\) edges. This is exactly the condition that both vertices have equal indegree and outdegree.
• If there are no \(JN\) or \(NJ\) edges, then \(JJ\) and \(NN\) edges cannot both exist, since they would form two disconnected components.

There is one additional condition coming from truth and lies. Once the circular order is fixed, choose the owner of the first cow. Moving around the circle, the owner's value changes exactly when the current cow claims that its right neighbour is \(N\). Hence after one full cycle we return to the starting owner only if the total number of right claims equal to \(N\) is even.

So the answer is \(\texttt{YES}\) exactly when all three conditions hold.

Construction

When a construction is required, build an Eulerian cycle of the two-vertex multigraph using the standard stack-based Euler-tour algorithm. The resulting edge order is the required circular order of the cows.

To determine the owners, start the first cow as John. Traverse the Eulerian cycle in order. If the current cow's right claim is \(J\), the next cow keeps the same owner; if it is \(N\), the owner switches between John and Nhoj. The parity condition guarantees that after the last cow this assignment closes consistently around the circle.

Each cow becomes one edge and is processed a constant number of times. Therefore each test case runs in \(O(N)\) time and uses \(O(N)\) memory. Since the total \(N\) over all test cases is at most \(5\cdot 10^5\), this easily fits the limits.

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;

const int MAX_N = 100000;

string left_claim;
string right_claim;

vector<int> edges[2];
int next_edge[2];

vector<int> cow_order;

int get_value(char c) {
    if (c == 'J') {
        return 0;
    }

    return 1;
}

void solve(int construction) {
    int n;
    cin >> n;

    cin >> left_claim;
    cin >> right_claim;

    edges[0].clear();
    edges[1].clear();
    cow_order.clear();

    int count_jj = 0;
    int count_jn = 0;
    int count_nj = 0;
    int count_nn = 0;

    int right_n_count = 0;

    for (int i = 0; i < n; i++) {
        int left = get_value(left_claim[i]);
        int right = get_value(right_claim[i]);

        edges[left].push_back(i);

        if (left == 0 && right == 0) {
            count_jj++;
        }
        else if (left == 0 && right == 1) {
            count_jn++;
        }
        else if (left == 1 && right == 0) {
            count_nj++;
        }
        else {
            count_nn++;
        }

        if (right == 1) {
            right_n_count++;
        }
    }

    bool possible = true;

    if (count_jn != count_nj) {
        possible = false;
    }

    if (count_jn == 0 && count_nj == 0) {
        if (count_jj > 0 && count_nn > 0) {
            possible = false;
        }
    }

    if (right_n_count % 2 == 1) {
        possible = false;
    }

    if (!possible) {
        cout << "NO\n";
        return;
    }

    cout << "YES\n";

    if (construction == 0) {
        return;
    }

    int start;

    if (!edges[0].empty()) {
        start = 0;
    }
    else {
        start = 1;
    }

    next_edge[0] = 0;
    next_edge[1] = 0;

    vector<int> vertex_stack;
    vector<int> edge_stack;

    vertex_stack.push_back(start);
    edge_stack.push_back(-1);

    while (!vertex_stack.empty()) {
        int vertex = vertex_stack.back();

        if (next_edge[vertex] < (int)edges[vertex].size()) {
            int cow = edges[vertex][next_edge[vertex]];
            next_edge[vertex]++;

            int next_vertex = get_value(right_claim[cow]);

            vertex_stack.push_back(next_vertex);
            edge_stack.push_back(cow);
        }
        else {
            int cow = edge_stack.back();

            vertex_stack.pop_back();
            edge_stack.pop_back();

            if (cow != -1) {
                cow_order.push_back(cow);
            }
        }
    }

    reverse(cow_order.begin(), cow_order.end());

    for (int i = 0; i < n; i++) {
        if (i > 0) {
            cout << " ";
        }

        cout << cow_order[i] + 1;
    }

    cout << "\n";

    string owners;

    int current_owner = 0;

    for (int i = 0; i < n; i++) {
        int cow = cow_order[i];

        if (current_owner == 0) {
            owners += 'J';
        }
        else {
            owners += 'N';
        }

        int right = get_value(right_claim[cow]);
        current_owner ^= right;
    }

    cout << owners << "\n";
}

int main() {

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

    int t, construction;
    cin >> t >> construction;

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

    return 0;
}