Balanced String Analysis (Simple and Extended)
Problem Statement
We need to analyze strings composed of 0, 1, and ?. The question marks can be replaced with either 0 or 1. The goal is to compute how many valid configurations result in "balanced" strings according to a specific criterion.
Simple Approach
For small lengths, a brute-force enumeration over all possible replacements of ? with {0,1} works. For each fully specified string, we can check its balance property by flipping each character one by one and counting the "01" and "10" transitions.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
// modular arithmetic helper (omitted for brevity)
using Z = MInt<1000000007>;
void solve() {
int len;
cin >> len;
string base;
cin >> base;
int qmarks = count(base.begin(), base.end(), '?');
Z total = 0;
string candidate = base;
for (int mask = 0; mask < (1 << qmarks); ++mask) {
int pos = 0;
for (int i = 0; i < len; ++i) {
if (base[i] != '?') {
candidate[i] = base[i];
} else {
candidate[i] = ((mask >> pos) & 1) + '0';
++pos;
}
}
int balanced_positions = 0;
for (int i = 0; i < len; ++i) {
candidate[i] = (candidate[i] == '1') ? '0' : '1';
int cnt01 = 0, cnt10 = 0;
for (int k = 0; k < len - 1; ++k) {
if (candidate[k] == '0' && candidate[k + 1] == '1') cnt01++;
if (candidate[k] == '1' && candidate[k + 1] == '0') cnt10++;
}
candidate[i] = (candidate[i] == '1') ? '0' : '1';
if (cnt01 == cnt10) balanced_positions++;
}
total += balanced_positions;
}
cout << total << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Extended Approach
A deeper pattern emerges: the balance condition depends mostly on whether the first and last characters differ. If they are the same, the string is always balanced. If they differ, each differing pair contributes two balanced configurations. Therefore we can compute the answer by:
- Enumerating possible values for the first and last character.
- Counting how many
?appear in the middle.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using Z = MInt<1000000007>;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
if (n == 1) {
cout << (s == "?" ? 2 : 1) << "\n";
return;
}
vector<int> front_options, back_options;
if (s[0] == '?') front_options = {0, 1};
else front_options = {s[0] - '0'};
if (s.back() == '?') back_options = {0, 1};
else back_options = {s.back() - '0'};
int diff_count[2] = {};
for (int f : front_options)
for (int b : back_options)
diff_count[f ^ b]++;
Z mid_power = 1;
for (int i = 1; i < n - 1; ++i)
if (s[i] == '?') mid_power *= 2;
Z ans = (diff_count[1] * 2 + diff_count[0] * (n - 2)) * mid_power;
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Palindrome Construction via Concatenation
Strategy
Given two strings of different lengths, we want to form a palindrome by concatenating them and potentially modifying characters. The idea is to use the longer string to supply characters that the shorter lacks. We compute the difference in frequency per letter, then check how many odd frequency positions in the longer string can compensate.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int len_a, len_b;
cin >> len_a >> len_b;
string a, b;
cin >> a >> b;
if (len_a < len_b) {
swap(len_a, len_b);
swap(a, b);
}
vector<int> freq_a(26), freq_b(26);
for (char c : a) freq_a[c - 'a']++;
for (char c : b) freq_b[c - 'a']++;
int deficit = 0;
for (int i = 0; i < 26; ++i) {
if (freq_a[i] < freq_b[i]) {
deficit += freq_b[i] - freq_a[i];
freq_a[i] = 0;
} else {
freq_a[i] -= freq_b[i];
}
}
len_a -= len_b;
int odd_count = 0;
for (int i = 0; i < 26; ++i) odd_count += freq_a[i] % 2;
if (odd_count >= deficit) {
odd_count -= deficit;
cout << deficit + odd_count / 2 << "\n";
} else {
cout << deficit << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Dragon’s Breath Maximum Damage
Concept
Each cell (i,j) attacks along its primary diagonal (constant i - j) and secondary diagonal (constant i + j). We precompute the sum of monster values on each diagonal and then test every cell to find the maximum total damage, remembering to subtract the cell’s own value once because its counted twice.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int rows, cols;
cin >> rows >> cols;
vector<vector<int>> grid(rows, vector<int>(cols));
map<int, i64> sum_primary, sum_secondary;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
cin >> grid[i][j];
sum_primary[i - j] += grid[i][j];
sum_secondary[i + j] += grid[i][j];
}
}
i64 max_damage = 0;
for (int i = 0; i < rows; ++i)
for (int j = 0; j < cols; ++j)
max_damage = max(max_damage,
sum_primary[i - j] + sum_secondary[i + j] - grid[i][j]);
cout << max_damage << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Counting Pattern Occurrences with Prefix Sums
Method
While scanning the string, keep a prefix count of the character u. Whenever the pattern "uwawauwa" is found, add the number of u's before the two characters preceding the pattern.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
string s;
cin >> s;
s = " " + s;
i64 result = 0;
vector<int> prefix_u(n + 1);
for (int i = 1; i <= n; ++i) {
prefix_u[i] = prefix_u[i - 1] + (s[i] == 'u');
if (s.substr(i, 8) == "uwawauwa") {
result += prefix_u[i - 2];
}
}
cout << result << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}
Maximum of Three Products
Direct Calculation
Simply output the maximum of x*a, y*b, or z*c.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int x, y, z, a, b, c;
cin >> x >> y >> z >> a >> b >> c;
cout << max({x * a, y * b, z * c}) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}
XOR-Based Triangle Sum Query
Explanation
The task is to compute sums of the form (\sum_{i=l}^r \sum_{j=i}^r a_i \oplus b_j). Because direct computation per query would be too slow, we decompose the sum:
[ \sum_{i=l}^r \sum_{j=i}^r a_i \oplus b_j = \sum_{i=l}^r \sum_{j=i}^n a_i \oplus b_j - \sum_{i=l}^r \sum_{j=r+1}^n a_i \oplus b_j ]
- The second term involves disjoint intervals and can be computed bitwise by counting 0/1 in (a[l..r]) and (b[r+1..n]).
- The first term is preprocessed: define (f_i = \sum_{j=i}^n a_i \oplus b_j) and its prefix sum (g_i). Then the first term equals (g_r - g_{l-1}).
Implementation
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
// Modular arithmetic support (similar to earlier)
using Z = MInt<1000000007>;
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1), b(n + 1);
vector<vector<int>> bits_a(n + 1, vector<int>(31)), bits_b(n + 1, vector<int>(31));
for (int i = 1; i <= n; ++i) {
cin >> a[i];
bits_a[i] = bits_a[i - 1];
for (int bit = 30; bit >= 0; --bit)
if ((a[i] >> bit) & 1) bits_a[i][bit]++;
}
for (int i = 1; i <= n; ++i) {
cin >> b[i];
bits_b[i] = bits_b[i - 1];
for (int bit = 30; bit >= 0; --bit)
if ((b[i] >> bit) & 1) bits_b[i][bit]++;
}
vector<Z> suffix_sum(n + 1);
for (int i = n; i >= 1; --i) {
for (int bit = 30; bit >= 0; --bit) {
Z a1 = (a[i] >> bit) & 1, a0 = 1 - a1;
Z b1 = bits_b[n][bit] - bits_b[i - 1][bit], b0 = (n - i + 1) - b1;
suffix_sum[i] += (a1 * b0 + b1 * a0) * (1LL << bit);
}
}
vector<Z> prefix_sum(n + 1);
for (int i = 1; i <= n; ++i) prefix_sum[i] = prefix_sum[i - 1] + suffix_sum[i];
while (q--) {
int l, r;
cin >> l >> r;
Z disjoint_term = 0;
for (int bit = 30; bit >= 0; --bit) {
Z a1 = bits_a[r][bit] - bits_a[l - 1][bit];
Z a0 = (r - l + 1) - a1;
Z b1 = bits_b[n][bit] - bits_b[r][bit];
Z b0 = (n - r) - b1;
disjoint_term += (a1 * b0 + b1 * a0) * (1LL << bit);
}
Z answer = prefix_sum[r] - prefix_sum[l - 1] - disjoint_term;
cout << answer << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) solve();
return 0;
}