Salam !
Here is the editorial for Codeforces Global Round 31. We hope you find these solutions helpful. We also have prepared a special editorial with step by step hint, examples, tables, and walkthroughs which is available here.
2180A - Carnival Wheel
Idea: AmirrzwM, MohammadParsaElahimanesh — Preparation: MohammadParsaElahimanesh
Since constraints are small, we can simulate the spins directly:
- Start from section $$$a$$$.
- Move the pointer by adding $$$b$$$ modulo $$$l$$$ repeatedly.
- Stop when we return to a previously visited section.
- Among all visited sections, select the section with the highest prize.
It runs in $$$\mathcal{O}(l)$$$ as we mark each section at most once.
It's easy to see that the pointer can land on section $$$c$$$ if $$$c \equiv a \pmod{d}$$$, where $$$d = \gcd(l, b)$$$. By Bézout's lemma, all such $$$c$$$ are indeed reachable. Hence, the maximum attainable section is:
// In the name of God
#include <bits/stdc++.h>
using namespace std;
int main() {
int l, a, b, t;
cin >> t;
while(t--) {
cin >> l >> a >> b;
cout << l - __gcd(l, b) + a % __gcd(l, b) << '\n';
}
return 0;
}
2180B - Ashmal
Idea: AmirrzwM, MohammadParsaElahimanesh — Preparation: MohammadParsaElahimanesh
Step 1: It can be shown (for instance, via a contradiction argument) that, to obtain the lexicographically minimum final string $$$s$$$, we must ensure $$$s$$$ is lexicographically minimum at each intermediate step as well.
Step 2: Therefore, at every step $$$i$$$, we choose the lexicographically smaller result between adding $$$a_i$$$ to the beginning or the end of our current string.
Step 3: Initially, $$$s$$$ is the empty string. Suppose before step $$$i$$$, the current string is $$$s_i$$$. Then the best choice for the updated string is:
- Step 4: By applying this choice at each step, we can compute the final (minimum) string in $$$\mathcal{O}(nS)$$$ where $$$S$$$ is the sum of string lengths.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
string s[n], t;
for(int i = 0; i < n; i++)
cin >> s[i];
for(int i = 0; i < n; i++)
t = min(t+s[i], s[i]+t);
cout << t << '\n';
}
return 0;
}
2180C - XOR-factorization
Idea: MohammadParsaElahimanesh — Preparation: MohammadParsaElahimanesh
We build $$$a_1,\dots,a_k$$$ bit by bit from the highest bit to $$$0$$$.
Let
Maintain two sets of indices:
$$$T$$$ (tight): current prefix of $$$a_i$$$ equals the prefix of $$$n$$$,
$$$L$$$ (loose): current prefix of $$$a_i$$$ is already smaller than the prefix of $$$n$$$.
Initially, $$$T={1,\dots,k}$$$, $$$L=\emptyset$$$, and all $$$a_i=0$$$.
Greedy rule for each bit $$$b$$$ (from high to low).
If the $$$b$$$-th bit of $$$n$$$ is $$$1$$$, then the number of $$$a_i$$$ having bit $$$b$$$ equal to $$$1$$$ must be odd. To maximize the sum we set as many ones as possible, i.e. exactly $$$o(k)$$$. So:
- if $$$k$$$ is odd, set this bit in all $$$k$$$ numbers;
- if $$$k$$$ is even, set it in all but one number. Prefer choosing that one from $$$T$$$ (if possible), because then it becomes loose ($$$T\to L$$$), which can help later.
If the $$$b$$$-th bit of $$$n$$$ is $$$0$$$, then the number of ones in this bit must be even. Tight indices cannot put $$$1$$$ here (otherwise $$$a_i \gt n$$$), so only $$$L$$$ may receive ones. Thus we set this bit in exactly $$$e(|L|)$$$ loose numbers (all of them if $$$|L|$$$ is even, otherwise all but one).
Why it is optimal. At bit $$$b$$$, each extra chosen $$$1$$$ adds $$$2^b$$$ to the total sum, and this gain is larger than anything we can get from lower bits. Also, the XOR condition fixes the parity in every bit, so we can only change the number of $$$1$$$’s by removing them from an even number of elements. So, at every bit we should keep as many $$$1$$$’s as possible, as long as we do not violate $$$a_i\le n$$$. When the $$$b$$$-th bit of $$$n$$$ is $$$1$$$ and $$$k$$$ is even, we must place one $$$0$$$; choosing it from a tight index increases $$$|L|$$$, which can help us place more $$$1$$$’s later when $$$n$$$ has $$$0$$$-bits.
This directly gives a construction with $$$0\le a_i\le n$$$, XOR equal to $$$n$$$, and maximum possible sum in $$$\mathcal{O}(k \log n)$$$.
// In the name of god
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
int a[k]{}, p = 0;
if(k&1)
for(int i = 0; i < k; i++)
a[i] = n;
else {
for(int i = 30; i >= 0; i--) {
if(n >> i & 1) {
for(int j = 0; j < k; j++)
if(j != min(p, k-1))
a[j] += (1 << i);
if(p < k)
p++;
} else
for(int j = 0; j < p/2*2; j++)
a[j] += (1 << i);
}
}
for(int i = 0; i < k; i++)
cout << a[i] << (i+1 == k? '\n':' ');
}
return 0;
}
2180D - Insolvable Disks
Idea: AmirrzwM, MohammadParsaElahimanesh — Preparation: AmirrzwM
Let $$$x_1, x_2, \ldots, x_n$$$ be the sorted list of points, and let $$$d_i \ (1 \le i \le n-1)$$$ be the distance between consecutive points, i.e.
We try to find the largest prefix of points that can be made connected.
Consider some valid choice of radii, and assume that the radius of the first disk is $$$r_1 = x$$$. In order for the second disk to be tangent to the first one, its radius must be
Continuing in this way, the third disk must have radius
In general, if we connect the first $$$k$$$ disks together, the radius of the $$$i$$$-th disk $$$(1 \le i \le k)$$$ must be
For this configuration to be valid, we must have
Substituting the expression for $$$r_i$$$, we obtain
For odd $$$i$$$, this inequality becomes
which is equivalent to
For even $$$i$$$, we obtain
which is equivalent to
Therefore, for each $$$i$$$ we obtain an interval of valid values for $$$x$$$. By iterating over $$$i$$$ and maintaining the intersection of all these intervals, we can determine the first index where the intersection becomes empty. This index gives the largest prefix of disks that can be made connected.
After removing these disks, we can repeat the same process on the remaining ones. It can be shown that this procedure finds the correct answer and runs in $$$O(n)$$$ time.
Why it is optimal.
For each index $$$i$$$, let $$$f_i$$$ be the rightmost position such that, for every $$$j$$$ with $$$i \le j \lt f_i$$$, we can simultaneously make the $$$j$$$-th disk tangent to the $$$(j+1)$$$-th disk. Thus, $$$f$$$ is increasing sequence.
With this notation, the problem becomes selecting indices $$$1=i_1 \lt i_2 \lt \cdots \lt i_k$$$ such that
By induction, we may assume $$$i_{t+1}=f_{i_t}+1$$$, because choosing any smaller $$$i_{t+1}\le f_{i_t}+1$$$ cannot extend the reachable prefix beyond $$$f_{i_t}$$$, while choosing exactly $$$f_{i_t}+1$$$ is the earliest index that can potentially increase the farthest reachable position. Hence this greedy choice is optimal. Also, note that once we set $$$i_{t+1}=f_{i_t}+1$$$, there are no additional constraints on the choice of $$$r_{i_{t+1}}$$$ coming from earlier indices. In particular, any restriction on $$$r_{i_{t+1}}$$$ can only be imposed by $$$i_{t+1}+1$$$ (otherwise $$$f_{i_t}$$$ would not have been maximal by definition).
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false) , cin.tie(0);
int tt;
cin >> tt;
while(tt--){
int n;
cin >> n;
int x[n];
for(int i = 0 ; i < n ; i++) cin >> x[i];
int ans = n-1;
int l = 0 , r = +1e9+1;
int cur = 0;
int fst = 1;
for(int i = 1 ; i < n ; i++){
cur = (x[i] - x[i-1]) - cur;
if(i % 2 == fst % 2){
r = min(r , cur);
if(i < n-1) l = max(l , cur - (x[i+1] - x[i]));
}
else{
l = max(l , -cur);
if(i < n-1) r = min(r , (x[i+1] - x[i]) - cur);
}
if(l >= r){
ans--;
l = 0 , r = +1e9+1;
cur = 0;
fst = i+1;
}
}
cout << ans << endl;
}
}
2180E - No Effect XOR
Idea: AmirrzwM — Preparation: MohammadParsaElahimanesh
Step 0. Let us consider $$$0$$$ as valid answer, for $$$l=r$$$ it's the only value, so assume $$$l \lt r$$$. Also xor is a bijection, so if $$$[l,r]$$$ maps to itself then its complement in $$$\mathbb W$$$ (all non-negative integers) also maps to itself.
Step 1. Let's count the number of $$$x$$$ such that maps $$$[0,n)$$$ to itself. If $$$n=2^k$$$ then every $$$0\le x \lt n$$$ works. If $$$2^{k-1} \lt n \lt 2^k$$$, then the $$$(k-1)$$$-th bit of $$$x$$$ must be $$$0$$$; otherwise it maps $$$2^k-1$$$ into $$$[0,n)$$$, hence the answer equals the answer for $$$[0, n-2^{k-1})$$$. Therefore the answer is simply the largest power of two dividing $$$n$$$.
Step 2. Choose $$$k$$$ with $$$2^{k-1}\le r \lt 2^k$$$. If $$$2^{k-1} \le l \lt r \lt 2^k$$$, then every number in $$$[l,r]$$$ has the $$$(k-1)$$$-th bit equal to $$$1$$$, so subtracting $$$2^{k-1}$$$ from both ends just removes that common bit and does not change the answer; repeating this reduction, we may assume $$$0 \le l \lt 2^{k-1} \le r \lt 2^k$$$.
Step 3. Work in the block $$$[0,2^k-1]$$$ and define $$$A=[0,l-1]$$$, $$$B=[l,r]$$$, $$$C=[r+1,2^k-1]$$$. We need $$$B\oplus x=B$$$. In this crossing case, every element of $$$A$$$ has $$$(k-1)$$$-th bit $$$0$$$ and every element of $$$C$$$ has $$$(k-1)$$$-th bit $$$1$$$, so xor by $$$x$$$ cannot send only part of $$$A$$$ to $$$C$$$. Since xor is a bijection on the whole block, once $$$B$$$ maps to itself we must also map $$$A\cup C$$$ to itself, and there are only two possibilities:
Map $$$A\to A$$$, $$$B\to B$$$, $$$C\to C$$$. This is equivalent to simultaneously keeping the prefix $$$A=[0,l)$$$ invariant and also keeping the prefix $$$A\cup B=[0,r+1)$$$ invariant.
Map $$$A\to C$$$ and $$$C\to A$$$, while still $$$B\to B$$$. This is possible only if $$$|A|=|C|$$$. Define $$$\bar{x}=x\oplus(2^k-1)$$$. Then for every $$$x$$$ that maps $$$A$$$ to $$$A$$$, the value $$$\bar{x}$$$ maps $$$A$$$ to $$$C$$$, and vice versa, since $$$2^k-1=(11\ldots 1)_2$$$ acts like a mirror on $$$[0,2^k)$$$.
Let $$$S$$$ be the set of all valid $$$x$$$ (including $$$0$$$). We claim that $$$S$$$ is closed under XOR. Assume $$$x,y\in S$$$. By validity, for every $$$i\in[l,r]$$$ we have
But $$$(i\oplus x)\oplus y = i\oplus (x\oplus y)$$$, hence for all $$$i\in[l,r]$$$,
so $$$x\oplus y\in S$$$. Therefore $$$S$$$ forms a vector space over $$$\mathbb{F}_2$$$, and it is enough to find a basis.
Consider
For $$$0\le x \lt 2^n$$$ we have
so $$$f_n$$$ acts like a mirror inside each block of length $$$2^n$$$. Motivated by this, we guess that basis elements are of the form $$$(111\ldots1)_2$$$, i.e. $$$2^n-1$$$.
Now we determine for which $$$n$$$ we have $$$2^n-1\in S$$$. Define the blocks
If $$$r-l+1 \gt 2^n$$$, then $$$2^n-1$$$ is valid if and only if for every $$$k$$$, the intersection $$$[l,r]\cap b_k$$$ is either empty or the whole block $$$b_k$$$ (equivalently, $$$[l,r]$$$ never cuts a block partially), since $$$f_n$$$ preserves each block and reverses the order inside it.
We must also check one boundary case, where $$$f_n$$$ maps $$$[l,r]$$$ to itself, which happens only if:
In other words, $$$l$$$ and $$$r$$$ must be symmetric with respect to the midpoint of one block under the mirror $$$f_n$$$.
// In the name of god
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll maxPower2Multiple(const ll &a) {return a&-a;}
inline ll prefixAnswer(const ll &a) {return maxPower2Multiple(a);}
inline bool isPerfect(const ll &a) {return a == maxPower2Multiple(a);}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int t;
cin >> t;
while(t--) {
ll l, r;
cin >> l >> r;
ll both = 1LL<<60;
while((both&l) == (both&r) && both > 0) {
if(both&l) l -= both, r -= both;
both >>= 1;
}
if(l and isPerfect(l+r+1))
cout << 2LL*min(prefixAnswer(l), prefixAnswer(r+1LL))-1LL << '\n';
else if(l)
cout << min(prefixAnswer(l), prefixAnswer(r+1LL))-1LL << '\n';
else
cout << prefixAnswer(r+1LL)-1LL << '\n';
}
return 0;
}
2180F1 - Control Car (Easy Version)
Idea: MohammadParsaElahimanesh — Preparation: MohammadParsaElahimanesh, AmirrzwM
We solve the problem using dynamic programming.
A naive DP definition would be to let $$$dp[i][j]$$$ be the probability that a car, currently at cell $$$(i,j)$$$, eventually reaches the bottom-right corner of the grid. However, this state does not contain enough information to determine valid transitions, since the future movement of the car depends on the direction from which it entered the current cell and on the orientations of certain walls. Therefore, we need to add more information to our DP states.
We define the following DP states:
$$$dp[i][j][0][0]$$$: the probability that the car reaches the bottom-right corner, given that it is currently at cell $$$(i,j)$$$, entered this cell from above, and the wall starting from the top-right corner of this cell is pointing downward.
$$$dp[i][j][0][1]$$$: similar to $$$dp[i][j][0][0]$$$, but the wall starting from the top-right corner of the cell is \textbf{not} pointing downward.
$$$dp[i][j][1][0]$$$: the probability that the car reaches the bottom-right corner, given that it is currently at cell $$$(i,j)$$$, entered this cell from the left, and the wall starting from the bottom-left corner of this cell is pointing to the right.
$$$dp[i][j][1][1]$$$: similar to $$$dp[i][j][1][0]$$$, but the wall starting from the bottom-left corner of the cell is \textbf{not} pointing to the right.
We now describe how to compute the transitions.
Consider the state $$$dp[i][j][0][0]$$$. In this case, the car is at cell $$$(i,j)$$$, it entered from above, and the top-right wall is pointing downward. Therefore, the car cannot move to cell $$$(i,j+1)$$$ and must move to cell $$$(i+1,j)$$$.
After moving to $$$(i+1,j)$$$, there is a probability of $$$\frac{3}{16}$$$ that the top-right wall of the new cell is pointing downward, and a probability of $$$\frac{3}{8}$$$ that it is not. Thus, we obtain
Using similar arguments for the remaining states, we get the following transitions:
By computing these DP states in reverse order of $$$i$$$ and $$$j$$$, we can evaluate all states in $$$O(nm)$$$ time and obtain the final answer.
// In the name of god
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int T = 10000;
constexpr int N = 5000;
constexpr ll mod = 1000000007;
constexpr ll inv2 = (mod+1)>>1;
constexpr ll inv4 = inv2>>1;
constexpr ll inv8 = inv4>>1;
constexpr ll inv16 = (inv8+mod)>>1;
ll dp[2][N+1][2][2];
vector<pair<int, int>> query[N+1];
ll ans[T];
inline ll Pow(ll a, ll b) {
ll res = 1LL;
b %= mod-1;
while(b) {
if(b&1) res = (res*a)%mod;
a = (a*a)%mod;
b >>= 1;
}
return res;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int t;
cin >> t;
for(int n, m, i = 0; i < t; i++) {
cin >> n >> m;
query[n].push_back({m, i});
}
for(int i = 0; i <= N; i++)
dp[N&1][i][0][0] = dp[N&1][i][0][1] = dp[N&1][i][1][0] = dp[N&1][i][1][1] = 1;
for(int i = N-1; i >= 0; i--) {
int q = i&1, p = 1-(i&1);
dp[q][N][0][0] = dp[q][N][0][1] = dp[q][N][1][0] = dp[q][N][1][1] = 1;
for(int j = N-1; j >= 0; j--) {
dp[q][j][0][0] = (dp[p][j][0][0]*3LL*inv16+dp[p][j][0][1]*3LL*inv8)%mod;
dp[q][j][0][1] = ((dp[p][j][0][0]*3LL*inv16+dp[p][j][0][1]*3LL*inv8)%mod+
dp[q][j+1][1][0]*inv16+dp[q][j+1][1][1]*5LL*inv16)%mod;
dp[q][j][1][0] = (dp[q][j+1][1][0]*3LL*inv16+dp[q][j+1][1][1]*3LL*inv8)%mod;
dp[q][j][1][1] = (dp[p][j][0][0]*inv4+dp[p][j][0][1]*inv2+dp[q][j+1][1][1]*3LL*inv16)%mod;
}
for(auto [m, qu]: query[N-i]) {
ll P = (dp[q][N-m][0][0]*inv4+dp[q][N-m][0][1]*3LL*inv4)%mod;
ans[qu] = (1LL-P+mod)*Pow(4LL, 1LL*(N-i+1)*(m+1))%mod;
}
}
for(int i = 0; i < t; i++)
cout << ans[i] << '\n';
return 0;
}
2180F2 - Control Car (Hard Version)
Idea: MohammadParsaElahimanesh — Preparation: MohammadParsaElahimanesh, AmirrzwM
Note that the $$$j$$$-th layer of DP states (that is, $$$dp[i][j]$$$ for all valid $$$i$$$) depends only on the $$$(j-1)$$$-th layer and the $$$j$$$-th layer itself. Moreover, all layers are computed using identical transition rules.
Let $$$dp[j]$$$ denote the vector consisting of all states $$$dp[i][j]$$$ for a fixed $$$j$$$. Then there exists a constant transition matrix $$$M$$$ such that
By computing $$$M^{\,m-1}$$$ and multiplying it by the initial vector $$$dp[1]$$$, we obtain $$$dp[m]$$$, from which the final answer can be extracted.
This can be done in $$$O(n^3 \log m)$$$ time using binary exponentiation.
// In the name of god
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll N = 50 + 1;
constexpr ll M = 1000000000000000LL;
constexpr ll mod = 1000000007;
constexpr ll inv2 = (mod+1)>>1;
constexpr ll inv4 = inv2>>1;
constexpr ll inv8 = inv4>>1;
constexpr ll inv16 = (inv8+mod)>>1;
ll n, m;
struct DP {
ll dp[N][2][2][N][2][2] = {};
};
inline DP upd(const DP& l, const DP& r) {
DP lr;
for(int li = 0; li <= n; li++)
for(int lh = 0; lh < 2; lh++)
for(int lk = 0; lk < 2; lk++)
for(int ri = li; ri <= n; ri++)
for(int rh = 0; rh < 2; rh++)
for(int rk = 0; rk < 2; rk++)
for(int mi = li; mi <= ri; mi++) {
for(int mh = 0; mh < 2; mh++)
for(int mk = 0; mk < 2; mk++)
lr.dp[li][lh][lk][ri][rh][rk] += l.dp[li][lh][lk][mi][mh][mk]*r.dp[mi][mh][mk][ri][rh][rk];
lr.dp[li][lh][lk][ri][rh][rk] %= mod;
}
return lr;
}
inline DP Identical() {
DP I;
for(int i = 0; i < n; i++)
for(int j = 0; j < 2; j++)
for(int k = 0; k < 2; k++)
I.dp[i][j][k][i][j][k] = 1;
return I;
}
inline DP Pow(DP a, ll b) {
DP res = Identical();
while(b) {
if(b&1) res = upd(res, a);
a = upd(a, a);
b >>= 1;
}
return res;
}
inline ll Pow(ll a, ll b) {
ll res = 1LL;
while(b) {
if(b&1) res = res*a%mod;
a = a*a%mod;
b >>= 1;
}
return res;
}
int main()
{
int t;
cin >> t;
while(t--) {
cin >> n >> m;
DP col;
col.dp[n][0][0][n][0][0] = col.dp[n][0][1][n][0][1] = col.dp[n][1][0][n][1][0] = col.dp[n][1][1][n][1][1] = 1;
for(int i = (int)n-1; i >= 0; i--) {
for(int j = i+1; j <= n; j++)
for(int k = 0; k < 2; k++)
for(int l = 0; l < 2; l++) {
col.dp[i][0][1][j][k][l] = col.dp[i][0][0][j][k][l] = (col.dp[i+1][0][0][j][k][l]*3LL*inv16+col.dp[i+1][0][1][j][k][l]*3LL*inv8)%mod;
col.dp[i][1][1][j][k][l] = (col.dp[i+1][0][0][j][k][l]*inv4+col.dp[i+1][0][1][j][k][l]*inv2)%mod;
}
col.dp[i][0][1][i][1][0] = inv16;
col.dp[i][0][1][i][1][1] = 5LL*inv16%mod;
col.dp[i][1][0][i][1][0] = 3LL*inv16%mod;
col.dp[i][1][0][i][1][1] = 3LL*inv8%mod;
col.dp[i][1][1][i][1][1] = 3LL*inv16;
}
DP dpnm = Pow(col, m);
ll ans = 0;
for(int i = 0; i <= n; i++)
for(int j = 0; j < 2; j++)
for(int k = 0; k < 2; k++)
ans = (ans+dpnm.dp[0][0][0][i][j][k]*inv4+dpnm.dp[0][0][1][i][j][k]*3LL*inv4)%mod;
cout << (1LL-ans+mod)*Pow(4LL, 1LL*(n+1LL)*(m+1LL))%mod << '\n';
}
return 0;
}
2180G - Balance
Idea: MohammadParsaElahimanesh, AmirrzwM, Shayan — Preparation: AmirrzwM
First, note that due to the structure of the queries, the array $$$a$$$ is always a palindrome.
Let $$$n$$$ be the current length of the array. Define $$$c_{i,m,k}$$$ as the number of subsequences of $$$a$$$ of length $$$m$$$ in which $$$a_i$$$ appears as the $$$k$$$-th element. Then the total sum of balances over all non-empty subsequences is equal to
By symmetry of the palindrome, we have
Using this symmetry, we can write
After rearranging terms, this implies that the total balance can be decomposed into two parts:
- the sum of all elements over all non-empty subsequences,
- plus the sum of averages of all non-empty subsequences.
The first part is straightforward. Each element $$$a_i$$$ appears in exactly $$$2^{n-1}$$$ non-empty subsequences, hence
For the second part, note that $$$a_i$$$ contributes to subsequences of length $$$k$$$ exactly $$$\binom{n-1}{k-1}$$$ times, and in such subsequences its coefficient in the average is $$$\frac{1}{k}$$$. Therefore,
It is easy to verify that
Hence the second part equals
Combining both parts, if we denote
the answer to a type $$$3$$$ query is
Thus, it is sufficient to maintain the values of $$$n$$$ and $$$S$$$. Since all computations are done modulo $$$10^9+7$$$, we maintain:
- $$$S \bmod (10^9+7)$$$,
- $$$n \bmod (10^9+7)$$$,
- $$$n \bmod (10^9+6)$$$ (for computing powers of $$$2$$$).
Updating $$$S$$$ and $$$n$$$ for queries of type $$$2$$$ is trivial. Updating $$$n$$$ for queries of type $$$1$$$ is also straightforward. The only non-trivial part is determining which element is removed in a type $$$1$$$ query in order to update $$$S$$$.
To handle this, consider a type $$$2$$$ query inserting a value $$$x$$$. There are two cases.
- If the current length of $$$a$$$ is odd ($$$2n+1$$$), after insertion the array becomes
The first time the middle element is removed, it is the original middle element of $$$a$$$. The next two times, the removed element is $$$x$$$. After that, the situation is equivalent to applying the same process to the array obtained by removing the middle element of $$$a$$$.
- If the current length of $$$a$$$ is even ($$$2n$$$), after insertion the array becomes
The first removed middle element is $$$x$$$, the second one is the original middle element of $$$a$$$ (namely $$$a_{n+1}$$$), and afterwards the situation again reduces to the same process on the array with its middle element removed.
Using this observation, we maintain a list of all values added by type $$$2$$$ queries, in order. For each such value we store an integer state in $$${0,1,2,3}$$$. When a new value $$$x$$$ is inserted:
- if the current length is odd, we assign it state $$$3$$$,
- otherwise, we assign it state $$$1$$$.
When processing a type $$$1$$$ query, we traverse this list from the end. For each element:
- if its state is $$$0$$$ or $$$1$$$, this element is the current middle element; we update its state to $$$(\text{state}+1)\bmod 4$$$ and return its value,
- otherwise, we only update its state to $$$(\text{state}+1)\bmod 4$$$ and continue.
This procedure finds the middle element in $$$O(1)$$$ amortized time per query.
Therefore, the overall time complexity of the solution is $$$O(q \log M)$$$.
#include <bits/stdc++.h>
using namespace std;
long long pw(long long a , long long b , long long mod){
long long ret = 1;
long long mul = a;
while(b > 0){
if(b&1)
ret = (ret * mul) % mod;
mul = (mul * mul) % mod;
b >>= 1;
}
return ret;
}
const int mod = 1e9 + 7;
int q;
int sum = 0 , lenm = 0 , lenm1 = 0 , len2 = 0;
vector<pair<int,int>> adds; // stay stay pass pass
int get(int id , int del = 1){
assert(id >= 0);
if(adds[id].second < 2){
if(del) adds[id].second = (adds[id].second + 1) & 3;
return adds[id].first;
}
else{
if(del) adds[id].second = (adds[id].second + 1) & 3;
return get(id-1 , del);
}
}
int main()
{
ios::sync_with_stdio(false) , cin.tie(0);
int tt;
cin >> tt;
while(tt--){
cin >> q;
sum = 0 , lenm = 0 , lenm1 = 0 , len2 = 0;
adds.clear();
while(q--){
int tp;
cin >> tp;
if(tp == 1){
sum = (sum - get(adds.size()-1 , 1) + mod) % mod;
lenm = (lenm - 1 + mod) % mod;
lenm1 = (lenm1 - 1 + (mod-1)) % (mod-1);
len2 ^= 1;
}
else if(tp == 2){
int x;
cin >> x;
if(len2 == 1) adds.push_back({x , 3});
else adds.push_back({x , 1});
sum = (sum + 1ll * (lenm + 1) * x) % mod;
lenm = (2 * lenm + 1) % mod;
lenm1 = (2 * lenm1 + 1) % (mod-1);
len2 = 1;
}
else if(tp == 3){
int ans = (pw(2 , (lenm1 - 1 + (mod-1)) % (mod-1) , mod) + 1ll * (pw(2 , lenm1 , mod) - 1) * pw(lenm , mod-2 , mod)) % mod;
ans = (1ll * ans * sum) % mod;
ans = (1ll * ans * pw(2 , mod-2 , mod)) % mod;
cout << ans << endl;
}
}
}
return 0;
}
2180H1 - Bug Is Feature (Unconditional Version)
Idea: Akulyat — Preparation: MohammadParsaElahimanesh
Step 1: reduce to independent series.
First, we can split the whole match into independent series $$$(a_i,b_i,c_i,[l_i,r_i])$$$. Since moves never mix two different games, by the Sprague-Grundy theorem we can compute the Grundy number contributed by each series and then solve the question.
Step 2: normalize one game.
Fix one game with upper bound $$$x$$$. Shift everything by $$$a$$$:
Because $$$a,b,c$$$ are an arithmetic progression, we have $$$c-a=2(b-a)$$$. Put $$$d=b-a$$$ and $$$y=x-a$$$, so the state starts as
Any move keeps the three numbers in an arithmetic progression (after reordering). In this normalized form, every legal move transforms $$$(0,\ d,\ 2d,\ y)$$$ into exactly one of the following forms: - $$$(d,\ 2d,\ 3d,\ y)$$$, - $$$(0,\ 2d,\ 4d,\ y)$$$, - $$$(d,\ \tfrac{3d}{2},\ 2d,\ y)$$$ when $$$d$$$ is even.
Step 3: parameters $$$(t,d)$$$ and then $$$(q,k)$$$.
It is convenient to measure the remaining room under $$$y$$$:
Then the game state is represented by $$$(t,d)$$$.
Write
and define
After this, the game depends only on $$$(q,k)$$$. We denote its Grundy number by $$$g(q,k)$$$.
Step 4: large ranges collapse to a few ranges of $$$q$$$.
In a fixed series, $$$d$$$ is fixed, hence $$$k$$$ and $$$D$$$ are fixed. As $$$x$$$ runs through $$$[l_i,r_i]$$$, the value $$$t=x-c_i$$$ runs through an interval $$$[L,R]$$$ where $$$L=l_i-c_i$$$ and $$$R=r_i-c_i$$$, and we look at
This $$$q$$$ stays constant on blocks of consecutive $$$D$$$ values, and the full blocks have length $$$D$$$. Since $$$D$$$ is odd, the contribution of the whole interval $$$t\in[L,R]$$$ can be reduced to:
one consecutive interval of $$$q$$$ values corresponding to full blocks,
at most two boundary blocks (the beginning and the end), treated separately.
Step 5: recursion for $$$g(q,k)$$$.
From the move description on $$$(q,k)$$$, we can write
Two facts make it easy to work with:
the third term is never needed, so $$$g(q,k)=\mathrm{mex}\Big(g(q-2^k,k),\ g(q,k-1)\Big)$$$.
for fixed $$$k$$$, the sequence $$$g(0,k),g(1,k),\ldots$$$ is periodic with period $$$2^{k+1}$$$.
Using the first fact, we get a simple split:
- if $$$q \lt 2^k$$$, then $$$g(q-2^k,k)$$$ does not exist, so $$$g(q,k)=\mathrm{mex}\Big({g(q,k-1)}\Big)$$$.
- if $$$q\ge 2^k$$$, then $$$g(q,k)=\mathrm{mex}\Big({g(q,k-1),\ g(q-2^k,k)}\Big)$$$.
Step 6: reduce interval XOR to prefix XOR.
In each series we need
Define the prefix XOR
Then
Step 7: compute $$$f(u,k)$$$ as a small tuple.
We save $$$f(u,k)$$$ as a tuple
where $$$p_i=1$$$ means the value $$$i$$$ has an odd contribution in
In other words, $$$p_i$$$ tells whether $$$i$$$ appears an odd number of times among $$$g(0,k),\ldots,g(u,k)$$$.
We first precompute the XOR over one full period
Since the period is $$$2^{k+1}$$$, two full consecutive periods cancel in XOR, so the XOR over length $$$2^{k+2}$$$ becomes $$$(0,0,0)$$$. Therefore, for a general $$$u$$$ we reduce it to the remainder inside a single period, and then compute it by recursion on $$$k$$$ from the formulas in Step 5. This makes computing $$$f(u,k)$$$ fast, in $$$O(k)=O(\log u)$$$ time.
// In the name of God
#include <iostream>
using namespace std;
#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
inline ll lg2(ll x){return 63 - __builtin_clzll(x);}
constexpr inline ll period(ll k) {return 1LL<<(k+1);}
constexpr inline ll half_period(ll k) {return 1LL<<k;}
inline ll equivalent(ll x, ll k) {return x & (period(k)-1);}
inline bool count_period_parity(ll x, ll k) {return (x >> (k+1)) & 1;}
struct node {
int u;
node(bool zero, bool one, bool two) {
u = ((int) zero << 0) + ((int) one << 1) + ((int) two << 2);
}
node(int x) {
u = x;
}
bool has(int i) const {return u & (1<<i);}
node Mex() const {
return node(has(1) ^ has(2), has(0), false);
}
node MexMex() const {
return node(false, has(2), has(0) ^ has(1));
}
node operator^(const node other) const {
return node(u ^ other.u);
}
void operator^=(const node other) {
u ^= other.u;
}
int get() const {
return (u >> 1);
}
};
const node full_period(true, true, false);
const node full_period_mex = full_period.Mex();
const node zero_node(false, false, false);
const node zero(true, false, false), one(false, true, false), two(false, false, true);
node grundy(ll x, ll k) {
if(k)
return equivalent(x, k) < half_period(k)? grundy(x, k-1).Mex() : grundy(x, k-1).MexMex();
return x&1? one : zero;
}
node prefix_grundy(ll r, ll k) {
node period_effect = (count_period_parity(r, k)? full_period : zero_node);
r = equivalent(r, k);
if(k == 0)
return (r? full_period : zero) ^ period_effect;
if(r < half_period(k))
return prefix_grundy(r, k-1).Mex() ^ period_effect;
return prefix_grundy(r - half_period(k), k-1).MexMex() ^ full_period_mex ^ period_effect;
}
inline node grundy(ll l, ll r, ll k) {
return (l? prefix_grundy(l-1, k) : zero_node) ^ prefix_grundy(r, k);
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int n;
int t;
cin >> t;
while(t--) {
cin >> n;
node ans(0);
for(ll a, b, c, l, r, lp, rp, d, k, i = 0; i < n; i++) {
cin >> a >> b >> c >> l >> r;
b -= a, c -= a, l -= a, r -= a, a = 0;
l -= c, r -= c;
k = lg2(b & -b), d = b >> k;
if(l / d == r / d) {
if((r - l + 1) & 1)
ans ^= grundy(l / d, k);
} else {
lp = (l+d-1) / d, rp = r / d;
if(lp < rp) ans ^= grundy(lp, rp-1, k);
if((lp*d-l)&1) ans ^= grundy(l / d, k);
if((r-rp*d+1)&1) ans ^= grundy(r / d, k);
}
}
cout << (ans.get()? "Bug" : "Feature") << '\n';
}
return 0;
}
// Thank God
2180H2 - Bug Is Feature (Conditional Version)
Idea: MohammadParsaElahimanesh, AmirrzwM, Shayan — Preparation: MohammadParsaElahimanesh
Step 1: Game Transformation.
Convert each game with $$$a_i \lt b_i \lt c_i \le x$$$ to analyze $$$0 \lt 1 \lt 2 \le x'$$$ where:
The interval $$$[l_i, r_i]$$$ transforms to
Note that each $$$x' \in [L_i, R_i]$$$ corresponds to multiple original $$$x$$$ values (the number of originals can change near the interval endpoints). From state $$$x'$$$, a player can move either to $$$x'-1$$$ or to $$$\left\lfloor \frac{x'}{2} \right\rfloor$$$. The game ends when $$$x'=2$$$, and the player who makes the last move wins.
Step 2: Grundy Numbers.
Define $$$g(x)$$$ for state $$$0 \lt 1 \lt 2 \le x$$$:
- Base cases:
- Recursive rule ($$$x \ge 4$$$):
Key properties (proven by induction):
- $$$g(x) = 0$$$ $$$\iff$$$ $$$x$$$ has odd trailing zeros in binary
- Non-zero $$$g(x)$$$ alternate $$$1 \leftrightarrow 2$$$ sequentially
Step 3: Counting Grundy Values.
For any interval $$$[l, r]$$$:
Count numbers with $$$g(x) = 0$$$:
- Define $$$C(y) =$$$ count of $$${x \le y \mid g(x) = 0}$$$
- Loop through bits to compute $$$C(y)$$$ in $$$O(\log y)$$$
- Zeros in $$$[l, r]$$$: $$$C(r) - C(l-1)$$$
Count $$$1$$$'s and $$$2$$$'s similarly using $$$C(y)$$$ and alternation of $$$1$$$ and $$$2$$$.
Step 4: Final Computation.
For each transformed interval $$$[L_i, R_i]$$$:
- Compute XOR of all $$$g(x)$$$ in $$$[L_i, R_i]$$$
- Aggregate XOR across all $$$n$$$ queries
- Total XOR $$$\neq 0 \implies$$$ Bug wins; else Feature wins
// In the name of God
#include <iostream>
using namespace std;
typedef long long ll;
inline ll count_zeros(ll x) {
int u = (x&2)>>1;
ll cnt = u;
while (x>>=2) {
u = (x&2)>>1;
cnt += x+u;
}
return cnt;
}
// normal grundy function
/*
inline int grundy(ll x) {
if((__builtin_ctzll(x)&1) == 1) return 0;
return 1+((x-count_zeros(x))&1);
}
*/
// magical function
inline int grundy(ll x) {
if((__builtin_ctzll(x)&1) == 1) return 0;
return 1+(__builtin_popcountll(x)&1);
}
inline int grundy(ll l, ll r) {
ll zel = count_zeros(l-1), zer = count_zeros(r);
ll onl = (l-1-zel)/2, onr = (r-zer)/2;
ll twl = (l-2-zel)/2, twr = (r-1-zer)/2;
return ((onr-onl)&1)^(((twr-twl)&1)<<1);
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int n, ans;
int t;
cin >> t;
while(t--) {
cin >> n;
ans = 0;
for(ll a, b, c, l, r, lp, rp, i = 0; i < n; i++) {
cin >> a >> b >> c >> l >> r;
b -= a, c -= a, l -= a, r -= a, a = 0;
if(l / b == r / b) {
if((r - l + 1)&1)
ans ^= grundy(l / b);
} else {
lp = (l+b-1)/b, rp = r/b;
if(b&1) ans ^= grundy(lp, rp-1);
if((lp*b-l)&1)ans ^= grundy(l/b);
if((r-rp*b+1)&1)ans ^= grundy(rp);
}
}
cout << (ans?"Bug":"Feature") << '\n';
}
return 0;
}
