## A — The Ultimate Square

Author: Gheal

**Hints**

**Hint 1**

If $$$n$$$ is odd, it is possible to create a square using all $$$n$$$ blocks.

**Hint 2**

If $$$n$$$ is even, it is possible to create a square using only the first $$$n-1$$$ blocks, since $$$n-1$$$ is odd. Can we use the last block to create a larger square?

**Solution**

If $$$n$$$ is odd, let $$$k=\frac{n+1}{2}$$$ be the width of the last block. It is possible to create a square of side length $$$k$$$ using every block as follows:

- Line $$$1$$$ contains a $$$1 \times k$$$ block;
- Line $$$2$$$ contains a $$$1 \times 1$$$ block and a $$$1 \times (k-1)$$$ block;
- Line $$$3$$$ contains a $$$1 \times 2$$$ block and a $$$1 \times (k-2)$$$ block;
- $$$\ldots$$$
- Line $$$i$$$ contains a $$$1 \times (i-1)$$$ block and a $$$1 \times (k-i+1)$$$ block;
- $$$\ldots$$$
- Line $$$k$$$ contains a $$$1 \times (k-1)$$$ block and a $$$1 \times 1$$$ block.

Since the area of this square is $$$k^2$$$, and the $$$n+1$$$-th block has a width of $$$k$$$ tiles, the total area of the first $$$n+1$$$ blocks is equal to $$$k^2+k \lt (k+1)^2$$$. Therefore, the answer for $$$n+1$$$ is also $$$k$$$.

In conclusion, the answer for each testcase is $$$\lfloor \frac{n+1}{2} \rfloor$$$.

Time complexity per testcase: $$$O(1)$$$.

**Code (C++)**

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void testcase(){
ll n;
cin>>n;
cout<<(n+1)/2<<'\n';
}
int main()
{
ll t; cin>>t; while(t--)
testcase();
return 0;
}
```

## B — Balanced Substrings

Author: Gheal

**Hints**

**Hint 1**

What is the maximum number of distinct characters in a diverse string?

**Hint 2**

What is the maximum frequency of a character in a diverse string?

**Hint 3**

What is the maximum possible length a diverse string?

**Solution**

In a diverse string, there are at most $$$10$$$ distinct characters: '0', '1', $$$\ldots$$$, '9'. Therefore, each of these characters can appear at most $$$10$$$ times in a diverse string.

With all this in mind, the maximum possible length of a diverse string is $$$10^2=100$$$. To solve this problem, we only need to check whether each substring of length $$$l \le 100$$$ is diverse.

Time complexity per testcase: $$$O(n \cdot 10^2)$$$

**Code(C++)**

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void tc(){
ll n;
string s;
cin>>n>>s;
ll ans=0;
for(ll i=0;i<s.size();i++){
int fr[10]{}, distinct=0, max_freq=0;
for(ll j=i;j<s.size() && (++fr[s[j]-'0'])<=10;j++){
max_freq=max(max_freq,fr[s[j]-'0']);
if(fr[s[j]-'0']==1) distinct++;
if(distinct>=max_freq) ans++;
}
}
cout<<ans<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll t; cin>>t; while(t--) tc();
return 0;
}
```

## C — Zero Sum Prefixes

**Hints**

**Hint 1**

What is the answer if $$$a_1=0$$$ and $$$a_i \neq 0$$$ for all $$$2 \le i \le n$$$?

**Hint 2**

What is the answer if $$$a_i=0$$$ and $$$a_j \neq 0$$$ for all $$$1 \le j \le n$$$, $$$j \neq i$$$?

**Hint 3**

What is the answer if there are only two indices $$$i$$$ and $$$j$$$ for which $$$a_i=a_j=0$$$?

**Solution**

Let's consider the prefix sum array $$$s=[a_1,a_1+a_2,\ldots,a_1+a_2+\ldots+a_n]$$$.

For every index $$$i$$$ such that $$$a_i=0$$$, if we change the value of $$$a_i$$$ to $$$x$$$, then every element from the suffix $$$[s_i,s_{i+1},\ldots,s_n]$$$ will be increased by $$$x$$$. Therefore, if $$$a_{i_1}=a_{i_2}=\ldots=a_{i_k}=0$$$, we'll partition array $$$s$$$ into multiple subarrays:

- $$$[s_1,s_2,\ldots,s_{i_1-1}]$$$;
- $$$[s_{i_1},s_{i_1+1},\ldots,s_{i_2-1}]$$$;
- $$$[s_{i_2},s_{i_2+1},\ldots,s_{i_3-1}]$$$;
- $$$\ldots$$$
- $$$[s_{i_k},s_{i_{k+1}},\ldots,s_n]$$$;

Since none of the elements from the first subarray can be changed, it will contribute with the number of occurences of $$$0$$$ in $$$[s_1,s_2,\ldots,s_{i_1-1}]$$$ towards the final answer.

For each of the other subarrays $$$[s_l,s_{l+1},\ldots,s_r]$$$, let $$$x$$$ be the most frequent element in the subarray, appearing $$$fr[x]$$$ times. Since $$$a_l=0$$$, we can change the value of $$$a_l$$$ to $$$-x$$$. In this case, every $$$x$$$ in this subarray will become equal to $$$0$$$, and our current subarray will contribute with $$$fr[x]$$$ towards the final answer.

Time complexity per testcase: $$$O(NlogN)$$$

**Code(C++)**

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=2e5+5;
ll a[MAXN];
map<ll,ll> freq;
void tc(){
ll n;
cin>>n;
ll maxfr=0,current_sum=0,ans=0;
bool found_wildcard=0;
freq.clear();
for(ll i=0;i<n;i++){
cin>>a[i];
if(a[i]==0){
if(found_wildcard) ans+=maxfr;
else ans+=freq[0];
found_wildcard=1;
maxfr=0,freq.clear();
}
current_sum+=a[i];
maxfr=max(maxfr,++freq[current_sum]);
}
if(found_wildcard) ans+=maxfr;
else ans+=freq[0];
cout<<ans<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(0);
ll t; cin>>t; while(t--)
tc();
return 0;
}

## D — ConstructOR

Author: Gheal

**Hints**

**Hint 1**

If at least one of $$$a$$$ and $$$b$$$ is odd, and $$$d$$$ is even, then there are no solutions.

**Proof**

Without loss of generality, we will only consider the case when $$$a$$$ is odd and $$$d$$$ is even. Since the last bit of $$$a$$$ is $$$1$$$, then the last bit of $$$a|x$$$ must also be $$$1$$$.

Therefore, $$$a|x$$$ cannot be a multiple of $$$d$$$, as $$$a|x$$$ is odd, while $$$d$$$ is even.

Note that there are more cases in which no solutions exist, however they are more generalised versions of this case.

**Hint 2**

If a triplet ($$$a,b,d$$$) has no solutions, then ($$$a\cdot 2,b\cdot 2,d\cdot 2$$$) has no solutions as well.

