Spinning Around
Given a binary string (S) of length (n) with exactly one 1. In each operation, you can reverse a substring of length (k). For each position (i), find the minimum number of operations to move the 1 to position (i). Some positions are forbidden and cannot hold the 1 during the process. If no such number exists, output (-1).
(n \le 10^5).
If position (i) can reach position (j), then:
- (|i-j| < k)
- (k+1 \le i+j \le 2n-(k-1))
- (i-j \not\equiv k \pmod{2})
The reachable positions from a given position form a contiguous segment of either all even or all odd indices.
Maintain two sets (set<int>) for unvisited odd and even positions. Perform BFS: for the current position, determine the parity of the next reachable set, use lower_bound to iterate over the valid range, remove visited positions immediately.
The time complexity is (O(n \log n)).
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, k, m, s;
bool forbidden[N];
int ans[N];
set<int> even_set, odd_set;
queue<int> q, del;
int main() {
scanf("%d%d%d%d", &n, &k, &m, &s);
for (int i = 1, x; i <= m; ++i) {
scanf("%d", &x);
forbidden[x] = true;
}
if (k > n || k == 1) {
for (int i = 1; i <= n; ++i)
printf(i == s ? "0 " : "-1 ");
return 0;
}
for (int i = 1; i <= n; ++i) {
if (forbidden[i] || i == s) continue;
if (i & 1) odd_set.insert(i);
else even_set.insert(i);
}
memset(ans, -1, sizeof(ans));
ans[s] = 0;
q.push(s);
while (!q.empty()) {
int cur = q.front(); q.pop();
int L = max(1, k + 1 - cur);
int R = min(n, 2 * n - (k - 1) - cur);
L = max(L, cur - k + 1);
R = min(R, cur + k - 1);
auto &target_set = ((cur - k) & 1) ? even_set : odd_set;
auto it = target_set.lower_bound(L);
while (it != target_set.end() && *it <= R) {
int nxt = *it;
ans[nxt] = ans[cur] + 1;
q.push(nxt);
del.push(nxt);
++it;
}
while (!del.empty()) {
target_set.erase(del.front());
del.pop();
}
}
for (int i = 1; i <= n; ++i)
printf("%d ", ans[i]);
return 0;
}
Bracket Matching
Given a string (S) consisting of (, ), and ? (wildcard). Count the number of substrings that can be rearranged into a valid bracket sequence.
(|S| \le 10^6).
Subtask 1: Only wildcards, (n \le 10^6)
Answer is the number of even-length substrings.
Subtask 2: No widlcards, (n \le 10^6)
Map ( to (+1), ) to (-1), compute prefix sum (s_i). For a substring ([i,j]) to be valid:
- (\forall k \in [i,j]: s_k \ge s_{i-1})
- (s_j = s_{i-1})
Use a monotonic stack to find for each left endpoint the maximal valid right endpoint, then use a vector and binary search with an offset to count exact matches.
Subtask 3 & 4: (n \le 2000)
DP with state ((l,r)): a substring is valid if it can be built by:
- Concatenating two valid substrings
- Wrapping a valid substring with
(and)
This gives (O(n^3)) with pruning.
Subtask 5: (n \le 10^6)
A substring ([l,r]) is valid if:
- Length is even
- Treating
(and?as (+1),)as (-1), the prefix sum (starting at (l)) never goes negative - Treating
)and?as (+1),(as (-1), the suffix sum (ending at (r)) never goes negative
Precompute, using monotonic stacks:
- (P_l): the maximum (r) such that the prefix condition holds for interval ([l,r])
- (Q_r): the minimum (l) such that the suffix condition holds for interval ([l,r])
For each (l), we need (r \in [l, P_l]) with (Q_r \le l). This is a 2D point counting problem. Use two Fenwick trees (for odd/even length) to process queries offline.
Complexity (O(n \log n)).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000010;
char s[N];
int n;
int pref[N], P[N], Q[N];
int st[N], top;
int tot;
struct Query {
int l, x, flag, parity;
bool operator<(const Query &o) const { return l < o.l; }
} q[N << 1];
int bit_odd[N], bit_even[N];
void add(int *t, int x, int v) {
for (; x <= n; x += x & -x) t[x] += v;
}
int sum(int *t, int x) {
int res = 0;
for (; x; x -= x & -x) res += t[x];
return res;
}
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
// compute P
for (int i = 1; i <= n; ++i)
pref[i] = pref[i-1] + (s[i] == ')' ? -1 : 1);
st[top = 1] = 0;
for (int i = 1; i <= n; ++i) {
while (top && pref[st[top]] > pref[i])
P[st[top--] + 1] = i - 1;
st[++top] = i;
}
while (top) P[st[top--] + 1] = n;
// compute Q (reverse)
for (int i = n; i >= 1; --i)
pref[i] = pref[i+1] + (s[i] == '(' ? -1 : 1);
st[top = 1] = n + 1;
for (int i = n; i >= 1; --i) {
while (top && pref[st[top]] > pref[i])
Q[st[top--] - 1] = i + 1;
st[++top] = i;
}
while (top) Q[st[top--] - 1] = 1;
// prepare queries
for (int i = 1; i <= n; ++i) {
if (i > P[i]) continue;
q[++tot] = {P[i], i, 1, i & 1};
if (i > 1) q[++tot] = {i - 1, i, -1, i & 1};
}
sort(q + 1, q + tot + 1);
ll ans = 0;
for (int i = 1, j = 1; i <= n && j <= tot; ++i) {
if (i >= Q[i]) add((i & 1) ? bit_odd : bit_even, Q[i], 1);
while (j <= tot && q[j].l == i) {
int *bit = (q[j].parity ? bit_even : bit_odd); // careful: parity of length = (r-l+1)&1, but we grouped by l's parity; adjust if needed
ans += q[j].flag * sum(bit, q[j].x);
++j;
}
}
printf("%lld\n", ans);
return 0;
}
Palindromes P
Given a string (S) with letters H and G. The cost of a substring is the minimum number of adjacent swaps needed to turn it into a palindrome (or (-1) if impossible). Compute the sum of costs over all substrings.
(|S| \le 7500), alphabet size 2.
Map to a binary string (e.g., H -> 1, G -> 0). A substring can be rearranged into a palindrome iff at most one character appears an odd number of times.
An optimal strategy groups the 1's from both ends towards the center. The cost for a substring ([l,r]) with 1's at positions (a_1, \dots, a_m) is: [ \left[ m \equiv 1 \pmod{2} \right] \cdot \left| \frac{l+r}{2} - a_{\frac{m+1}{2}} \right| + \sum_{i=1}^{\lfloor m/2 \rfloor} |a_i + a_{m-i+1} - l - r| ]
We can count contributions by pairing 1's. For a pair ((a_i, a_j)) (with (i \le j)), they contribute to all substrings where (l \le a_i, r \ge a_j), and the length parity is consistent. Use a sweep over pairs, maintaining two Fenwick trees for sums and counts of (l+r). Complexity (O(n^2 \log n)).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 7510;
int n, m;
char s[N];
bool a[N];
int pos[N];
int cnt_bit[2*N];
ll sum_bit[2*N];
ll total_sum;
int total_cnt;
void add_val(int c, int v) {
total_cnt += c;
total_sum += 1ll * c * v;
for (int x = v; x <= 2*n; x += x & -x) {
cnt_bit[x] += c;
sum_bit[x] += 1ll * c * v;
}
}
int query_cnt(int x) {
int res = 0;
for (; x; x -= x & -x) res += cnt_bit[x];
return res;
}
ll query_sum(int x) {
ll res = 0;
for (; x; x -= x & -x) res += sum_bit[x];
return res;
}
void process(int l, int r, int L, int R, bool odd_len) {
r -= l; R -= L;
for (int s = 0; s <= r + R; ++s) {
if (odd_len && ((s + l + L) & 1)) continue;
int left = max(0, s - R);
int right = min(s, r);
add_val(right - left + 1, s + l + L);
}
}
ll ans;
void solve(int start_l, int start_r) {
bool odd_len = ((pos[start_r] - pos[start_l] + 1) & 1);
total_cnt = total_sum = 0;
memset(cnt_bit, 0, sizeof(cnt_bit));
memset(sum_bit, 0, sizeof(sum_bit));
int l = start_l, r = start_r;
while (l <= r) {
process(pos[l-1] + 1, pos[l], pos[r], pos[r+1] - 1, odd_len);
int x = pos[l] + pos[r];
ll cur = total_sum - 2 * query_sum(x) + 1ll * x * (2 * query_cnt(x) - total_cnt);
ans += (l == r) ? cur / 2 : cur;
++l; --r;
}
}
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
int h_cnt = 0, g_cnt = 0;
for (int i = 1; i <= n; ++i) {
if (s[i] == 'H') h_cnt++;
else g_cnt++;
}
for (int i = 1; i <= n; ++i) {
a[i] = (s[i] == 'H') ^ (h_cnt > g_cnt);
if (a[i]) pos[++m] = i;
}
pos[m+1] = n+1;
for (int i = 1; i <= m; ++i) solve(1, i);
for (int i = 2; i <= m; ++i) solve(i, m);
// subtract substrings that cannot be palindrome
for (int l = 1; l <= n; ++l) {
int c0 = 0, c1 = 0;
for (int r = l; r <= n; ++r) {
if (!a[r]) c0++; else c1++;
if ((c0 & 1) && (c1 & 1)) ans--;
}
}
printf("%lld\n", ans);
return 0;
}
Card Pulling
Given (n) distinct binary strings of length (l). In each interaction, you receive the (i)-th bit with probability (p_i). For each string, find the expected number of interactions needed to uniquely identify it. Mod (998244353).
(T \le 10), (l \le 15), (n \le 2^l), (p_i \in [1, 10^4] \times 10^{-4}).
Use the standard expectation trick: For each state (S) (a pattern of known bits with ? for unknown), let (P_S) be the probability of staying in that state (i.e., no new bits revealed). The expected time spent in (S) is (t_S = 1/(1-P_S)). Transition from (S) to (T) (where (T) has more known bits) has coefficient (\prod_{i \in T \setminus S} p_i \times \prod_{i \notin T} (1-p_i) \times 1/(1-P_S)).
Computing (f_S): for each fully known state (mask of size (l)), set its id. Then for each (S) (ternary string of length (l)), determine if it unique identifies a string: set (f_S = -1) if ambiguous, otherwise the id. Fill using DP from smaller ? sets.
Then compute (P_S) and (t_S) for all (3^l) states, and for each string sum over states that cannot identify it.
Complexity (O(T \cdot 3^l)).
#include <bits/stdc++.h>
using namespace std;
const int L = 16;
const int N = 1 << L;
const int R = 14400000; // 3^15
const int MOD = 998244353;
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = 1ll * res * a % MOD;
a = 1ll * a * a % MOD;
b >>= 1;
}
return res;
}
const int INV_10000 = qpow(10000, MOD - 2);
int T, l, n;
int p[L];
int id[R];
int val[R];
int cnt[R], pcnt[R];
int f[N], hav[N], dis[N], ans[N];
int read_binary() {
char ch; int x = 0, cur = 0;
while (!isdigit(ch = getchar()));
while (isdigit(ch)) {
if (ch == '1') x |= (1 << cur);
cur++; ch = getchar();
}
return x;
}
int main() {
scanf("%d", &T);
int pow3[L];
pow3[0] = 1;
for (int i = 1; i < L; ++i) pow3[i] = pow3[i-1] * 3;
while (T--) {
scanf("%d%d", &l, &n);
for (int i = 0; i < l; ++i) {
scanf("%d", &p[i]);
p[i] = 1ll * p[i] * INV_10000 % MOD;
}
memset(id, 0, sizeof(id));
for (int i = 1; i <= n; ++i) {
int s = read_binary();
int enc = 0;
for (int j = 1; j <= l; ++j)
if (s & (1 << (j-1))) enc += pow3[l-j];
id[enc] = i;
}
if (n == 1) {
puts("0");
continue;
}
// compute cnt (number of ? bits) and val (actual mask)
memset(cnt, 0, sizeof(cnt));
cnt[0] = 0;
for (int i = 0; i < l; ++i) {
for (int k = 0; k < pow3[i]; ++k) {
pcnt[k*3] = cnt[k] + 1;
pcnt[k*3+1] = cnt[k] + 1;
pcnt[k*3+2] = 0;
}
for (int k = 0; k < pow3[i+1]; ++k) cnt[k] = pcnt[k];
}
for (int i = 0; i < pow3[l]; ++i) {
if (cnt[i] >= l) continue;
int nxt = i - pow3[cnt[i]];
val[i] = val[nxt] ^ (1 << (l - cnt[i] - 1));
if (!id[i]) id[i] = id[nxt];
else if (id[nxt] && id[nxt] != id[i]) id[i] = -1;
nxt = i - 2 * pow3[cnt[i]];
if (!id[i]) id[i] = id[nxt];
else if (id[nxt] && id[nxt] != id[i]) id[i] = -1;
}
// precompute hav and dis for all masks
for (int mask = 0; mask < (1<<l); ++mask) {
hav[mask] = dis[mask] = 1;
for (int i = 0; i < l; ++i) {
if (mask & (1<<i)) {
hav[mask] = 1ll * hav[mask] * p[i] % MOD;
dis[mask] = 1ll * dis[mask] * (MOD + 1 - p[i]) % MOD;
}
}
}
// compute f for all masks (fully known states)
f[(1<<l)-1] = 1;
ans[0] = 0;
for (int mask = (1<<l)-1; mask >= 0; --mask) {
int inv = qpow((MOD + 1 - dis[mask]) % MOD, MOD - 2);
f[mask] = 1ll * f[mask] * inv % MOD;
for (int sub = mask; sub; sub = (sub-1) & mask) {
int nxt = mask ^ sub;
f[nxt] = (f[nxt] + 1ll * f[mask] * hav[sub] % MOD * dis[mask ^ sub] % MOD) % MOD;
}
ans[0] = (ans[0] + f[mask]) % MOD;
}
for (int i = 1; i <= n; ++i) ans[i] = ans[0];
for (int i = 0; i < pow3[l]; ++i) {
int who = id[i];
if (who > 0) {
ans[who] = (ans[who] + MOD - f[val[i]]) % MOD;
}
}
for (int i = 1; i <= n; ++i)
printf("%d\n", ans[i]);
}
return 0;
}