USACO 2026 Cow Splits: Bitmasks and Square Subsequences

Cow Splits is a good bridge from Bronze implementation to early Silver reasoning. The phrase "split" can make students think about contiguous substrings, but the useful idea here is selecting positions to form subsequences.

Subsequence versus substring

A substring is one continuous block. A subsequence keeps the original order but may skip positions. That distinction matters because a selected group of characters can come from scattered positions.

S = C O C O W O W O
mask selects positions 0, 1, 2, 3
selected subsequence = C O C O

The selected string COCO is square because the first half equals the second half: CO + CO.

Why bitmasks fit

When the string is small enough, an integer mask can represent a subset of positions. If bit i is on, include position i. This makes the search systematic instead of random.

for mask from 1 to (1 << n) - 1:
    build selected characters
    build remaining characters
    test whether both are square

Square string test

A string is square when it has even length and its two halves match.

boolean isSquare(String s)
{
    if (s.length() % 2 != 0) return false;
    int mid = s.length() / 2;
    return s.substring(0, mid).equals(s.substring(mid));
}

Common mistakes

• Checking only contiguous substrings instead of selected subsequences.
• Forgetting that a square string must have even length.
• Building the selected characters out of order.
• Trying bitmask search when n is too large for 2^n.

Practice prompt

For S = COCOWOWO, find one mask that creates COCO and one remaining subsequence that is also square. Then write the selected position list.