Combined with the first hint, we can say that a triplet ($$$a,b,d$$$) has no solutions if $$$min(\text{lsb}(a),\text{lsb}(b)) \lt \text{lsb}(d)$$$. Here, $$$\text{lsb}(x)$$$ represents the least significant bit of $$$x$$$.

**Hint 3**

Since both $$$a|x$$$ and $$$b|x$$$ must be divisible by $$$d$$$, it's better to choose an $$$x$$$ such that $$$a|x=b|x=x$$$.

**Hint 4**

If $$$d$$$ is odd, since $$$a,b \lt 2^{30}$$$, we can ensure that $$$a|x=b|x=x$$$ by setting the last $$$30$$$ bits of $$$c$$$ to $$$1$$$.

If $$$d$$$ is even, then the last $$$\text{lsb}(d)$$$ bits of $$$x$$$ should be set to $$$0$$$, while the other bits from the last $$$30$$$ bits should be set to $$$1$$$. Here, $$$\text{lsb}(x)$$$ represents the least significant bit of $$$x$$$.

**Solution**

Let $$$k=\text{lsb}(d)$$$, where $$$\text{lsb}(d)$$$ represents the least significant bit of $$$d$$$.

Since $$$a|x$$$ and $$$b|x$$$ are multiples of $$$d$$$, the last $$$k$$$ bits of $$$a$$$ and $$$b$$$ (and also $$$x$$$) must be equal to $$$0$$$.

Otherwise, there are no solutions and we can print $$$-1$$$.

To simplify the construction process, we will try to find some $$$x$$$ such that $$$a|x=b|x=x$$$. Since we already know that the last $$$k$$$ bits of $$$a$$$, $$$b$$$ and $$$x$$$ are $$$0$$$, we will consider that the other $$$30-k$$$ of the $$$30$$$ least significant bits of $$$x$$$ are equal to $$$1$$$:

This gives the following general formula for $$$x$$$:

Now, we'll try to find some $$$p$$$ for which $$$x$$$ is a multiple of $$$d=2^k \cdot d'$$$:

Time complexity per testcase: $$$O(log d)$$$

Note that if $$$a|b$$$ is already a multiple of $$$d$$$, we can consider $$$x=a|b$$$.

**Code(C++)**

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void tc(){
ll a,b,d,k=0,inverse_of_2,total_inverse=1;
cin>>a>>b>>d;
a|=b;
if(a%d==0){
cout<<a<<'\n';
return;
}
while(a%2==0 && d%2==0)
a/=2,d/=2,k++;
inverse_of_2=(d+1)/2;
if(a%2==1 && d%2==0){
cout<<"-1\n";
return;
}
for(ll i=0;i<30-k;i++)
total_inverse=total_inverse*inverse_of_2%d;
cout<<((total_inverse<<(30-k))-1)*(1ll<<k)<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(0);
ll t; cin>>t; while(t--)
tc();
}
```

## E — Yet Another Array Counting Problem

Author: Gheal

**Hints**

**Hint 1**

Let $$$m$$$ be the position of the leftmost maximum on the segment $$$[1;n]$$$.

If $$$l \le m \le r$$$, then the position of the leftmost maximum on the segment $$$[l;r]$$$ is equal to $$$m$$$.

If $$$l \le r \lt m $$$, then the leftmost maximum on the segment $$$[l;r]$$$ is some element $$$a_p$$$, $$$p \lt m$$$.

If $$$m \lt l \le r$$$, then the leftmost maximum on the segment $$$[l;r]$$$ is some element $$$a_{p_2}$$$, $$$p_2 \gt m$$$.

**Hint 2**

Let $$$m$$$ be the position of the leftmost maximum on the segment $$$[l;r]$$$.

If $$$p$$$ is the position of the leftmost maximum on the segment $$$[l;m-1]$$$ and $$$p_2$$$ is the position of the leftmost maximum on the segment $$$[m+1;r]$$$, then $$$b_m \gt b_{p}$$$ and $$$b_m \ge b_{p_2}$$$.

**Hint 3**

Using the idea from the previous hint, we can recursively build a binary tree where the children of node $$$m$$$ are nodes $$$p$$$ and $$$p_2$$$.

**Hint 4**

Can this problem be boiled down to a tree dp? (Note that $$$n \cdot m \le 10^6$$$)

**Solution**

Let $$$f(i,j)$$$ be the position of the leftmost maximum in the interval $$$(i;j)$$$, $$$1 \le i \le j \le n$$$.

Let's consider an interval $$$(l;r)$$$ such that $$$f(l,r)=m$$$. For the sake of simplicity, let's assume that $$$l \lt m \lt r$$$.

Let $$$p=f(l,m-1)$$$ and $$$p_2=f(m+1,r)$$$. Since $$$a_m$$$ is the leftmost maximum in $$$(l;r)$$$, $$$p \lt m$$$ and $$$p_2 \gt m$$$, the following conditions must hold for array $$$b$$$:

- $$$b_m \gt b_p$$$
- $$$b_m \ge b_{p_2}$$$

Let's consider a binary tree where the children of node $$$u=f(l,r)$$$ are nodes $$$p=f(l,u-1)$$$ and $$$p_2=f(u+1,r)$$$, for every $$$1 \le u \le n$$$.

Note that if $$$u=l$$$, $$$f(l,l-1)$$$ is not defined, and, as such, node $$$u$$$ will have no left child. Similarly, if $$$u=r$$$, then node $$$u$$$ will have no right child.

Let $$$dp[u][x]$$$ be equal to the number of ways to assign values to every element $$$b_v$$$ from the subtree rooted in $$$u$$$, if $$$b_u=x$$$.

- If $$$u$$$ has a left child and $$$x=1$$$, then $$$dp[u][x]=0$$$;
- Otherwise, if $$$u$$$ has two children, then $$$dp[u][x]=(\sum_{i=1}^{x-1}dp[p][i]) \cdot(\sum_{i=1}^{x}dp[p_2][i])$$$;
- If $$$u$$$ only has a left child, then $$$dp[u][x]=\sum_{i=1}^{x-1}dp[p][i]$$$;
- If $$$u$$$ only has a right child, then $$$dp[u][x]=\sum_{i=1}^{x}dp[p_2][i]$$$;
- If $$$u$$$ has no children, then $$$dp[u][x]=1$$$.

To optimise the transitions, we'll also need to compute $$$sum[u][x]=\sum_{i=1}^{x} dp[u][x]$$$ alongside our normal $$$dp$$$.

Intended time complexity per testcase: $$$O(n \cdot m+n \cdot log(n))$$$

**Additional implementation details**

In order to construct the binary tree, we can use a recursive divide and conquer function $$$divide(l,r)$$$ to split our current interval $$$(l;r)$$$ into two new intervals $$$(l;m-1)$$$ and $$$(m+1;r)$$$.

Additionally, we can also compute the values of $$$dp[m][x]$$$ and $$$sum[m][x]$$$ inside $$$divide(l,r)$$$ after calling $$$divide(l,m-1)$$$ and divide $$$(m+1,r)$$$.

Range leftmost maximumum queries can be answered in $$$O(1)$$$ using a sparse table, see the model solution for more information.

**Code(C++)**

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NMAX=2e5+5,LGMAX=18,MOD=1e9+7;
int n,m;
int leftmost_maximum[LGMAX][NMAX],msb[NMAX];
int v[NMAX];
vector<vector<ll>> dp,sum;
int leftmost_maximum_query(int l, int r){
int bit=msb[r-l+1];
if(v[leftmost_maximum[bit][l]]>=v[leftmost_maximum[bit][r-(1<<bit)+1]]) return leftmost_maximum[bit][l];
else return leftmost_maximum[bit][r-(1<<bit)+1];
}
int divide(int l, int r){
if(l>r) return -1;
int mid=leftmost_maximum_query(l,r);
int p=divide(l,mid-1),p2=divide(mid+1,r);
for(int i=1;i<=m;i++){
if(p!=-1 && i==1) dp[mid][1]=0;
else dp[mid][i]=(p>=0?sum[p][i-1]:1ll)*(p2>=0?sum[p2][i]:1ll)%MOD;
sum[mid][i]=(sum[mid][i-1]+dp[mid][i])%MOD;
}
return mid;
}
void tc(){
cin>>n>>m;
dp.resize(n),sum.resize(n);
for(int i=0;i<n;i++){
cin>>v[i];
leftmost_maximum[0][i]=i;
dp[i].resize(m+1),sum[i].resize(m+1);
for(int j=0;j<=m;j++) dp[i][j]=sum[i][j]=0;
}
for(int bit=1;bit<LGMAX;bit++){
for(int i=0;i+(1<<bit)<=n;i++){
if(v[leftmost_maximum[bit-1][i]]>=v[leftmost_maximum[bit-1][i+(1<<(bit-1))]])
leftmost_maximum[bit][i]=leftmost_maximum[bit-1][i];
else
leftmost_maximum[bit][i]=leftmost_maximum[bit-1][i+(1<<(bit-1))];
}
}
divide(0,n-1);
cout<<sum[leftmost_maximum_query(0,n-1)][m]<<'\n';
}
int main()
{
for(int i=2;i<NMAX;i++)
msb[i]=msb[i-1]+((i&(i-1))==0); /// msb = floor(log2)
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t; cin>>t; while(t--)
tc();
return 0;
}
```

