2023 US Open · Bronze
← Back to 2023 US Open · Official results page
Three Bronze problems, 5 hours combined. B1 is a sweet counting exercise on a string with wildcards, B2 is a greedy-construction problem disguised as grammar parsing, and B3 is the trickiest of the set — a circular "rotate then shift" dance that needs you to notice it's really a permutation raised to a power.
B1 · FEB
Official statement (cpid=1323)
Statement (paraphrase)
You're given a length-N string over {B, E, F}. The 'F' characters are
wildcards — each must be filled with either B or E. The "excitement level" of a fully
resolved string is the number of indices i where the i-th and (i+1)-th
characters are equal. Output every distinct excitement level that some assignment of
the F's can produce, in increasing order.
Constraints
- 1 ≤ N ≤ 2·10⁵
- Subtasks: N ≤ 10 (brute force) · full
- Time limit: 2 s, memory: 256 MB
Key idea
Split the string into maximal "F-runs" bounded by non-F characters (or the string ends).
Each run contributes independently: a run of length L between fixed left and right
characters can produce any excitement contribution in some contiguous interval
[lo, hi] with the same parity. Sum the per-run intervals (Minkowski sum of
intervals with parity = arithmetic-progression union) plus the fixed contribution from
adjacent non-F pairs. Output every value in the resulting set.
Complexity
O(N) preprocessing of runs + O(N) to enumerate reachable excitement levels (bounded by N).
Reference C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N; string s;
cin >> N >> s;
// Fixed contribution from positions where both neighbors are non-F.
int base = 0;
for (int i = 0; i + 1 < N; i++)
if (s[i] != 'F' && s[i + 1] != 'F' && s[i] == s[i + 1]) base++;
// For each maximal F-run, determine [lo,hi] of equal-adjacent pairs it can contribute,
// considering its left/right anchor (or string boundary).
// dp[k] = set of achievable totals after processing runs; represented as a bitset.
vector<char> reach(N + 1, 0);
reach[base] = 1;
int i = 0;
while (i < N) {
if (s[i] != 'F') { i++; continue; }
int j = i;
while (j < N && s[j] == 'F') j++;
int L = j - i;
char left = (i > 0) ? s[i - 1] : '?';
char right = (j < N) ? s[j] : '?';
// Internal adjacent pairs inside the F-run: L-1 of them, each can be 0 or 1
// (we can always make adjacent characters equal or unequal by choosing freely)
// but the boundary pairs (with left/right anchors) cost 1 each if matched.
// Achievable extra contribution: any value in [0, L-1 + matchableBoundary]
// with same parity as max — actually any integer in [0, max] works for L >= 1.
int maxAdd = (L - 1) + (left != '?') + (right != '?');
// Try every add in [0, maxAdd]; union into reach[].
vector<char> next(N + 1, 0);
for (int v = 0; v <= N; v++) if (reach[v])
for (int add = 0; add <= maxAdd && v + add <= N; add++)
next[v + add] = 1;
reach = next;
i = j;
}
vector<int> out;
for (int v = 0; v <= N; v++) if (reach[v]) out.push_back(v);
cout << out.size() << "\n";
for (int v : out) cout << v << "\n";
}
Pitfalls
- String boundaries change parity: a leading or trailing F-run has only one anchor, so its max contribution is L−1 + 1, not L+1.
- The "every value in [0, maxAdd] is reachable" claim is the key insight — convince yourself with small L=1,2,3 cases before trusting it.
- Sort the output. Bessie problems love asking for sorted distinct values.
B2 · Moo Language
Official statement (cpid=1324)
Statement (paraphrase)
You have a word bank: N words tagged as noun / transitive-verb / intransitive-verb / conjunction, plus C commas and P periods. Build a sequence of valid sentences using each word at most once that maximizes the total word count. Sentences are either noun + intransitive-verb or noun + transitive-verb + noun (, noun)*. Two sentences can be joined by a conjunction; each sentence ends in a period.
Constraints
- 1 ≤ T ≤ 100, 1 ≤ N ≤ 1000, sum bounded
- Subtasks: N ≤ 10 · N ≤ 100 · full
- Time limit: 2 s, memory: 256 MB
Key idea
Greedy + try-all on the count of "transitive" sentences. Let nouns = n, transitive verbs = tv, intransitive verbs = iv. Each intransitive sentence eats 1 noun + 1 iv (2 words). Each transitive sentence eats 1 noun + 1 tv + at least 1 more noun (≥ 3 words), and extra nouns appended via commas (capped by C across all transitive sentences) each add 1 word. Periods cap total sentence count; conjunctions glue pairs of sentences (no extra periods but +1 word per conjunction). Enumerate the number of transitive sentences t ∈ [0, min(tv, P, ⌊n/2⌋)], then greedily fill intransitive sentences and extra-noun commas.
Complexity
O(N) per test case after sorting words by type. With N ≤ 1000, even O(N²) brute over the parameter range fits well under 2 s.
Reference C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T; cin >> T;
while (T--) {
int N, C, P; cin >> N >> C >> P;
vector<string> nouns, tv, iv, conj;
for (int i = 0; i < N; i++) {
string w, t; cin >> w >> t;
if (t == "noun") nouns.push_back(w);
else if (t == "transitive-verb") tv.push_back(w);
else if (t == "intransitive-verb") iv.push_back(w);
else conj.push_back(w);
}
int n = nouns.size(), Tv = tv.size(), Iv = iv.size(), Cn = conj.size();
int best = 0;
// Try each split: i intransitive sentences, j transitive sentences.
// i + j <= P + (uses-of-conjunction). With k conjunctions, sentences capped by 2*(P + k)? Actually
// each period ends one "sentence block" (chain), and a block has 1 or 2 sentences (joined by 1 conj).
// So total sentences S satisfies blocks B = (S + #conjUsed)/(?) — simpler bound: S <= 2*P, and
// #conjUsed = S - B where B <= P. Constraint: S <= 2P, conjUsed = max(0, S - P), conjUsed <= Cn.
for (int i = 0; i <= Iv; i++) {
for (int j = 0; j <= Tv; j++) {
if (i + j == 0) continue;
int S = i + j;
int needConj = max(0, S - P);
if (needConj > Cn) continue;
int nounsNeeded = i + 2 * j; // intransitive: 1 noun; transitive: at least 2 nouns
if (nounsNeeded > n) continue;
int extraNouns = min(n - nounsNeeded, (j == 0 ? 0 : C)); // commas only inside transitive sentences
int words = 2 * i + 3 * j + extraNouns + needConj;
best = max(best, words);
}
}
cout << best << "\n";
// Full credit also requires printing the actual constructed paragraph; omitted for brevity.
}
}
Pitfalls
- Commas can only appear inside a transitive sentence (after the second noun). If there are no transitive sentences, C is useless.
- Each conjunction joins exactly two sentences into one "block" terminated by one period — so P caps the number of blocks, not the number of sentences.
- The problem also asks for the actual paragraph as output, not just the count — full solution needs reconstruction.
B3 · Rotate and Shift
Official statement (cpid=1325)
Statement (paraphrase)
N cows stand at positions 0..N−1 around a circle. K "active" positions A₀ < A₁ < … < A_{K−1} are given. Each minute the cow at each active position A_i moves to position A_{(i+1) mod K} (a K-cycle rotation among active slots), then every position is incremented by 1 modulo N (shift). After T minutes, output where each cow originally at position i ends up.
Constraints
- 1 ≤ N ≤ 2·10⁵, 1 ≤ K ≤ N, 1 ≤ T ≤ 10⁹
- Subtasks: N ≤ 1000 and T ≤ 10000 · full
- Time limit: 4 s (doubled), memory: 256 MB
Key idea
One "minute" is a fixed permutation P on N elements: rotate active slots, then add 1 modulo N to every index. We need P^T. Use binary exponentiation on permutations: O(N log T). Alternative cycle decomposition: find every cycle of P, then advance each cow by T mod (cycle length).
Complexity
O(N log T) with binary exponentiation, or O(N) with cycle decomposition (preferred — T ≤ 10⁹ means log T ≈ 30, but cycle decomposition needs no extra log factor).
Reference C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long N, K, T;
cin >> N >> K >> T;
vector<long long> A(K);
for (auto &x : A) cin >> x;
// Build permutation P: cow at position p moves to P[p].
// Step 1 (rotate active): A[i] -> A[(i+1)%K]. Non-active positions unchanged.
// Step 2 (shift): every position +1 mod N.
vector<long long> perm(N);
for (long long p = 0; p < N; p++) perm[p] = (p + 1) % N;
// Override active slots: cow at A[i] first moves to A[(i+1)%K] then shifts by +1.
for (long long i = 0; i < K; i++)
perm[A[i]] = (A[(i + 1) % K] + 1) % N;
// Cycle decomposition: for each cow, find its position after T steps.
vector<long long> ans(N, -1);
vector<char> seen(N, 0);
for (long long s = 0; s < N; s++) {
if (seen[s]) continue;
// Walk the cycle from s.
vector<long long> cyc;
long long u = s;
while (!seen[u]) { seen[u] = 1; cyc.push_back(u); u = perm[u]; }
long long L = cyc.size();
long long shift = T % L;
for (long long k = 0; k < L; k++)
ans[cyc[k]] = cyc[(k + shift) % L];
}
// ans[p] = position cow originally at p ends up. Problem asks: print cow at each
// final position. Build inverse.
vector<long long> out(N);
for (long long p = 0; p < N; p++) out[ans[p]] = p;
for (long long p = 0; p < N; p++) cout << out[p] << " \n"[p + 1 == N];
}
Pitfalls
- The "rotate then shift" order matters — many solutions invert the steps and get a different permutation. Re-read the statement.
- T can be 10⁹, so any O(N · T) simulation TLEs. Only the cycle / exponentiation approach scales.
- Final output: the problem asks for the label of the cow at each final position, not the final position of each labelled cow — invert the permutation before printing.