#include <bits/stdc++.h>
using namespace std;
void test_case() {
int a, b, c, n; cin >> a >> b >> c >> n;
c = min(c, n / 100); n -= c * 100;
b = min(b, n / 10); n -= b * 10;
a = min(a, n); n -= a;
if (n == 0) cout << "YES\n";
else cout << "NO\n";
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) test_case();
}
We only need to use $100 coins as much as possible first, then $10 coins as much as possible, and finally $1 coins.
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int T; cin >> T;
while(T--) {
int n; cin >> n;
vector<int> a(n), b(n);
long long ans = LLONG_MIN, sum = 0, sa = 0, sb = 0;
for(auto &i: a) cin >> i;
for(auto &i: b) cin >> i, sum += i;
ans = 2 * a.back() - sum;
for(int i = n - 1 ; i >= 0 ; i--) {
sa += a[i], sb += b[i];
ans = max(ans, min((sa - a.back()) - (sb - b[i]), sa - (sum - b.back())));
}
cout << ans << '\n';
}
return 0;
}
Consider enumerate $$$i_a$$$ from $$$1$$$ to $$$n$$$.
For a fixed $$$i_a$$$,Bob has only two possible optimal options:choose $$$i_b=1 or i_a+1(if i_a \neq n)$$$.So Bob chooses $$$min(a_{i_a}+...+a_n-(b_1+...+b_{n-1}),a_{i_a}+...+a_{n-1}-(b_{i_a+1}+...+b_n))$$$.
Note $$$score_i$$$ as the answer for fixed $$$i_a=i$$$,the final answer is $$$max(score_i)$$$.
#include <bits/stdc++.h>
using namespace std;
#define int long long
void test_case() {
int n; cin >> n;
string s; cin >> s;
int same = 1, cnt = 0;
for (int i = 1; i < n; i++) {
if (s[i] != s[i - 1]) same = 0;
same++;
if (same >= 3) cnt += same - 2;
}
for (int i = 0; i < n; i += 2) s[i] = '1' + '0' - s[i];
same = 1;
for (int i = 1; i < n; i++) {
if (s[i] != s[i - 1]) same = 0;
same++;
cnt += (same - 1) / 2;
}
cout << cnt << '\n';
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) test_case();
}
The key observation is super palindromes are strings of length $$$\geq 3$$$ with all numbers equal, or a string with alternating $$$0-1$$$ (and has odd length).
After that, we only need to enumerate $$$i$$$ from $$$i$$$ to $$$n$$$ and count super palindromes that ends with $$$i$$$.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define N 210000
void test_case() {
int n; cin >> n;
int ptr = 1, need = n * (n + 1) / 4;
vector<int> bad;
for (int i = 1; i <= n; i++) {
while (ptr <= i) ptr++;
while (ptr <= n && (n + ptr) * (n - ptr + 1) / 2 >= need &&
(n + ptr) * (n - ptr + 1) / 2 - (n - i - (n - ptr + 1)) * (n - ptr + 1) > need) ptr++;
if ((n + ptr) * (n - ptr + 1) / 2 < need) {
bad.push_back(i);
need -= i;
continue;
}
cout << i << ' ';
}
for (int x : bad) cout << x << ' ';
cout << '\n';
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) test_case();
}
Let $$$p$$$ be the lexicographically smallest balanced permutation of length $$$n$$$ and $$$x$$$ be the integer such that $$$1 \leq x < n$$$ and $$$p_1+p_2+⋯+p_x=p_{x+1}+p_{x+2}+⋯+p_n$$$. Let's take a look to the lexicographically smallest (not necessary balanced) permutation of length $$$n$$$, which is $$${1,2,\dots,n}$$$.
Let $$$m$$$ be the largest value such that $$$1+2+\dots+m \leq (m+1)+(m+2)+\dots+n$$$. Notice that since $$$m$$$ is as large as possible, $$$1+2+\dots+m+(m+1) > (m+2)+(m+3)+\dots+n$$$. Which means, $$$x < m+1$$$ for \textbf{any} balanced permutation of length $$$n$$$ (since no matter how you rearrange the permutation, $$$p_1+p_2+⋯+p_{m+1} \geq 1+2+\dots+m+(m+1)$$$). It is also worth noting that $$$m < n$$$. This will be useful later.
Since $$$p$$$ is the lexicographically smallest balanced permutation of length $$$n$$$, we want to greedily shove as much small numbers as possible to the prefix of $$$p$$$, then sort the prefix from smallest to largest. Notice that since $$$x < m+1$$$, it is possible that $$$x = m$$$ in the optimal solution and we can prove that it actually is.
Assume $$$p = {1,2,\dots,n}$$$ (in other words, $$$p_i = i$$$ for all $$$1 \leq i \leq n$$$). Focus on the $$$m$$$ first numbers in the permutation. Let $$$r = \frac{1+2+\dots+n}{2} - (1+2+\dots+m)$$$ (which means $$$r \leq 0$$$). Since $$$1+2+\dots+m+(m+1) > (m+2)+(m+3)+\dots+n$$$, $$$r < m+1$$$ which means $$$r \leq m$$$. This means that in order to make sure $$$p_1+p_2+⋯+p_m = p_{m+1}+p_{m+2}+⋯+p_n$$$, we can just add $$$1$$$ to all $$$p_j$$$ where $$$m-r+1 \leq j \leq m$$$ and $$$p_1+p_2+⋯+p_m$$$ will still be a possible prefix of the permutation, since $$$p_m \leq n$$$ and $$$p_1 < p_2 < \dots < p_m$$$ will still be satisfied after the changes (because $$$m < n$$$ and $$$p_1 < p_2 < \dots < p_{m-r} < p_{m-r+1} < \dots < p_m$$$). Now that we know $$$x = m$$$, how can we make $$$p$$$ as small lexicographically as possible?
Let's focus on the first $$$m$$$ numbers inside $$$p$$$. Set $$$p_i := i$$$ for all $$$1 \leq i \leq m$$$. We will modify this later. Now, since $$$r = \frac{1+2+\dots+n}{2} - (1+2+\dots+m)$$$, we need to add the value $$$r$$$ to the first $$$m$$$ numbers by spreading the addition. However, to make sure $$$p$$$ is as small as possible, we have to greedily add some value to some last numbers inside $$${p_1,p_2,\dots,p_m}$$$ such that the added value is $$$r$$$ and $$${p_1,p_2,\dots,p_m}$$$ is lexicographically smallest. In other words, we can do this procedure to construct the first $$$m$$$ numbers inside the permutation:
\begin{itemize} \item Set $$$p_i := i$$$ for all $$$1 \leq i \leq m$$$. \item Let $$$j = m$$$. While $$$r > 0$$$, add $$$\min(r,k-j)$$$ to $$$p_j$$$, decrease $$$r$$$ by $$$\min(r,k-j)$$$, and decrease $$$j$$$ by $$$1$$$ where $$$k$$$ is the maximum integer such that $$$k \leq n$$$ and $$$k$$$ \textbf{currently} does not appear inside $$${p_1,p_2,\dots,p_m}$$$. \end{itemize}
For the last $$$n-m$$$ numbers, notice that we can just fill these with all the numbers that are not used in the first $$$m$$$ numbers, since the sum of the numbers will automatically be equal to $$$p_1+p_2+\dots+p_m = \frac{1+2+\dots+n}{2}$$$. Do note that to make sure $$$p$$$ is as small as possible, $$$p_{m+1} < p_{m+2} < \dots < p_n$$$ need to be satisfied.
Bonus question: can you guess which $$$n$$$ values results in no possible balanced permutation?
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)(1e16)
#define N 510000
#define K 51
int a[N], cnt[N], pref[N], dp[K][N], n, k;
void calc(int i, int l, int r, int vl, int vr) {
if (r < l) return;
int mid = (l + r) / 2;
int v, mn = INF;
for (int j = vr; j >= vl; j--) {
int sum = pref[mid] - pref[j - 1];
int need = cnt[mid] - cnt[j - 1];
if (i % 2 == 0) {
need = (j + j + need - 1) * need / 2;
sum = sum - need;
} else {
need = (mid + mid - need + 1) * need / 2;
sum = need - sum;
}
if (dp[i - 1][j - 1] + sum < mn) {
mn = dp[i - 1][j - 1] + sum;
v = j;
}
}
dp[i][mid] = mn;
calc(i, l, mid - 1, vl, v);
calc(i, mid + 1, r, v, vr);
}
void test_case() {
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 2; i <= n; i++)
a[i] ^= a[i - 1];
for (int i = 1; i <= n; i++)
cnt[i] = cnt[i - 1] + a[i], pref[i] = pref[i - 1] + i * a[i];
for (int i = 1; i < n; i++)
dp[0][i] = INF;
dp[0][0] = 0;
int ans = INF;
for (int i = 1; i <= k; i++) {
calc(i, 1, n - 1, 1, n - 1);
if (i + (a[n] ^ (i & 1)) <= k)
ans = min(ans, dp[i][n - 1]);
}
cout << ans << '\n';
}
int32_t main() {
int t; cin >> t;
while (t--) test_case();
}
...
...
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD (int)(1e9+7)
#define N 110000ll
#define K 20ll
#define B 850000006ll
struct segtree {
vector<int> sumk, sump, lk;
segtree() {}
segtree(int n) {
sumk = vector<int>(4 * n + 1, 0);
sump = vector<int>(4 * n + 1, 0);
lk = vector<int>(4 * n + 1, 1);
build(1, 0, n - 1);
}
void build(int v, int l, int r) {
sumk[v] = (r - l + 1);
if (l == r) return;
int mid = (l + r) / 2;
build(v * 2 + 0, l, mid);
build(v * 2 + 1, mid + 1, r);
}
void push(int v, int l, int r) {
if (lk[v] == 1) return;
sumk[v] = lk[v] * sumk[v] % MOD;
sump[v] = lk[v] * sump[v] % MOD;
if (l != r) {
lk[v * 2 + 0] = lk[v] * lk[v * 2 + 0] % MOD;
lk[v * 2 + 1] = lk[v] * lk[v * 2 + 1] % MOD;
}
lk[v] = 1;
}
void upd(int v, int l, int r, int k, int x) {
push(v, l, r);
if (k < l || r < k) return;
if (l == r) {
sumk[v] = 1;
sump[v] = x;
return;
}
int mid = (l + r) / 2;
upd(v * 2 + 0, l, mid, k, x);
upd(v * 2 + 1, mid + 1, r, k, x);
sumk[v] = (sumk[v * 2 + 0] + sumk[v * 2 + 1]) % MOD;
sump[v] = (sump[v * 2 + 0] + sump[v * 2 + 1]) % MOD;
}
void mul(int v, int l, int r, int ql, int qr, int k) {
push(v, l, r);
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
lk[v] = k;
push(v, l, r);
return;
}
int mid = (l + r) / 2;
mul(v * 2 + 0, l, mid, ql, qr, k);
mul(v * 2 + 1, mid + 1, r, ql, qr, k);
sumk[v] = (sumk[v * 2 + 0] + sumk[v * 2 + 1]) % MOD;
sump[v] = (sump[v * 2 + 0] + sump[v * 2 + 1]) % MOD;
}
int curk, curp;
void get(int v, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return;
push(v, l, r);
if (ql <= l && r <= qr) {curk += sumk[v]; curp += sump[v]; return;}
int mid = (l + r) / 2;
get(v * 2 + 0, l, mid, ql, qr);
get(v * 2 + 1, mid + 1, r, ql, qr);
}
};
int a[N];
segtree p[K], pp;
int inv(int x) {
return x == 1 ? 1 : MOD - MOD / x * inv(MOD % x) % MOD;
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin >> n >> q;
pp = segtree(n);
for (int i = 0; i < K; i++)
p[i] = segtree(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
for (int j = 0; j < K; j++)
if (a[i] & (1 << j)) p[j].upd(1, 0, n - 1, i, 1);
}
int pk = (1 - 2 * B % MOD + MOD) % MOD, pb = B;
int ppk = pk * pk % MOD, ppb = (B - B * B % MOD + MOD) % MOD;
int pki = inv((pk - 1 + MOD) % MOD), ppki = inv((ppk - 1 + MOD) % MOD);
while (q--) {
int t; cin >> t;
if (t == 1) {
int i, x; cin >> i >> x; i--;
for (int j = 0; j < K; j++)
p[j].upd(1, 0, n - 1, i, (x >> j) & 1);
pp.upd(1, 0, n - 1, i, 0);
} else if (t == 2) {
int l, r; cin >> l >> r; l--; r--;
for (int j = 0; j < K; j++)
p[j].mul(1, 0, n - 1, l, r, pk);
pp.mul(1, 0, n - 1, l, r, ppk);
} else if (t == 3) {
int l, r; cin >> l >> r; l--; r--;
if (l == r) {cout << 0 << '\n'; continue;}
int ev = 0;
pp.curk = pp.curp = 0;
pp.get(1, 0, n - 1, l, r);
int sumpp = ((pp.curk % MOD * ppb % MOD - (r - l + 1) * ppb % MOD + MOD) * ppki + pp.curp) % MOD;
for (int j = 0; j < K; j++) {
p[j].curk = p[j].curp = 0;
p[j].get(1, 0, n - 1, l, r);
int sump = ((p[j].curk % MOD * pb % MOD - (r - l + 1) * pb % MOD + MOD) * pki + p[j].curp) % MOD;
int cur = (sump * (r - l + 1 - sump + MOD) % MOD - sumpp + MOD) % MOD;
(ev += cur * (1 << j) % MOD) %= MOD;
}
(ev *= inv(r - l + 1) * inv(r - l) % MOD * 2 % MOD) %= MOD;
cout << ev << '\n';
}
}
}
Firstly, because of linearity of expectation, we can calculate answer for each bit independently.
Formula for expected value on segment for one bit is $$$\sum_{l\leq i\neq j\leq r} p_i(1-p_j)$$$, where $$$p_i$$$ is probability of $$$a_i$$$ being set to $$$1$$$.
$\displaystyle \sum_{l\leq i\neq j\leq r} p_i(1-p_j) = \sum_{l\leq i,j\leq r} p_i(1-p_j) — \sum_{l\leq i\leq r} p_i(1-p_i) =\ \displaystyle (\sum_{l\leq i\leq r} p_i)(\sum_{l\leq i\leq r} (1-p_i)) — \sum_{l\leq i\leq r} p_i(1-p_i) =\ \displaystyle (\sum_{l\leq i\leq r} p_i)(r-l+1 — \sum_{l\leq i\leq r} p_i) — \sum_{l\leq i\leq r} p_i(1-p_i)$
To calculate this, we just need to maintain $$$\sum_{l\leq i\leq r} p_i$$$ and $$$\sum_{l\leq i\leq r} p_i(1-p_i)$$$ Let $$$po_i$$$ be $$$p_i$$$ before second operation and $$$b$$$ probability of bit changing ($$$\frac{1}{20}$$$).
$p_i = po_i\cdot (1-b) + (1-po_i)\cdot b =\ po_i — po_i\cdot 2b + b = (1-2b)po_i + b$
$p_i(1-p_i) = ((1-2b)po_i + b)(1 — (1-2b)po_i — b) =\ (1-2b)po_i + b — ((1-2b)po_i + b)^2 =\ (1-2b)po_i + b — (1-2b)(1-2b)po_i^2 — b^2 — 2b(1-2b)po_i =\ (1-2b)(1-2b)po_i — (1-2b)(1-2b)po_i^2 + b — b^2 =\ (1-2b)(1-2b)po_i(1 — po_i) + b — b^2$
Now to maintain $$$\sum_{l\leq i\leq r} p_i$$$ and $$$\sum_{l\leq i\leq r} p_i(1-p_i)$$$ we just need to apply linear function on segment, we can do it using segment tree. This is already fast enough for C++20 compiler. We can notice that $$$p_i(1-p_i)$$$ is same for all bits, so we can maintain only one segtree for it. With this optimization solution passes using other compilers.
The final complexity is $$$\mathcal{O}(n \log n \log A)$$$