## F — Circular Xor Reversal

**Hints**

**Hint 1**

How can we perform $$$a_i=a_i \oplus a_j$$$ for any $$$0 \le i,j \lt n$$$, $$$i \neq j$$$?

**Hint 2**

We can swap the values of $$$a_i$$$ and $$$a_j$$$ by performing the following sequence of xor assignments:

- $$$a_i=a_i \oplus a_j$$$;
- $$$a_j=a_j \oplus a_i$$$;
- $$$a_i=a_i \oplus a_j$$$;

**Hint 3**

Performing $$$a_i=a_i \oplus a_j$$$ on its own is pretty wasteful, as it requires $$$4 \cdot \text{dist}(i,j) - c$$$ operations, where $$$dist(i,j)=(j+n-i) \mod n$$$, and $$$c$$$ is a constant.

If $$$j=i+3$$$, can we perform $$$a_i=a_i \oplus a_j$$$ and $$$a_{i+1}=a_{i+1} \oplus a_{j-1}$$$ simultaneously?

**Hint 4**

Building on the idea presented in hint $$$3$$$, can we perform the following $$$\frac{n}{2}$$$ xor assignments simultaneously if $$$n$$$ is even?

- $$$a_0 = a_0 \oplus a_{n-1}$$$;
- $$$a_1 = a_1 \oplus a_{n-2}$$$;
- $$$a_2 = a_2 \oplus a_{n-3}$$$;
- $$$\ldots$$$
- $$$a_{\frac{n}{2}-1} = a_{\frac{n}{2}-1} \oplus a_{\frac{n}{2}}$$$

The target number of operations for performing all $$$\frac{n}{2}$$$ assignments is $$$\frac{n^2}{2}$$$.

**Hint 5**

Using hints $$$2$$$ and $$$4$$$, we can already solve the problem if $$$n$$$ is even.

If $$$m=dist(i,j) \gt 0$$$ and $$$b_k=a_{(i+k) \mod n}$$$, let $$$f(i,j)$$$ be a sequence of operations that performs:

- $$$b_0 = b_0 \oplus b_{m}$$$;
- $$$b_1 = b_1 \oplus b_{m-1}$$$;
- $$$b_2 = b_2 \oplus b_{m-2}$$$;
- $$$\ldots$$$
- $$$b_{\lfloor\frac{m-2}{2} \rfloor } = b_{\lfloor \frac{m-1}{2} \rfloor} \oplus b_{\lfloor \frac{m+2}{2} \rfloor}$$$

We can reverse array $$$a$$$ by performing $$$f(0,n-1)$$$, $$$f(\frac{n}{2},\frac{n}{2}-1)$$$ and $$$f(0,n-1)$$$, in this order.

Otherwise, if $$$n$$$ is odd, we can perform $$$f(0,n-1)$$$, $$$f(\frac{n+1}{2},\frac{n-3}{2})$$$ and $$$f(0,n-1)$$$, in this order.

The total number of operations is $$$3\cdot \frac{n^2}{2} \le 3 \cdot \frac{400^2}{2} = 240\,000 \lt 250\,000$$$.

**Solution**

If $$$m=dist(i,j)=((j+n-i) \mod n)$$$, $$$m \gt 0$$$ and $$$b_k=a_{(i+k) \mod n}$$$, let $$$f(i,j)$$$ be a sequence of operations that performs:

- $$$b_0 = b_0 \oplus b_{m-1}$$$;
- $$$b_1 = b_1 \oplus b_{m-2}$$$;
- $$$b_2 = b_2 \oplus b_{m-3}$$$;
- $$$\ldots$$$
- $$$b_{\lfloor\frac{m-1}{2} \rfloor } = b_{\lfloor \frac{m-1}{2} \rfloor} \oplus b_{\lfloor \frac{m+2}{2} \rfloor}$$$

If $$$n$$$ is even, we can reverse array $$$a$$$ by performing $$$f(0,n-1)$$$, $$$f(\frac{n}{2},\frac{n}{2}-1)$$$ and $$$f(0,n-1)$$$, in this order.

Otherwise, if $$$n$$$ is odd, we can perform $$$f(0,n-1)$$$, $$$f(\frac{n+1}{2},\frac{n-3}{2})$$$ and $$$f(0,n-1)$$$, in this order.

One possible way to construct $$$f(i,j)$$$ is as follows:

- Perform an operation on every $$$i$$$ from $$$m-1$$$ to $$$0$$$:

- Perform an operation on every $$$i$$$ from $$$1$$$ to $$$m-1$$$:

- Perform an operation on every $$$i$$$ from $$$m-2$$$ to $$$1$$$:

