USACO 2026 Third Contest Bronze Division - Strange Function#

Problem link: here

Problem Solution#

Call a positive integer $\textit{clean}$ if all of its digits are $0$ or $1$, and $\textit{messy}$ otherwise. In this language $f$ acts as follows: a messy $x$ is sent to $\pi(x)$, where $\pi$ replaces every digit $d$ by $d\bmod 2$; a clean $x$ is sent to $x-1$. Since $\pi(x)$ is clean by construction, the whole process looks like $$ x \;\xrightarrow{\;\pi\;}\; \text{clean} \;\xrightarrow{\;-1\;}\; \text{maybe messy} \;\xrightarrow{\;\pi\;}\; \text{clean} \;\longrightarrow\; \cdots \;\longrightarrow\; 0, $$ so at most one cleaning step ever happens, and only at the very start; everything afterwards is a walk on clean numbers. The central observation is that this walk is a \textit{binary counter in disguise}, which yields a closed formula for the answer.

The Walk on Clean Numbers Is a Binary Counter#

Fix a clean $x$ with digits $b_1b_2\cdots b_n$, $b_i\in\{0,1\}$, and let $$ P=(b_1b_2\cdots b_n)2=\sum $$ be the value of the digit string read in }^{n}b_i\,2^{\,n-i$\emph{binary}$. (Leading zeros are harmless: they contribute $0$ to $P$.) We claim the state is fully described by $P$, and each unit decrease of $P$ costs one or two applications of $f$.

Case 1: $b_n=1$, i.e. $P$ is odd. Subtracting $1$ causes no borrow: the final $1$ turns into $0$, the other digits are untouched, so $x-1$ is again clean with string $b_1\cdots b_{n-1}0$, whose binary value is $P-1$. Cost: $\textbf{one}$ step. (If $P=1$ then $x=1$ and we land on $0$.)

Case 2: $b_n=0$, i.e. $P$ is even. Since $x>0$ ends in $0$, we have $x\ge 10$, so $P\ge 2$ and the string has a rightmost $1$, say at position $k$. Subtracting $1$ now borrows: each trailing $0$ (positions $k{+}1,\dots,n$) becomes $9$, the digit $b_k=1$ becomes $0$, and positions $1,\dots,k-1$ do not change. The result is messy, so the next step applies $\pi$: each $9$ is odd, hence becomes $1$; each $0$ stays $0$; the untouched prefix keeps its digits. After these two steps we hold the clean number with string $$ b_1\cdots b_{k-1}\,0\,\underbrace{1\cdots1}_{n-k\text{ ones}}, $$ whose binary value is $P-1$ --- because subtracting $1$ from the $\emph{binary}$ number $(b_1\cdots b_n)_2$ does exactly this: trailing zeros flip to ones, the rightmost one flips to zero. Cost: $\textbf{two}$ steps.

In both cases the process marches through $P, P-1, P-2, \dots, 1, 0$, and $x$ reaches $0$ exactly when $P$ reaches $0$.

Counting the Steps#

Starting from a clean number with binary value $P$, the number of steps is $$ \sum_{j=1}^{P} c(j),\qquad c(j)=\begin{cases}1,&j\text{ odd}\ 2,&j\text{ even}\end{cases} \;=\;\Big\lceil \tfrac P2\Big\rceil+2\Big\lfloor \tfrac P2\Big\rfloor \;=\;P+\Big\lfloor \tfrac P2\Big\rfloor, $$ since $1,\dots,P$ contains $\lceil P/2\rceil$ odd and $\lfloor P/2\rfloor$ even values. A messy input needs one extra cleaning step at the start, which lands on the clean number $\pi(x)$. Writing $b_i = d_i \bmod 2$ for the input digits $d_i$:

$$ \text{answer}=P+\Big\lfloor \tfrac P2\Big\rfloor+\big[x\text{ is messy}\big],\qquad P=\sum_{i} b_i\,2^{\,n-i}. $$ Check the samples. For $x=24680$ every digit is even, so $P=0$ and the answer is $1$. For $x=210$ the parity string is $010$, so $P=2$, $\lfloor P/2\rfloor=1$, and the answer is $2+1+1=4$, matching $210\to10\to9\to1\to0$.

Computing Everything Modulo $10^9+7$#

$P$ may have up to $10^6$ bits, so all arithmetic is done modulo $M=10^9+7$. The residue $P\bmod M$ comes from Horner's scheme over the parity bits: $P \gets (2P+b_i)\bmod M$.

The subtle point is $\lfloor P/2\rfloor$: it is $\emph{not}$ determined by $P\bmod M$, so it cannot be recovered by halving that residue. Instead, note that $\lfloor P/2\rfloor$ is exactly the binary value of the parity string with the last bit dropped, i.e. $\sum_{i \lt n} b_i, 2^{\,n-1-i}$. The reference code therefore keeps a second accumulator fed with $b_1,\dots,b_{n-1}$ only, which produces precisely this quantity modulo $M$. (Alternatively, one may track $P\bmod 2M$, which fits in a 64-bit integer, and halve it; the two-accumulator scan is simpler.) Whether $x$ is messy is detected in the same single pass, by checking that every digit is $0$ or $1$.

One harmless edge case: a messy $x$ whose digits are all even has $P=0$; the formula correctly outputs $1$, since $\pi(x)=0$ in a single step.

Each test is solved by one linear scan of the digits of $x$: $O(n)$ time and $O(1)$ extra memory per test. Since the total number of input digits is at most $10^6$, the entire run is $O(10^6)$ --- proportional to the input size, hence optimal.

Source code#

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

#include <iostream>
#include <string>

using namespace std;

const long long MOD = 1000000007;

void solve() {
    string x;
    cin >> x;

    bool already_binary = true;

    for (int i = 0; i < (int)x.size(); i++) {
        if (x[i] != '0' && x[i] != '1') {
            already_binary = false;
        }
    }

    long long value = 0;
    long long half_value = 0;

    for (int i = 0; i < (int)x.size(); i++) {
        int digit = (x[i] - '0') % 2;

        value = (value * 2 + digit) % MOD;

        if (i + 1 < (int)x.size()) {
            half_value = (half_value * 2 + digit) % MOD;
        }
    }

    long long answer = value + half_value;

    if (!already_binary) {
        answer++;
    }

    answer %= MOD;

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

int main() {

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

    int t;
    cin >> t;

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

    return 0;
}

USACO 2026 Third Contest Bronze Division - Strange Function#

Problem Solution#

The Walk on Clean Numbers Is a Binary Counter#

Counting the Steps#

Computing Everything Modulo \(10^9+7\)#

Source code#