- Perform an operation on every $$$i$$$ from $$$2$$$ to $$$m-2$$$:

- $$$\ldots$$$

- The last step is to perform an operation on every $$$i$$$ from $$$0$$$ to $$$\lfloor\frac{m-2}{2}\rfloor$$$:

Here, $$$(l..r)$$$ denotes $$$b_l \oplus b_{l+1} \oplus \ldots \oplus b_r$$$.

The number of operations needed for $$$f(i,j)$$$ is equal to $$$m+(m-1)+\ldots+1+(\frac{m}{2})=\frac{m\cdot(m+1)}{2}+\frac{m}{2}=\frac{m^2+2\cdot m}{2}$$$, therefore the total number of operations needed to reverse the array is $$$\frac{3}{2} \cdot (m^2+2\cdot m)$$$. Since $$$m \le n-1$$$, $$$\frac{3}{2} \cdot (m^2+2\cdot m) \le \frac{3}{2} \cdot (399^2 + 2\cdot 399) \lt 250\,000$$$.

Time complexity per testcase: $$$O(N^2)$$$

**Code(C++)**

#include <bits/stdc++.h>
using namespace std;
vector<int> ans;
int n;
void add_op(int pos){
ans.push_back(pos%n);
}
void f(int l, int r){
if(r<l) r+=n;
int m=r-l,direction=0,start=l;
r--;
while(l<=r){
if(direction==0){
for(int i=r;i>=l;i--)
add_op(i);
l++;
}
else{
for(int i=l;i<=r;i++)
add_op(i);
r--;
}
direction=1-direction;
}
for(int i=start;i<start+m/2;i++)
add_op(i);
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(0);
cin>>n;
f(0,n-1);
f((n+1)/2,(n-2)/2);
f(0,n-1);
cout<<ans.size()<<'\n';
for(auto it : ans) cout<<it<<' ';
}

If there is anything wrong or unclear in this editorial, feel free to ping me in the comments.

Good Round! Thanks for the fast editorial!

bro how to achieve graph like you what are you doing

They had probably done CP on other websites before starting on Cofedorces, or at least they had had experience with math and problem solving in programming, maybe also some algorithms.

Actually I believe it's an alt bro

My Solution for D:

Check no solution:Note $$$cal(x)=max(i),2^i|x$$$,if $$$cal(d)>min(cal(a),cal(b))$$$,no solution.

Otherwise,Let's construct the solution.

First,let $$$d»=cal(d),a»=cal(d),b»=cal(d)$$$,calculate the $$$x$$$ for the new $$$a,b,d$$$.When outputting the answer, we only need to output $$$2^{cal(d)}x$$$.

How to construct such $$$x$$$?The key point is make $$$x=(2^{key}-1)+2^{key}X$$$,($$$key=30-cal(d)$$$).

This is actually a problem of solving congruence equations:$$$(2^{key}-1)+2^{key}X=0(mod\space d)$$$,use exgcd to get such $$$X$$$.

Here is another solution for D:

If $$$min(lsb(a),lsb(b))<lsb(d)$$$, there is no solution. Because $$$lsb(d*k)>=lsb(d)$$$ so their $$$lsb$$$ can never be equal. Hence, they can't also be equal.

Otherwise; let $$$ans = 0$$$ initially, we want to fill bits of $$$ans$$$ such that it will be multiple of d, and $$$ans$$$ will be *superset of $$$a|b$$$.

Let's iterate over bits of $$$ans$$$ $$$0$$$ to $$$29$$$

If $$$i$$$'th bit of $$$ans$$$ is $$$0$$$ then add $$$d * (2^{i-lsb(d)})$$$ to $$$ans$$$. Now that bit will be $$$1$$$ and it will contain $$$a|b$$$ anyway.

Since $$$d$$$ has at most $$$30$$$ bits and our target is to fill first $$$30$$$ bits and there must be an intersection, our answer will require at most $$$30+30-1=59$$$ bits and this fits constraints!

Here is my submission.

(*Note : $$$X$$$ is superset of $$$Y$$$ if $$$Y$$$ is subset of $$$X$$$.)

tallbee23 "If i'th bit .... contain a|b anyway." Can you please explain this line? Like how did you come up with this approach?

If $$$i$$$'th bit of $$$ans$$$ is $$$0$$$, when we add $$$d*(2^{i-lsb(d)}$$$ to $$$ans$$$, actually we shifted $$$d$$$ to intersect $$$lsb(d)$$$ with that bit. Since $$$lsb(d)=2^{i}$$$ and $$$2^i$$$ & $$$ans = 0$$$ after shifting, if we gather them then $$$i$$$'th bit will be $$$1$$$. Since we filled first $$$30$$$ bits with $$$1$$$, it will be superset of $$$a|b$$$.

Actually first $$$30$$$ bits except bits that is

smallerthan $$$lsb(d)$$$ are $$$1$$$. But since $$$lsb(d) \le lsb(a|b)$$$, it is meaningless. There is no bit such that $$$bit$$$ & $$$(a|b) = 1$$$ and $$$bit$$$ & $$$ans = 0$$$.I wrote above comment incorrectly you must to start from $$$lsb(d)$$$ instead of $$$0$$$but when coding it,`(1LL<<bit)`

gives $$$0$$$ if $$$bit$$$ is negative. So you can start from $$$0$$$ too if you used shifting that way.Problem D can also be solved using Chinese Remainder Theorem. First step is the same as stated in solution given above: proccess cases, when answer is -1, and then you can just find X, s.t. X = a|b (mod 2^30), and X = 0 (mod d'). Where d' comes from d = 2^i * d', where d' is odd. The answer is under 2^60, since 2^30*d < 2^30*2^30 = 2^60

I used the same approach as yours but getting wrong answer. if p=a|b and prod=(1l<<30)*d, i used x=p*(prod/(1l<<30))*inv(prod/(1l<<30))%(1l<<30)+d*(prod/d)*inv(prod/d)%d

x%=prod

181039686

Can you explain the crt method in your code? I did like usual chinese remainder theorem and to take an account that x is congruent to 0 mod d. I took the remainder 0 as d and did normal chinese remainder theorem. It did not work. I saw that you are doing something in reverse fashion, but could not understand it. I appreciate your idea anyway! Thanks and eagerly waiting for your reply and my submission is at above comment.

Basically, I used Garner's alrorithm for 2 co-prime numbers: d' and 2^30. You can read more about that here: https://cp-algorithms.com/algebra/chinese-remainder-theorem.html#garners-algorithm I don't really know what is wrong with your formula above, since it's quite messy, but maybe you can find your mistake by reading this article

oh, this is something new. Thanks for sharing this!

I finally got AC using your approach and normal congruence relation.

We have two congruence equations as

x=(a|b)mod(1l<<30) ---> 1

x=0mod(d') ---> 2

That means x=d'*k, replacing this in 1 gives

d'*k=(a|b)mod(1l<<30)

k=(a|b)(1/d')mod(1l<<30)

Solve this we can find k and k*d is the answer

Hope it might help someone.

Today i learned that if we have remainder 0 in chinese remainder theorem we can convert x into multiple of that modulus and solve it instead of doing normal chinese remainder theorem which might yield a wrong answer.

181131228

I think you are getting something wrong. There is only 1 chinese remainder theorem, but there is also an algorithm to construct the number from remainders modulo co-prime set of numbers. Chinese remainder theorem works for any remainders, as long as they are remainders modulo co-prime set of numbers. I don't understand what is normal chinese remainder theorem you are referring to.

Read this: https://math.stackexchange.com/questions/2617244/chinese-remainder-theorem-with-0-mod-n

I also used chinese remainder theorem, By normal i mean without changing x(but for some reason it did not work).

What worked is after changing x to k*d'

Not worked: Using chinese remainder theorem: 181039686

Worked: Using chinese remainder theorem but changing x to k*d' : 181131228

I could not find the mistake i made and i clearly stated in my previous comments. But after changing the equations it worked, i don't know why.

Take a look at Ticket 16436 from

CF Stressfor a counter example.thx, got x * 2^30 + (a|b) = 0 (or d) mod d => x * 2^30 = (d — (a|b) % d) mod d => x * 2^30 = c => x = c * inv(2^30,d)

I think the problem b was difficult than usual.

agree

Huge gap between A and B.

next time we will give all problems to have *800 so there won't be any impediments for people to AK

Problem A is so dumb, just look at it, a lot of people did it under 1 minute, which is time to read the statement alone. Its enough just to go to test cases and see the STUPID pattern

I agree. I do not understand why problemsetters include such problems. Such tasks punish participants who take the time to properly solve the problem (e.g. work out a few sample cases on their own, and figure out the $$$\lceil n/2\rceil$$$ relationship, rather than relying on sample cases to do it for you). Competitive programming should not be like this in my opinion.

Some would say pattern recognition is part of problem solving

I had the O(100*n) solution for B TLE: https://codeforces.com/contest/1748/submission/180630056 How come?

Same for C linear solution TLE: https://codeforces.com/contest/1748/submission/180643204

python is so slow

For C it's most likely this: https://codeforces.com/blog/entry/62393

testcase 8 I think is an anti hash test that's designed to cause as many collisions as possible in your dictionary setup. This results in the dictionary taking O(n) per lookup causing TLE.

For B I'm not entirely sure what's causing TLE but I don't think you need

`.strip`

for n and s. I also converted s from string to an int array initially so I wouldn't need to convert each character into int type excessively.181003922

Getting TLE on Linear solution for Problem C: Test Case 7

Have used unordered_map. If not to use hashing, then how to solve this one?

https://codeforces.com/blog/entry/62393

Looking at it test case 7 is also an anti hash test, specifically for c++ unordered map. you can still use hashing here but you you just need to define a custom hash function to reduce collisions.

Thank you for the reply. I have understood this now.

I'm pretty sure it's because you're doing max(d.values()). That's an inefficient implementation because the max operation is O(n). Instead, try maintaining a variable for the max value in the dictionary and see if that passes.

You're checking if current digit's freq is greater than 10 or not, it could be possible that it is repeated only once, in this case you will check for all substrings (not just 100). You need a length check instead of individual digit's freq check.

you think the solution is wrong? how did it pass all the 100 tests before the tle?

It isn't wrong. It's just inefficient. Replace the freq check with length check and it will produce the exact same output with less iterations.

https://codeforces.com/contest/1748/submission/180679051 Can you say where am i suppose to doing error , it gives me WA in testcase 2

you should try to define print = sys.stdout.write, it may decrease the time and instead of checking mx > 10, check if mx <= different values which is easily to find

I submitted your B with PyPy3, and it passed as usual, use PyPy if you're competing with Python

So that's how it is, so funny

Python is not very fast. It can be accelerated. Go to my profile, I sent the problem with your complete solution (after the round). Only I used acceleration. It went in a time that is 10 times less than the maximum.

Unfortunately, yes this contest is not suitable for python users, I was skeptical of both B and C, even though my idea was same. B bcoz its 10^7 operations, C bcoz it uses dictionary

Python is extremely slow on looping. While 1e8~1e9 loop iterations are acceptable with C++, in python this number is about 1e6~1e7.

E is easy but I have no time :(

use cartesian-tree and dp.

Looking at Um_nik's screencast, he only used 3 minutes (13:00 to 16:00) to read/think and 7 mins (16:00 to 23:00) to implement for E: https://www.youtube.com/watch?v=zdlrEs78gEQ&t=1004s

Makes me feel bad that I gave up 30 minutes into the contest and solved nothing else because I kept coming up with hard to implement solutions and thought I wouldn't have time (even though I had over an hour left). There's always enough time, just gotta gitgud

is it possible to solve B in python 3 , I see no accepted solutions. would be greatly appreciated if someone can help me with it. thanks

Check the solutions under PyPy3

Wow so fast tutorials .Great Contest .Problems were great . Thank u :)

I dont know why I'm experiencing a TLE for this code on my last pretest for problem C T_T any idea??

python is so slow

Read this

Just use the pypy3

Actually, the hash seems to matter here too. Idk the exact reason, but my O(n) code got accepted when I only changed the hash (thanks @DrMrogon https://codeforces.com/contest/1748/submission/180659676).

Before (TLE on test 8): https://codeforces.com/contest/1748/submission/180682651 After (Accepted): https://codeforces.com/contest/1748/submission/180683231

my python3 code alse TLE even on pypy3,no idea why

well,i changed the number to str and count in dictionary and then accepted like this:

Really nice round. I had guessed that if $$$min(lsb(a), lsb(b)) < lsb(d)$$$, it might be impossible in problem D but can't prove it. Could someone provide a proof of why that is always true?

$$$lsb(kd) \ge lsb(d)$$$ for any natural number $$$k$$$, i think?

but $$$min(lsb(a),lsb(b))<lsb(d)$$$ implies that $$$min(lsb(a\vert x),lsb(b\vert x))<lsb(d)$$$

I have proved it thanks to you. <3

please, can you share your proof?

Do the multiplication in binary, we multiply the decimal number $$$a$$$ and $$$b$$$, you will notice that the first bit which is set in the binary representation of the product is at least $$$max(lsb(a), lsb(b))$$$.

The $$$a$$$ and $$$b$$$ above are just for proof, don't confuse it with the $$$a$$$ and $$$b$$$ of problem.

With this, we can conclude that if $$$min(lsb(a | x), lsb(b | x)) \ge lsb(d)$$$ else it's impossible.

a|x and b|x should be of some form like k*d if they are divisible by d but if min(lsb(a), lsb(b))<lsb(d) But lsb(k*d)>=lsb(d) => min(lsb(a), lsb(b))<lsb(k*d)

So it is a contradiction. Hence in such case we can form a|x and b|x into some form like k*d. Thus no solution.

Am I the only one who stupidly used Euler's Theorem to find inverse modulo in D?

lol i do this every single time i need inverse modulo))

Can anyone explain me why am I getting TLE in Problem C here's my code https://codeforces.com/contest/1748/submission/180659944

Because of unordered_map.. change it to map only

After changing to map it got accepted but why ? I mean with unordered_map wasn't it O(n) and map O(nlogn)

Unordered map can be forced to operate in O(n^2).

Refer to this https://codeforces.com/blog/entry/62393

In worst case searching/insertion take o(n) time .. so ur complexity become o(n^2).

I choose

`GNU C++20 11.2.0(64 bit, winlibs)`

when I submit your code, and it's ok.My solution for B: for each i such that 1<=i<=n we find for each possible number of distinct elements what is the range L,R where this occurs. Then for each range we check where is the first index j such that the subarray [i,j] is bad, and subract R-j+1 from all possible subarrays. Time complexity is O(100nlogn) because we can find the ranges and check for bad subarrays using binary search. You can check my code to understand more

whats the expected rating for B?

Thanks for the fast editorial. I quite liked problems A-C. However, on problem D I feel like there should have been a constraint that D is a prime that is not 2. Because most of the ideas from D still apply, but finding the modular inverse is much easier. Or it could have also been split into an easier and harder version, with the easier one having D as a prime. I feel that C-D gap was quite large.

You can calculate composite inverses in $$$O(\log{m})$$$ as well. https://codeforces.com/blog/entry/103374?#comment-917844

I got AC using Euler's theorem. but the complexity was O(t * sqrt(d)). It would not be good to split this problem into two versions. They would be almost the same.

Why? We can simply use extended euclidean algorithm or a Euler's theorem right?

Yes, but that is much less known than modular inverse for prime modulo. And all other observations are more or less the same.

can anyone please explain problem B...

There are only 10 types of numbers, so the longest enumeration in a sequence is 100, and violence is sufficient

we can only have 10 distinct characters [0..9], so at max each can be repeated 10 times, so max length of diverse string can't be more than 100.

but the implemented solution is not straight forward.

for each i in [0..n], we are finding maximum x, in (i..n], such that sub array [i,x] has all of its character's frequency<=10, because it can't be diverse as per hints and above logic. while finding we are also updating maximum frequency of all characters and number of distinct characters each time, and also checking if in current state has distinct>=max_freq if so then we can say sub array from [0..j] is diverse.

this is run length counting, counting while running ^_^

1 second is too small for B, do better next time.

I cant solve b during contest, but still I think that it was a nice problem

Yeah I mean i am not able to solve B and C but this round teaches me some new concept .

Good and challenging round,tnx for the fast editorial. <3

I think my solution for D is somewhat simpler (at least for me) to understand:

First, it is impossible if the (where $$$lsb$$$ is the least significant bit) $$$lsb(a) \leq lsb(d)$$$ or $$$lsb(b) \leq lsb(d)$$$ because we are trying to find an $$$x$$$ such that $$$a|x$$$ and $$$b|x$$$ are both multiples of $$$d$$$. When we multiply a number $$$h$$$ by another $$$k$$$ and look at the result in binary, the result is the sum of multiplying the first by each of the bits of the second, which would imply that $$$lsb(h*k) \geq lsb(h)$$$ and $$$lsb(h*k) \geq lsb(k)$$$.

After we figure this out and deal with that case, the rest is easy. First lets say $$$m_i$$$ is the $$$i_{th}$$$ bit of $$$m$$$. We want to find a multiple of $$$d$$$ (lets call it $$$k$$$) where there is no bit $$$i$$$ such that $$$x_i=1$$$ and $$$k_i=0$$$. If we find this then all we need to do is apply a bitwise OR to $$$x$$$ in order to make $$$x=k$$$. This is always possible through the following algorithm:

Lets make $$$x=a|b$$$ and $$$k=d$$$ initally, then we iterate through the bits of both,

If $$$x_i=k_i$$$ then we can can ignore this bit.

If $$$x_i=1$$$ and $$$k_i=0$$$ we can left shift $$$d$$$ some number of times until the $$$lsb(d)$$$ is at the $$$i_{th}$$$ bit and then add this to $$$k$$$. This would not change any of the bits that we have already iterated over, would maintain that $$$k$$$ is a multiple of $$$d$$$, and would make $$$k_i=1$$$.

Now, there is no bit $$$i$$$ where $$$x_i=1$$$ and $$$k_i=0$$$, so we can just make $$$x = k$$$ by making $$$x=x|k$$$

Im pretty sure this is a naive solution compared to one using a single eqution but still I enjoyed coming up with it and think it is a little easier to understand.

I was having a very hard time understanding it Now I get it after reading your comment...really thx <3

Could u plz say what's does curr+=e does in ur code?

e was $$$d$$$ but right shifted until the $$$lsb(d)$$$ was at the first bit. The way I iterated through the bits of $$$k$$$ was by using a temporary variable for it and right shifting it continuously, only looking at it's first bit. So curr+=e is the same as adding $$$d$$$ to $$$k$$$ like I described in my solution.

My implementation was quite messy though because I rushed it before the contest ended so I wouldn't really bother trying to understand it.

Thanks a lot...Got it....

`We want to find a multiple of d (lets call it k) where there is no bit i such that xi=1 and ki=0.`

Why do we want to do this?

Because then we can make $$$x=k$$$ which would imply that $$$x$$$ is a multiple of $$$d$$$. I am also assuming that $$$x=a|b$$$ initally so this would then imply that $$$a|x$$$ and $$$b|x$$$ are both divisible by $$$d$$$.

Your solution really deserve to be the editorial for this problem instead of the huge misleading equations of the official editorial, Thanks. rfhalb

I did floor(ceil(n/2)) for problem A,(took n as double). Disappointed after seeing the simple (n+1)/2 solution as I failed to recognize pattern through testcase.

Actually they are the same concept .

`ceil(n,k)`

is`(n+k-1)/k`

if k==2 ceil(n,2) is (n+1)/2 That's all.

floor is the normal dividing :

`floor(n/k)`

is`n/k`

Ayy Tx

In problem F the number of operations can be improved from $$$\frac{3}{2} m^2 + O(m)$$$ to $$$\frac{5}{4} m^2 + O(m)$$$.

Similarly to $$$f(i, j)$$$ in the editorial we can define $$$g(i, j, l)$$$ as a sequence of operations that performs xor-assignments $$$a_i = a_i \oplus a_{j+l-1}$$$, $$$a_{i+1} = a_{i+1} \oplus a_{j+l-2}$$$, ..., $$$a_{i+l-1} = a_{i+l-1} \oplus a_{j}$$$, where indices are cyclic modulo $$$n$$$ and cyclic segments $$$[i, i + l - 1]$$$ and $$$[j, j + l - 1]$$$ do not intersect. This sequence is the same as $$$f(i, j + l)$$$ when $$$l \equiv j - i$$$ and otherwise ends with 3 passes between $$$i + l - 1$$$ and $$$j$$$ to clean up the mess. Defining $$$h(i, j, l)$$$ as a sequence of operations that reverse-swaps such two segments, $$$h(i, j, l) = g(i, j, l) \mathbin\Vert g(j, i, l) \mathbin\Vert g(i, j, l)$$$, $$$\frac{3}{2} m^2$$$ solution is $$$h(0, \lceil\frac{n}{2}\rceil, \lfloor\frac{n}{2}\rfloor)$$$.

But we don't have to drag $$$a_{n-1}$$$ through the whole array to get to $$$a_0$$$. Essentially instead of $$$swap(a_0, a_{n-1})$$$ we can perform $$$swap(a_{n-1}, a_0)$$$, then we replace two long passes and one short with two short passes and one long. Instead of $$$h(0, \lceil\frac{n}{2}\rceil, \lfloor\frac{n}{2}\rfloor)$$$ we split both segments, reverse-swap one pair though the middle of the array and the other through the ends. For example, taking $$$x = \lfloor\frac{n}{2}\rfloor$$$, $$$y = \lceil\frac{x}{2}\rceil$$$: $$$h(n - y, 0, y) \mathbin\Vert h(y, n - x, x - y)$$$.

Hint 2 for problme D: Combined with the first hint, we can say that a triplet (a,b,d) has no solutions if min(lsb(a),lsb(b))<lsb(d). Here, lsb(x) represents the least significant bit of x.

Does this mean that if a and b are even and d is odd then it should have no solution but test case 7 of the example have a solution?

`Does this mean that if a and b are even and d is odd then it should have no solution`

It's incorrect. There is a solution.If $$$a$$$ and $$$b$$$ are even, then their LSB of both

are greater than 1.If $$$d$$$ is odd, then

its LSB is 1.$$$min(1, 1) < 1$$$Isn't true. Hence, there is a solution.If you are confused with the fact that

if $$$min(lsb(a), lsb(b)) < lsb(d)$$$, then there is no solution., read below.Let $$$dq$$$ be any multiple of $$$d$$$. And $$$k = lsb(d)$$$. You can see that $$$lsb(dq) \geq lsb(d)$$$. It can be easily seen by adding d itself in its binary representation. You can see that any multiple of $$$d$$$ will have its bits on after or from $$$lsb(d)$$$.

Let $$$m = a|x$$$. According to the problem, we require $$$m$$$ to be some multiple of $$$d$$$. Since $$$m$$$ will be forced to have on all bits that are on in $$$a$$$ or $$$x$$$, then $$$m$$$ will have the $$$lsb(a)$$$ bit on. But we have seen that any multiple of $$$d$$$ will have its bits on from or after its lsb. Hence, if $$$lsb(a) < lsb(d)$$$, then there is no solution, it's impossible to have any multiple of $$$d$$$ that can have the $$$lsb(a)$$$ on, since it's less than $$$lsb(d)$$$.

So if $$$lsb(a) < lsb(d)$$$ or $$$lsb(b) < lsb(d)$$$, then there is no solution.

I use

`unordered_map`

in C, and I get TLE.Use

`map`

instead. Remember not to use`unordered_map`

in cf.I also get TLE by using map....

but I Accepted it by using

`map`

: 180658394Thank you for your advice.

I keep getting a "wrong" judgement on my Kotlin code even though I followed the example solution to a tee. Any hints?

Apparently I need to replace

`[email protected]`

with`[email protected]`

I'm not sure I'm right or not, but const number can't exist in $$$O()$$$(except $$$1$$$).

The number of operations are $$$n\times10^2$$$ but you can't say that the time complexity is $$$O(n\times10^2)$$$,maybe.

And of course it is easy to understand, but I suggest to fix it due to rigour.

If I'm wrong please figure out thx.

I think $$$O(N \cdot 10^2)$$$ is more concise than saying "$$$O(N \cdot a^2)$$$, where $$$a=10$$$ is the alphabet size", even though it's not as rigorous.

Nice observation though!

me when worst case $$$n$$$ is worst case $$$10^5$$$ so my $$$O(n^3)$$$ solution becomes $$$O((10^5)^3)$$$ which is a constant so it is equal to $$$O(1)$$$ so it enters any conceivable TL

Is anyone able to provide a detailed youtube explanation in english for solution C? Struggling to get my head around it..

Is anyone able to let me know if my explanation is correct here?

https://codeforces.com/contest/1748/submission/180639586#

wa on #516th ... any help?

Take a look at Ticket 16437 from

CF Stressfor a counter example.already got it, but thanks!

I finally became Master after this round. Thank you for the interesting problems.

I feel like there's an error in editorial of problem C. It should be added $$$[s_{i_1}, s_{i_1 + 1}, \cdots, s_{i_2 - 1}]$$$ in between $$$[s_1, s_2, \cdots, s_{i_1 - 1}]$$$ and $$$[s_{i_2}, s_{i_2 + 1}, \cdots, s_{i_3 - 1}]$$$. Of course, it does not really matter, the pattern is obvious, I was just pointing it out.

You're right, thanks for noticing. It's fixed now.

I have a stupid and complicated solution for B https://codeforces.com/contest/1748/submission/180642025 time complexity O(n logn)

I think the sample of D is a big hint. During the competition, I tried to convert the output of the last example into binary and found that the last 30 digits are all 1s, so I could find the solution. I think if the sample set the last 30 digits to be a|b, I must not be able to solve it.

Editorial posted 3 weeks ago..

how to solve d with exgcd（Extended Euclidean algorithm）?

Have someone else solved C by dp?

tried but wa if you know pls teach me

Consider $$$O(n^2)$$$ dp: $$$dp(i)$$$ -- maximum number of consecutive subsegments with zero sum you can get from the $$$i$$$-th prefix. $$$dp(i) = max_{j = 1...i} check(j, i) * dp(j - 1) + 1$$$ where function $$$check(l, r)$$$ is a boolean function which returns $$$1$$$ if you could obtain subsegment $$$(l, r)$$$ having zero sum. It is possible if and only if it contains $$$0$$$ or if it has zero sum. You can consider these two cases and optimize dp: find previous zero left to position $$$i$$$ and get something like prefix minimum, and for second case you can store in map optimum dp for every prefix sum value.

so my question is:

why https://codeforces.com/contest/1748/submission/180728658 this works and https://codeforces.com/contest/1748/submission/180728780 does not?

the only difference is that in #1 I go from n-1 to 0 and #2 I go from 0 to n-1

i would be glad if anyone could help me!

you are doing something wrong on the way you access indexes. May be printing indexes would help

have not gone through the code completely, but since we have to look at the prefix sums it makes sense that only one of them is ccorrect

I guess I got it. The problem is that we need to count the most frequent sum on suffix, not on prefix. Thanks y'all!

can someone explain greedy approach of c ? It sounds unintutive to me.

This's a great round... and my first round in CF :)

Balanced Substrings is too hard for a B

can someone explain how is the score at index where a[i]==0 is independent from score at a[j] == 0 where j<i, for other indexes which are greater than i, we can adjust the value of zero at index i such that we nullify the effect.

can someone explain the dp solution for qC?

Can anyone explain why in problem "C — Zero Sum Prefixes" is c++

`std::map`

(my test) more preferable than`std::unordered_map`

(my time limit test)?Always thought that

`std::unordered_map`

should give constant time on all required operations but`std::map`

— logarithmic. sorry for the newbie question.This blog explains the issues with

`std::unordered_map`

very well: https://codeforces.com/blog/entry/62393I participated from an alt but wanted to offer my feedback on the problems.

A — alright, I accidentally saw the title before I vc'd and prewrote the code, it actually worked

B — also alright

C — not very interesting, this problem does not need to exist

D — weird definition of an integer, this problem does not need to exist

E — annoying, this problem does not need to exist

F — incredibly annoying, I don't like this problem at all, i won't even try to solve it

Am o problema mai calitativa:

Dandu se un sir de operanzi cifre si operator ^ * | & ~ XOR + — / ** ! oplus, gasiti valoarea maxima a expresiei facand maximum k interschimbari.

MarinushCan somebody help me with problem C? My submission is here : https://codeforces.com/contest/1748/submission/180749200 . I don't know why i get WA and tried to figure out a testcase to get me WA. I have tried many times but failed. Please help ):(.

i did not understand the editorial for first problem,can anyone explain please???

B problem is really hard as usual. I was surprised to see that B problem was 1400 rated..!!

I participated from an alt but wanted to offer my feedback on the problems. A — alright, I accidentally saw the title before I vc'd and prewrote the code, it actually worked B — also alright C — not very interesting, this problem does not need to exist D — weird definition of an integer, this problem does not need to exist E — annoying, this problem does not need to exist F — incredibly annoying, I don't like this problem at all, i won't even try to solve it I have another solution for F: Bagi bulaneala pe vectori

Good. A *3000 in Div.2.

At Codeforces Round #833 (Div. 2)

There is a case of cheating in the problem B A solution is available during the contest on YouTube https://youtu.be/0x9kKxfqLr8

Matching solutions:- https://codeforces.com/contest/1748/submission/180650292

https://codeforces.com/contest/1748/submission/180650184

https://codeforces.com/contest/1748/submission/180649269

https://codeforces.com/contest/1748/submission/180646072

https://codeforces.com/contest/1748/submission/180646346

https://codeforces.com/contest/1748/submission/180646263

https://codeforces.com/contest/1748/submission/180646094

https://codeforces.com/contest/1748/submission/180645940

Can someone tell why I'm getting Wrong Answer for Problem C, testcase 2, #410, please. Thanks https://codeforces.com/contest/1748/submission/181030747

Take a look at Ticket 16438 from

CF Stressfor a counter example.Thanks a lot, didnt know about this website.

For problem D, how can we say for sure that $$$x$$$ will be of the form: $$$p11..11(30 - k \ times)00..00(k \ times)$$$

In problem D: How can we prove that $$$x_{(2)}=p 1 1 1 … 1 0 0 … 0$$$ is divisible by both a and b? Please, help!

The data structure, described in the editorial for problem E, is called Cartesian tree. One can build it in O(N).

How come in Problem B, not using ~~~~~ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ~~~~~ gives AC 181109995 but using this in code gives WA 181109865

Guys I can't seem to find what's wrong with my code for problem C https://pastecode.io/s/6qmq0jkc please take a look

Maybe you should iterate in subarray, not all element in the whole array.

No i got it, i forgot to check the case where there are no 0's in v or the case where prefix sum can be zero even before we encounter our 1st 0 in v[i].

https://pastecode.io/s/yic81p8g

Problem C Test 7 will block solutions using unordered_map, shit.

I came up with a different solution to problem E but it is not working (even on the first test case). I can't figure out what is wrong with my approach. I have described the idea below.

Observation

a[i] >= a[i + 1] implies b[i] >= b[i + 1]

a[i] < a[i + 1] implies b[i] < b[i + 1]

dp state: dp[i][j] = number of arrays with b[i] = j

Below is a link to my submission with actual code (which optimizes the above pseudocode using a prefix sum array.

181409754

Take a look at Ticket 16439 from

CF Stressfor a counter example.In problem D, there's this step in the explanation

$$$p+1 ≡ (2^{−1})^{30−k} \mod d' ⇔ p+1 ≡ (\frac{d'+1}{2}) ^ {30−k} \mod d'$$$

I don't understand where it comes from, like what property is being used or why this is done, can anybody help me please?

Still confused about C, consider a test case:

considering that i partition into subsegments then i will get answer as 5 here, but if i make replacements in subsegment for example: [0,1,-1,1]=[0,1,0,1]=-1(replace it with 0 in array)

1 -1 1 -1 1 0 1 1 -1 0

now [0,1,1,-1]=[0,1,2,1]=-1(replace with 0)

1 -1 1 -1 1 -1 1 1 -1 0

replace last with 0 with -prefix sum till ith index

[1,-1,1,-1,1,-1,1,1,-1,-1]=[1,0,1,0,1,0,1,2,1,0]

so after doing these operation according to subsegment i get answer 5 but if i change element to do dry run to see structure of array i get 4 zeros, is there anything wrong i did? or can you propose me some solution having 5 zeros? thanks in advance

Why is my same code getting accepted in GNU G++17 7.3.0 and not in GNU G++20 11.2.0 (64 bit, winlibs) ? What's the difference between these two languages? GNU G++17 7.3.0 — 186674226 GNU G++20 11.2.0 (64 bit, winlibs) — 186674279

For problem B, can anyone help me understand why this 188673953 is AC, but this 188673213 is WA?

The AC one is simply starting from

`ans=0`

and doing`ans++`

for each diverse substring. The WA one is the opposite. It starts with`ans=(n*(n+1))/2`

and doing`ans--`

for each non-diverse substring.Take a look at Ticket 16693 from

CF Stressfor a counter example.By the way, it's trivial to prove that your WA algorithm is incorrect. In your AC submission, you are iterating over all diverse substrings. In your WA submission, you iterate over all non-diverse substrings. So if I combine both of your solutions, I would be able to iterate over all $$$O(n^2)$$$ substrings in $$$O(n)$$$ time. A contradiction.

The catch here is that the diverse substrings are scarce, and closer to $$$O(n)$$$, while their complement is abundant, of order $$$O(n^2)$$$. That's why the subtraction strategy would result in TLE if implemented properly, or would undercount the non diverse substrings of length greater than 100 if implemented poorly.

Thanks so much!

Awesome contest but most of us were late :)

In C can it happen that maximum frequency prefix of the subarray is such that for nullifying that prefix our ai exeeds the limit of 1e9 ?

My bad it can be any arbitary number.... i thought that just like initial ai new replaced ones should also lie b/w -1e9 and 1e9

D is such a nice problem man but there is something that I found very unintuitive about it and that is — why you filled all the digits before p and after k to be one. I mean the best thing I could arrive at after solving this problem for hours was that rather than filling up all of them with ones as you did I would fill it with a^b and I reched nowhere.