## A — The Third Three Number Problem

Authors: antontrygubO_o, Gheal

**Hints**

**Hint 1**

An answer exists only when $$$n$$$ is even.

**Hint 2**

- $$$a \oplus a = 0$$$
- $$$a \oplus 0 = a$$$

**Solution**

First and foremost, it can be proven that $$$(a \oplus b) + (b \oplus c) + (a \oplus c)$$$ is always even, for all possible non-negative values of $$$a$$$, $$$b$$$ and $$$c$$$.

**Proof**

Firstly, $$$a \oplus b$$$ and $$$a+b$$$ have the same parity, since $$$a + b = a \oplus b + 2 \cdot (a \text{&} b) $$$. Therefore, $$$(a \oplus b) + (b \oplus c) + (a \oplus c)$$$ has the same parity as $$$(a+b)+(b+c)+(a+c)=2 \cdot (a+b+c)$$$.

Therefore, if $$$n$$$ is even, one possible solution is $$$a=0$$$, $$$b=0$$$ and $$$c=\frac n2$$$. In this case, $$$(a \oplus b) + (b \oplus c) + (a \oplus c)= 0+\frac n2+\frac n2=n$$$. Otherwise, there are no solutions.

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

**Code (C++)**

```
#include<bits/stdc++.h>
using namespace std;
void testcase(){
int n;
cin>>n;
if(n%2==0)
cout<<"0 0 "<<n/2<<'\n';
else
cout<<"-1\n";
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int t;
cin>>t;
while(t--)
testcase();
return 0;
}
```

**Post Scriptum**

This is actually the third iteration of the problem, which was suggested by antontrygubO_o.

The first iteration had $$$|a-b|+|b-c|+|a-c|=n$$$, and the second one had $$$gcd(a,b)+gcd(b,c)+gcd(a,c)=n$$$.

## B — Almost Ternary Matrix

Author: Gheal

**Solution**

The general construction consists of a $$$2 \times 2$$$ checkerboard with a $$$1$$$-thick border. Here is the intended solution for $$$n=6$$$ and $$$m=8$$$:

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

**Code(C++)**

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void testcase(){
ll n,m;
cin>>n>>m;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
cout<<((i%4<=1)!=(j%4<=1))<<" \n"[j==m];
}
}
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int t;
cin>>t;
while(t--)
testcase();
return 0;
}
```

## C — The Third Problem

Author: Gheal

**Hints**

**Hint 1**

Let $$$p[x]$$$ be the position of $$$x$$$ in permutation $$$a$$$.

Since $$$MEX([a_{p[0]}])=1$$$, the only possible position of $$$0$$$ in permutation $$$b$$$ is exactly $$$p[0]$$$.

**Hint 2**

Continuing this line of thought, where can $$$1$$$ be placed in permutation $$$b$$$?

**Hint 3**

Without loss of generality, we will assume that $$$p[0] \lt p[1]$$$.

- If $$$p[2] \lt p[0]$$$, then how many possible positions can $$$2$$$ have in permutation $$$b$$$?
- If $$$p[0] \lt p[2] \lt p[1]$$$, then how many possible positions can $$$2$$$ have in permutation $$$b$$$?
- If $$$p[2] \gt p[1]$$$, then how many possible positions can $$$2$$$ have in permutation $$$b$$$?

**Solution**

Let $$$p[x]$$$ be the position of $$$x$$$ in permutation $$$a$$$.

Since $$$MEX([a_{p[0]}])=1$$$, the only possible position of $$$0$$$ in permutation $$$b$$$ is exactly $$$p[0]$$$.

Without loss of generality, we will assume that $$$p[0] \lt p[1]$$$. For every interval $$$[l,r]$$$ ($$$l \le p[0] \lt p[1]\le r$$$), $$$MEX([b_l,\ldots,b_r])$$$ must be at least $$$2$$$. For every other interval, $$$MEX([b_l,\ldots,b_r])$$$ cannot exceed $$$2$$$. The only position for $$$1$$$ which satisfies both of these constraints is exactly $$$p[1]$$$.

Let's consider the *current interval* $$$[l,r]$$$ as being $$$[p[0],p[1]]$$$.

If $$$p[2] \in [l,r]$$$, we can say that, for every interval $$$[x,y]$$$ ($$$x \le l \lt r \le y$$$), $$$MEX([b_x,\ldots,b_y])$$$ must be at least $$$3$$$. Similarly, for every other interval, $$$MEX([b_x,\ldots,b_y])$$$ cannot exceed $$$3$$$. Both of these constraints are only met if $$$2$$$ occurs in permutation $$$b$$$ on some position $$$p \in [l,r]$$$. Since only $$$2$$$ positions are currently occupied in $$$[l,r]$$$, the total number of similar permutations will be multiplied by $$$(r-l+1)-2$$$.

Otherwise, $$$2$$$ can be placed in permutation $$$b$$$ only on $$$p[2]$$$. Additionally, the current interval will be "extended" to include $$$p[2]$$$, resuting in either $$$[p[2],r]$$$ or $$$[l,p[2]]$$$.

After processing $$$0,1, \ldots, k-2$$$ and $$$k-1$$$, the algorithm for processing $$$k$$$ is very similar to the one presented earlier. If $$$p[k] \in [l,r]$$$, the answer gets multiplied by $$$(r-l+1)-k$$$. Otherwise, the current interval is extended to include $$$p[k]$$$.

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

**Code(C++)**

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NMAX=1e5+5,MOD=1e9+7;
ll v[NMAX],pos[NMAX];
void tc(){
ll n,l,r,ans=1;
cin>>n;
for(ll i=0;i<n;i++){
cin>>v[i];
pos[v[i]]=i;
}
l = r = pos[0];
for(ll i=1;i<n;i++){
if(pos[i]<l) l = pos[i];
else if(pos[i]>r) r = pos[i];
else ans=ans*(r-l+1-i)%MOD;
}
cout<<ans<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
ll t;
cin>>t;
while(t--)
tc();
return 0;
}
```

## D — Almost Triple Deletions

Author: Gheal

**Hints**

**Hint 1**

Consider the opposite problem: What is the smallest possible length of a final array?

**Hint 2**

For which arrays is the smallest possible final length equal to $$$0$$$?

**Hint 3**

Considering the second hint, it is possible to completely remove some subsegments from the array.

**Solution**

Lemma: An array $$$a_1,a_2,\ldots, a_n$$$ can be fully deleted via a sequence of operations if and only if it satisfies both of the following constraints:

$$$n$$$ is even

The maximum frequency of any element in the array is at most $$$\frac n2$$$.

**Proof**

If $$$n$$$ is odd, then any final array will also have an odd length, which can't be $$$0$$$.

An optimal strategy is to always delete one of the most frequent elements and any one of its neighbours. If the most frequent element occurs $$$k \gt \frac n2$$$ times, then the final array will have at least $$$n-2 \cdot (n-k)=2\cdot k - n \gt 0$$$ elements. Otherwise, this strategy ensures the full deletion of the array, since, after performing an operation, it is impossible for an element to occur more than $$$\frac {n-2}{2}$$$ times in the array.

Since the maximum frequency of a value for every subsegment $$$[a_l,a_{l+1},\ldots,a_r]$$$ can be computed in $$$O(n^2)$$$, it is possible to precompute all subsegments which can be deleted via a sequence of operations.

Let $$$dp[i]$$$ be the maximum length of a final array consisting of $$$a_i$$$ and some subsequence from the first $$$i-1$$$ elements. Initially, $$$dp[i]$$$ is set to $$$1$$$ if the prefix $$$[a_1,a_2,\ldots, a_{i-1}]$$$ can be fully deleted. Otherwise, $$$dp[i]=0$$$.

For every pair of indices $$$i$$$ and $$$j$$$ ($$$1 \le j \lt i \le n, a_i=a_j$$$), if we can fully delete subarray $$$[a_{j+1},a_{j+2},\ldots a_{i-1}]$$$, then we can append $$$a_i$$$ to any final array ending in $$$a_j$$$. Naturally, $$$dp[i]$$$ will be strictly greater than $$$dp[j]$$$. This gives us the following recurrence:

If we define a final array as a subsequence of equal elements from the array $$$a$$$, to which $$$a_{n+1}$$$ is forcefully appended, then the final answer can be written as $$$dp[n+1]-1$$$. Note that, when computing $$$dp[n+1]$$$, $$$a_j$$$ should not be compared to $$$a_{n+1}$$$.

Total time complexity per testcase: $$$O(n^2)$$$.

**Code(C++)**

```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll NMAX=5e3+5;
ll dp[NMAX],fr[NMAX],a[NMAX];
void tc(){
ll n,maxfreq=0;
cin>>n;
for(ll i=1;i<=n;i++)
cin>>a[i];
dp[0]=dp[n+1]=0;
for(ll j=1;j<=n;j++) fr[j]=0;
for(ll i=1;i<=n+1;i++){
if(i%2 && maxfreq<=i/2)
dp[i]=1;
else
dp[i]=0;
maxfreq=max(maxfreq,++fr[a[i]]);
}
for(ll i=1;i<=n;i++){
for(ll j=1;j<=n;j++) fr[j]=0;
maxfreq=0;
if(dp[i]>0) /// If there is no subarray ending in a[i], then some subarrays beginning with a[j] might be incorrectly flagged as possible final arrays
for(ll j=i+1;j<=n+1;j++){
if((j-i)%2 && maxfreq<=(j-i)/2 && (j==n+1 || a[i]==a[j]))
dp[j]=max(dp[j],dp[i]+1);
maxfreq=max(maxfreq,++fr[a[j]]);
}
}
cout<<dp[n+1]-1<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll t; cin>>t; while(t--)
tc();
return 0;
}
```

## E — Three Days Grace

Author: tibinyte

**Solution**

We can see that in the final multiset, each number $$$A_i$$$ from the initial multiset will be assigned to a subset of values $$$x_1, x_2,....,x_k$$$ such that their product is $$$A_i$$$. Every such multiset can be created. Also let $$$vmax$$$ be the maximum value in the initial multiset.

Consider iterating through the minimum value. To get the best maximum value that has this minimum we fixed, one can use dynamic programming $$$dp[i][j] = $$$the best possible maximum if we had number $$$i$$$ and the minimum value in the product is $$$j$$$, $$$j$$$ is a divisor of $$$i$$$. This dp can be calculated in $$$O(vmax \cdot log^2(vmax))$$$ for all values. We can also process all updates when incrementing the minimum and keeping the result with a total effort of $$$O(vmax \cdot log^2(vmax))$$$. Thus we have a total time complexity of $$$O(vmax \cdot log^2(vmax))$$$. However, this ( we hope ) won't pass.

Here is a way more elegant solution ( thanks to cadmiumky ):

To get things straight, we observe that when we decompose a number, we just actually write it as a product of numbers. We still consider fixing the minimum value used in our multiset, call it $$$L$$$. We will further consider that we iterate $$$L$$$ from the greatest possible value (i.e. $$$vmax$$$) to $$$1$$$, and as such, we try at each iteration to calculate the minimum possible value which will appear in any decomposition as the maximum value in said decomposition.

We shall now retain for each element the minimal maximum value in a decomposition where the minimum of that decomposition is $$$L$$$, let's say for element $$$i$$$, this value will be stored in $$$dp[i]$$$. Naturally, after calculating this value for every number, we now try to tweak the calculated values as to match the fact that, after this iteration concluded, we will decrease $$$L$$$. For further simplicity, we denote $$$L' = L - 1$$$.

So, we changed the minimum value allowed. What changes now? Well, it is easy to see that any element that is not divisible by $$$L'$$$ won't be affected by this modification, as much as it is impossible to include $$$L'$$$ in any decomposition of said number. So it remains to modify the multiples of $$$L'$$$. Let's take a such number, $$$M$$$. How can we modify $$$dp[M]$$$? Well, we can include $$$L'$$$ in the decomposition as many times as we want, and then when we decide to stop including it, we remain with a number which needs to be further decomposed. The attributed maximum of this value should already be calculated, so we can consider it as a new candidate for the update of $$$dp[M]$$$. This idea could be implemented simpler by going through multiples of $$$L'$$$, and for an element, updating $$$dp[i]$$$ with $$$dp[i / L']$$$ (by taking the minimum of either)

We now need for each iteration to keep track of the attributed maximums of each element that actually appears in our initial list. This can be done by keeping a frequency of all these elements, and after all updates, taking the (already known) maximum of the previous iteration and decreasing it until we find another element that actually appears in our set (this can be verified by simply checking the frequency). This is correct, as much as all the values gradually decrease as $$$L$$$ decreases, so their maximum would have to decrease as well.

Final time complexity: $$$O(vmax * log(vmax))$$$

**Code(C++)**

```
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int nmax = 5e6 + 5;
int appear[nmax];
int mxval[nmax];
int toggle[nmax];
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--)
{
int n, m, mn = nmax, mx = 0;
cin >> n >> m;
for (int i = 0; i <= m; ++i)
{
appear[i] = toggle[i] = mxval[i] = 0;
}
for (int i = 0, x; i < n; i++)
{
cin >> x;
appear[x] = 1;
toggle[x] = 1;
mn = min(mn, x);
mx = max(mx, x);
}
for (int i = 0; i <= mx; i++)
{
mxval[i] = i;
}
int ptr = mx, smax = mx - mn;
for (int i = mx; i >= 1; i--)
{
for (ll j = (ll)i * i; j <= mx; j += i)
{
if (appear[j])
toggle[mxval[j]]--;
mxval[j] = min(mxval[j], mxval[j / i]);
if (appear[j])
toggle[mxval[j]]++;
}
while (toggle[ptr] == 0)
ptr--;
if (i <= mn)
smax = min(smax, ptr - i);
}
cout << smax << '\n';
}
}
```

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

Very Fast Tutorial, Amazing Contest

Thank you for the hintsB was quite an annoying one

yeah

I know, right?!

Could someone please explain the implementation? I didn't get what the solution shared in the editorial is saying exactly...

Start by solving a 2x2 matrix. For the 2x4 matrix, you can flip the 2x2 matrix to the right. You can see that if you just flip the 2x2 matrix to the right every time, you can solve matrices of sizes 2x6, 2x8, and so on. The same can be applied with nx2 matrices (4x2, 6x2, 8x2 and so on), except this time you flip the 2x2 matrix down.

This is hard to comprehend.

a much easier implementation would be to notice that a pattern in the binary matrices like this

and we can obtain any row x column by increasing or decreasing the rows or columns accroding to this pattern.

for eg : a 8 x 10 will look

like thisso for implementing just make a 50 x 50 matrix (which is not much of a trouble if you use copy and paste) and output for given row and column

my code :

codeamazing

bro is a true gamer

OMG, I can't believe I didn't try this uff. I was unnecessarily trying to automate the process! Thank you very much.

I realize why I didn't get thisUsually in any problem that requires us to calculate some array, matrix, or whatever which remains same for all testcases, I just write a "generator code" to generate that array, say

The problem here was that I tried to do something similar, like how vikxen said by appending the reversed lists for further columns and transposing matrix for further rows and whatnot but I couldn't do it in time.

Should've done it manually.

I think getting into into the graphical proof would rather be long so the setter avoided elaborating much on that, but there's actually a subtle way to approach it.

Consider the top left cell, start filling from there recursively for some small input, you'll notice a pattern and reach some solution for it. So, now you have the answer to this small input, can you reuse this ?

So, assuming you tried using it, did you notice some induction happening or an extension of your pattern?

You can prove by induction that the pattern in fact safely extends for the given input!

Codeyeap

No.

Well, it didn't have any particular way to solve it, you just had to guess the structure of the matrix and I just found that pretty annoying... idk about you.

B/E and C/D seem to have the same rate problem poll.

Edit: Thanks for fixing! Perhaps it should've been better to keep the C/D poll for C, since it's likely that most people voted for C rather than D, but it shouldn't be too major of a problem.

yea

Sorry for this, it should be fixed now.

D & C have same "problem rate"

Comment DeletedThanks for the fast editorial. And the contest was amazing! Problems are great.

In my opinion C was relatively tough as compared to general C.

Most testers said that the current C would be better as a div2 D. We did try to insert a new C between the current B and C, however this wasn't approved in the end.

Ohh..that was the case...but overall contest was pretty good.

Though i couldn't do it, but C was really an interesting problem.

I went on the wrong track, and even tried to implement offline fenwick tree queries lol. I thought it had something to do with the number of elements greater than a number k between the first appearance of a number from 0 to k and the last appearance of a number in the range 0 to k. The solution was much simpler lol. I didn't have time to finish this solution so idk if it works.

D was too hard too, contests should be easier so they don't make me feel bad :((( Also they should make me grandmaster

Hahaha

lol

Bro, You were

MASTERonce . DamnHere's my submission. 162794168

Thank you

.

Thank you.

That's the most cursed thing I have ever written, accidentally or not. Has been fixed.

I found a solution for B, but couldn't implement it in the contest (I am sure that there are other people like me). I generally think problems like B in Div. 2 should be easy to implement when you find a solution.

Well, I guess that was the whole point of B, figuring out the solution was easier than standard div2B's, but the implementation was the tricky part.

I mean, implementation was harder than standard B's, but not that hard. Also, the simplicity of the idea kinda makes up for it in my opinion.

My implementation is pretty short, I genuinely thought the idea was the hard part.

I guess I'm getting smarter B-)

There was a hint on sample tests on problem B. Sad I saw it so late

In solution of C, "If p[2]∈[l,r], we can say that, for every interval x,y, MEX([bl,…,br]) must be at least 3"

Shouldn't that be MEX of [bX....bY]?

That is true, thank you for noticing. It has been fixed now.

Auto comment: topic has been updated by Gheal (previous revision, new revision, compare).Did anyone solve problem D with segment tree?

mass cheating in this round https://www.youtube.com/watch?v=AxY427BJnl8

Please ban these kind of users

yes.

I would request Mike and his team to kindly look into this since it made the contest unfair for many! ;(

[.]

Solution to B, "...with a 1-thick border."

What is that border?

Like if you cover the boarder in the picture, you have a checkerboard that looks like this:

I think that's what they meant. Hope that helps.

Thank you, it wasn't clear to me neither.

Are you going to be posting a screencast of this contest?

Welllllll....

I recorded an incredibly entertaining screencast and was going to post it. But for some reason my mic was set up incorrectly so there was no sound, despite my recording software visually showing me that there was sound. So I feel kind of cheated out of it, but unfortunately on screencast this time, especially because this one would have been great. :(

I'm very sorry to hear this... Right when i saw you in the standings I was hyped to see a screencast. However, did you like the problems ?

I did, yeah. Overall they were very interesting. The only one I downvoted was A, because I think asking a newbie questions about xor isn't very approachable. It was a neat idea, but I think a little scary for that position if you're not familiar with CP.

my construction was that these 2 2X2 blocks

01

10

and

10

01

have to be used alternately. Sorry for the bad formatting.

That's the way I thought too. I am still wondering how jiangly's brain works after seeing this solution:

what on earth is this

It's just a more concise way of formatting writing the checkerboard thing. Essentially, it's just the parity of (i = 1 mod 2) + (j = 1 mod 2) + (i = 1 or 3 mod 4) + (j = 1 or 3 mod 4), which is exactly what you want if you look at the checkerboard.

It would be more clear if I could post a whiteboard drawing, but in any case, I think just chewing on this type of parity stuff will make it easier to internalize/visualize/quickly convert from tilings to math.

lol what a orz guy.

why im not able to attempt the hacks for this contest?

No one is. The contest is like that.

People are attempting hacks, i can see that in the hacks menu.

I am sorry. I made a mistake. I can't hack neither.

The contest has ended, and outside of contest only higher rated players can hack (https://codeforces.com/blog/entry/68204)

What is " \n"[j==m]; in the c++ solution of the B problem??? Doesn't it have a name??

`j==m`

can be transformed into`int(j==m)`

;`" \n"`

is a string constant (char array).Then it's just the same as accessing an array.

cool way to code clean!

Interesting, because I felt that such kind of coding style is the complete opposite of clean coding (unless, if you think clean code == shortest possible code).

As far as I know, clean code means the one which is easily understandable to others. Condensing your code so much that no one else understands it, I don't understand the logic behind it.

so when we will get only " " and when we will get " \n" how it is decided ??...

when j == m, the output is true which is taken as 1. and when it is less that m, the output is false, i.e 0;

Let us assume s = " \n", so s[0] = ' ' and s[1] = '\n'. Here, in the for loop, he wrote " \n"[j == m], so if j == m, j == m will be 1 and " \n"[1] = '\n' will be printed, otherwise " \n"[0] = ' ' will be printed.

MikeMirzayanov This person's (bored_kid) submissions look very sus. example:162802356

they probably could've used the time it took them to insert all these lines to actually solve the problem lol, I really don't understand those people... good job for calling them out

bored_kid if you are bored, go and learn new things. Rather than copying and defaming your country by just mentioning India, instead mention your real name and institution.

This Guy Posts Solutions on YouTubein real time. Can we do something about that? He always gets 500 to 600 views during contests

Sorry for stupid question but I am seeing this syntax first time, From Editorial of problem B-

Can you tell what [j==m] is doing here and why there is no << before that?

See this comment.

if

`j==m`

, it means`j`

is the last element of the row, so`j==m`

is`1`

and`" \n"[1]`

is actually`'\n'`

. Otherwise,`j==m`

is`0`

and`" \n"[0]`

is a whitespace. This small trick is used to print whitespaces between elements, and a newline after a row of elements.Thanks for the round!

In problem E, some of solution can be hacked with special testcase:

t=1

n=1000000,m=5000000

a={n numbers with a large number of divisors in [1,m]}

Especially when the solution has O(MlogMlogN) time complexitity, I recommend you to check it :)

I actually had generator with large divisors, but I think i should have considered a bigger upperbound on the number of divisors. I think it was set to be at most 50 divisors less than the maximum possible number of divisors...

nice editorial and thanks for the hints

How to prove that the sum (a⊕b)+(b⊕c)+(a⊕c) is always even in the first problem?

Consider the lowest bit of the three numbers, and check all cases.

Any formal proof?

I included a formal proof in the solution for A.

How we can conclude that a ⊕ b and a + b have the same parity (odd or even number of 1-bits) from the equation a + b = a ⊕ b + 2⋅(a&b)? And also how same parity ensures that (a ⊕ b)+(b ⊕ c)+(a ⊕ c) will be even?

$$$2\cdot (a\text{&}b)$$$ is always even, so it would make sense that $$$a + b$$$ and $$$a ⊕ b$$$ have the same parity.

The parity of $$$(a ⊕ b)+(b ⊕ c)+(a ⊕ c)$$$ is the same as the parity of $$$(a+b)+(b+c)+(a+c)=2 \cdot (a+b+c)$$$, which is always even.

You are considering parity as the property of an integer of whether it is even or odd or it means parity of a number whether it contains an odd or even number of 1-bits?

Parity as in whether an integer is even or odd.

for odd numbers it is impossible to have a b c to satisfy the condition and for even number one possible pair is 0 n/2 n/2 so the sum is always even.hope it helps

last bit of all 3 elements 0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

now xor them and add last bit will always be zero. :)

PROOF FOR A... We know

0^1 = 1

0^0 =0

and 1^1=0

CASE1:

One of a,b,c is odd,let us say c, then the rightmost bit for c is 1 and for a and b is 0 ,this imply(a^c) is odd (as rightmost bit is 1)

similarly (b^c) is also odd .

and (a^b) is even as rightmost bit is 0.

so the sum will also even.

CASE2:

Any two is odd, let us say b and c , then the rightmost bit for a is 0 and for c and b is 1 ,this imply(a^c) is odd as (rightmost bit is 1 )

similarly (a^b) is also odd .

and (c^b) is even as (rightmost bit is 0).

so the sum will also even.

CASE3:

All of the three is oddthe rightmost bit for a,b & c is 1.a^b is even as rightmost bit is 0.

similarly b^c and c^a are even .

so sum will even.

CASE 4:

None of them is odd, the rightmost bit for a,b &c is 0.a^b is even as rightmost bit is 0.

similarly b^c and c^a are even .

so sum will become even.

code

Thank you for your nice explanation.

thanks

Amazing Observation uks_28. I just guessed and solved but you proved it in a very simple way.

Thanks

consider the case where n is odd which has last bit as 1, so we need last bit as 1. but if we check all cases where numbers having last bit like

`1 0 0`

`0 1 0`

`0 0 1`

`1 1 0`

`0 1 1`

`1 0 1`

`1 1 1`

All cases give last bit as 0 if we try out it in given equation.The observation in B is very hard .-32 in the rating thanks codeforces

Here is a way to approach problem B: (let me use "color" instead of "value")

We have to find a coloring, such that each cell has exactly 2 neighbours of a different color. IMHO, 2 neighbours of a different color are quite annoying. I've tried to avoid it, reformulating like this: each cell has 4 neighbours, so let's find a coloring, such that each cell has 4-2=2 neighbours of the same color. But it fails on the borders.

However, we can avoid "different color" part! Let's

`xor`

each cell with corresponding cell in the chess coloring. Now we have to find a coloring, such that each cell has exactly 2 neighbours of the same color.From that side, the solution is easier: split the matrix into 2x2 squares and color neighbouring ones differently.

Here's the solution for 8x6 matrix (I've assumed black is 0, white is 1):

Interesting facts:

The answer is

`((i/2 + j/2) % 2) ^ ((i + j) % 2)`

The answer is the same as in the editorial

can't understand from the part "however we can avoid ..." can you please explain a bit more how are you xoring with the chess board and how this approach comes into your mind

Suppose you have a matrix

`a`

, such that every cell`(i, j)`

have exactly two neighbours of the same value. Then you put the matrix on a chess board and flip those values that lay on white cells. Effectively, you assume that black is 0, white is 1 and perform`xor`

of corresponding cells.Consider some black cell (the logic with white cells is pretty much the same). It has only white neighbours. That means it doesn't change value, but all the neighbours do. In result, the former cell has now exactly two neighbours with different value.

Can't say anything about how to come up with the idea...

How did you create the image for the editorial of problem B? It's pretty.

I made it using vanilla HTML and JavaScript.

CodeHi, could somebody explain third's logic, can't wrap my head around it.

On Codechef, there was a similar problem as C, it had like 20-30 solves. In editorial, there was some statement that the current requirement is equivalent to... If someone remembers, can you please share the link

Here

Problem

Bwasn't in expectation. Was very annoying !I solved A through C. I thought that A was kind of mathy for an A, but it was okay. Problem B was kinda easy for a B as it was just figuring out how the optimal construction will look like. And I thought C was a pretty nice C. My sol was to maintain 2 pointers pointing to the left and right of the current subarray, and l = r = position of 0 at the beginning. While the MEX of the subarray was less than n, I used reverse indexing to get the position of the MEX in array a and moved my subarray to include it. Then, I calculated the amount of extra numbers(from the difference of the MEXes) that could go in the empty spaces of the subarray and I multiplied the answer by space_P_amount, where amount was the number of extra numbers that could go anywhere inside the array. 162794168

was B really that simple that it got 9k+ correct submission . I wanted to know as I didnt able to come with an algorithm for B even after spending 2 hrs. Its happening since past 2 contest that i got stuck on B and my rating is decreasing gradually due to this

Same for me, I am surprised by the big number of solves.

it's due to cheating B is a good problem and its difficult to observe the pattern

Lol I spent more than 30 minutes coming up with a solution right now. Constructive problems are wild, eh? I saw someone's comment saying "B was easier than regular div2 B" ☠️

Problem A :- a=0, b=n/2 and c=n/2 also works.

For problems like D, really wondering how people come up with the right dp idea along with this observation? This dp method and the proof don't seem obvious to me, and I don't understand how to come up with this idea given this problem (For me, binary search or checking the maximum value of each value is more intuitive, though they can't solve this problem). (Perhaps it's just I am too bad at dp orz)

Man, I never would've thought of this dp idea. I wasn't able to solve D during the contest but it seems like you can solve it kinda greedily as well. I created the can_delete matrix to store if some subarray can be deleted and then I just found out the max length possible greedily. Can't prove it tho. my submission

Hmm, that's a strange solution... However you were very close to the solution, most difficult thing imo was checking weather subarray can be deleted...

I figured out a solution during the contest that if we create some matrix that stores if a subarray can be deleted or not we can easily build a dp table such that dp[i] denotes the maximum number of the same elements as a[i] of which the last element is at the ith position. Just couldn't think of a way to make the matrix (matrix — isposs[i][j] = 1/0 depending on whether we could delete the subarray i...j or not respectively). The observation (n/2 must be even and max(freq[1..n]) <= n/2) was not intuitive. Link to my solution

Try something like 1 2 1 2 1 2 1 2 3 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3

Same here. I thought checking for each distinct value is obvious thing as it also matched the complexity O(n^2). I did try to think of some dp after that. Something like, dp[i][j] = maximum equal value j we can get from first i elements;

but couldn't figure out the whole thing.

Can Anyone Explain the Solution of Problem C a bit more?

First all, it is easy to know 0 and 1 must have the same position in 'a' as 'b'. It is easy to find examples that 'a' is not similar with 'b' if the statement is not true.

Next, consider the interval by the position of 0 and 1. If 2 is in this interval in 'b', then 2 can be any position in the interval in 'a'. To prove this, there are several cases to consider. But it is easy to understand the reason if you use a sample to learn. And if 2 is out of the interval in 'b', then 2 must be in the same position in 'a'. After 2 is considered, continue to consider the interval by the position of 0, 1, and 2. And consider whether 3 is in the interval or is out of the interval. And so on until to n-1.

I don't know how this formula is gotten: "(r−l+1)−k", but you can always calculate how many position are available in one interval and multiply the number to the answer.

One sample submit: https://codeforces.com/contest/1699/submission/162835519

yeah thanks I understand now, for the formula for ex if pos of 1 is 0 and pos of 0 is 3 then the no of positions for 2 are =3-0+1-(num of pos taken by 0 and 1) which is 2 itself so 3-0+1-2=2 hence the formula (r-l+1)-k hope you can understand now

I know number 0 . But why is the position of number 1 the same as that of number 1 of array a? Please indicate,thanks.

If you use a sample to check it, it is not difficult to find that is true. If 1 is on right side of 0, such like "2 0 3 4 1 5", it is quite clear, as starting from position of '1', MEX value becomes 2 or more. If 1 is on left side of 0, such like "2 1 3 4 0 5", I guess you may ignore the problem asks any interval should have same MEX. Then you can check an interval which covers '0'. Whether '1' is in the interval impact MEX value of position '0'. So '1' cannot be moved either; otherwise at least one interval's MEX is different.

houxiang thanks for the approach, got it now !

my solution for problem c,

lets pos[a[i]] = i;

initially let l=r=pos[0], as the only position for the 0 in

bis the same as ina, because ina, mex(l=pos[0], r=pos[0])=1, and we have to maintain that inb.now to get a new mex value in

a, we have to extend our interval [l, r] somehow to get a value greater than 1, to achieve that, we have to at least include the value 1 into our interval, so we have to extend either l or r to include the value 1, so if (pos[1] < l) then we have to extent l, or if (r < pos[1]) we have to extend r, after doing that, we can see how the position of value 1 in b have to be the same in a, but now the mex value can be greater or equal to 1, so we might have values greater than 1 included in our new interval that we don't benefit of, we simply are going to store them for later when they are included in the mex value (because if we position them in the current interval then we didn't consider the possibility that they can be positioned outside the current interval).we continue trying to increase the mex value of our interval, for example, after extending the interval to include the value 2, we got the mex value 4, so now we are going to look for the value 5 so we can have a new mex value.

now about the stored-for-later values, that at some point they were greater than the mex value (actually they were greater than mex+1), now some of them are included in the new mex value, so they have to be positioned somewhere in the current interval and not outside it, so we are going to look at the currently available positions in b that aren't occupied with some values, and we are going to choose some of them to put those values, and then choose their order. after that, we delete those newly positioned values from the stored-for-later set of values and continue our process until the interval covers all of

a.my implementation

how to manage mex value with updates

can we do B using dfs traversal? for example first fill all the positions of the 2d array with 1 then run dfs from (0,0) so that every cell change exactly two neighbour cells 0. any one help?? if i'm wrong

Possibly, but it's definitely not necessary. A simple matrix traversal is enough for this problem.

what exactly do you mean by DFS traversal? what exactly would you do for each node?

for every node (i,j) goto (i-1,j),(i+1,j),(i,j+1)and(i,j-1) then make exactly two of them to opposite color of (i,j).

how do you decide which ones to flip then?

Can someone prove B? I solved it like this too but I don't know how to prove it exactly

Can anyone suggest me similar problems such as today's Div2 B? I found it annoying. I know no problem is a bad problem and instead of complaining we all should try our best but sometimes I feel like I'm getting nowhere. How should I approach such problem ? Should I try out as many test cases as possible until I find a pattern ?

How can somebody come up with this solution for problem B 162759681. Can anybody explain the intuition and logic behind its implementation ?

The questions mentoined in post scriptum of problem A. How can we solve them can anyone give hints? According to me for 1) mod — if n is even return 0,n/2,n/2 else -1 2) gcd — no idea

For gcd, the intended solution is $$$1$$$ $$$n-2$$$ $$$n-2$$$.

for mod is the logic correct?

Yes. If I recall correctly, $$$a$$$, $$$b$$$ and $$$c$$$ needed to be distinct, which I didn't mention in the blog. My solution was $$$0$$$, $$$1$$$, $$$\frac n2$$$.

thanks got it btw nice editorial

thanks, glad you liked it

Can you please reply to my query as well. How is this solution 162759681 working exactly and what is the intuition behind this implementation

https://codeforces.com/contest/1699/submission/162794343

Pretty solution for B

Base row1..... .... 1001 Base row2... . ... 0110 Again repeated row3 0110 Row4.. .......... 1001 Like this formats its repeated

I did not understand this statement from C: "For every other interval, MEX([bl,…,br]) cannot exceed 2". In the above statement, how can the MEX value be 2? Isn't the maximum MEX 1 for all other intervals?

Spoiler1 3 0 2

L = 0,R = 2

The statement in solution C says "For every interval [l,r] such that (l≤p[0]<p[1]≤r), MEX([bl,…,br]) must be at least 2. For every other interval, MEX([bl,…,br]) cannot exceed 2". The interval L = 0, R = 2 you mentioned satisfies the condition (l≤p[0]<p[1]≤r). But the question is about intervals that don't satisfy this condition.

Yeah I had the same Confusion

Sadly I had to do some more important things so I couldn't participate :(

But I really enjoyed cadmiumky's problems!

MarinushAnd I really enjoyed you not participating!

And I really enjoyed the bried time before this comment where you hadn't assumed I asked!

cadmiumkyTbh, problem B was too easy for div2b, thanks to first sample that used pattern, which can be extended to infinite boards. However, problem C was annoying imo.

I found B hardest among A-D, seems skill issue on my part.

Maybe we're just good at different types of tasks, I can't say that I'm really into DP problems ;)

Can you Explain the Solution of Problem D a bit more?So hard for me![cry][cry]~

Can U explain B . I found it to be very tricky and could'nt solve it!

Just look at the pattern in the first sample.

Split your n * m board into 2 * 2 squares, and paint these squares like chessboard, but instead of black and white use [[0, 1], [1, 0]] and [[1, 0], [0, 1]].

You can extend this pattern to infinite boards.

wow thanks for the help dude

btw, those squares have to be alternating.

The problems were great. Thank you!

i see your comment in every blogs.. you are so active..

Is it bad?

i guess no .. if you have enough time... just it was my observation..

In the third problem can we like just try to logically make out what the value of all subarrays MEX will be and then the numbers which are constant(mostly 0 & 1 along with some other number in Their MEX) and then fix positions of these numbers or the ranges the number can exist in. After this I am getting a bit lost, can anyone help with this thought process

Really liked the name of Problem E, The best band in the world ❤️

OMG, you're awesome!

You too king ❤️

can someone explain the editorial of B?

In problem E, Can anyone give an example of values of the following dp state. I didn't get what is it actually storing.

dp[i][j]= the best possible maximum if we had number i and the minimum value in the product is j, j is a divisor of i.For a number $$$i$$$ and all ways of writing it as product of some values that are $$$>= j$$$, take the one that has the lowest maximum value. It is easy to see only values that can affect this dp must be divisors of $$$i$$$ so we only need to consider those.

thanks, that helped

Nice contest

Gheal Can you update the test cases for D? They seem to be weak enough to pass a following greedy solution: for each value val of the array, just go through the array from left to right; whenever we meet val, if possible, remove the segment since last val we picked. Something like

would fail this approach. 162829437

This test was added automatically because of a successful hack with it, I'm not sure if the submissions will be rejudged though.

the problem a and c were very similar to codechef problems A was very similar to this problem and C was very similar to this problem

Very Fast Tutorials!

Damn it! I was using LinkedList for D :/

Am I the only one who thought D can be done more easily than C?

lol, I just go in order.

Hey harshitbhatt!Can you Explain the Solution of Problem D a bit more?Thank you!

Amazing C

The problem B is quiet hard to me ;(

The Editorial is fantastic and it is easy to understand.Thanks!

Actually A is the simplified version of this CodeChef problem.That is why I can solve it at 0 minute. Btw isn’t antontrygubO_o the contest admin of Codechef?

Why 256MiB in Problem E?

I spent about 1 hour on this...

B was quite an annoying one

The simplest solution that always works correctly is to find those numbers that gcd(a, b) + gcd(b, c) + gcd(a, c) = n; And if n is even then the possible move will be 0 0 n/2 otherwise there is no solution: int n; cin >> n;

good at problem solving

fazik

Hey Gheal! I was wondering why the hints to problem D seemed pretty difficult to me, but when I opened the "solution" I realised that probably "subsequence" has been used instead of "subsegment" or the more favourable (in my opinion) "subarray".

Please look into that!

My bad. In romanian, the transliterations of subsequence and subarray have swapped meanings. Thank you for spotting this mistake, it has been corrected.

Hey,naman1601! Can you Explain the Solution of Problem D a bit more?Thank you!

Question C how is this kind of question done? I can't deduce. Can you give some methods or suggestions？orz,%%%,thanks.

The first part of editorial for E says:

This dp can be calculated in $$$O(vmax⋅log^2(vmax))$$$ for all valuesWhy not in $$$O(vmax⋅log(vmax))$$$?

Usage of maps for finding at what index would divisor x be in number i.

Can Anyone Explain the Solution of Problem D a bit more?

Why these $$$O(m \cdot log(m))$$$ solutions get TLE? 162900411 and 162902446

I'm quite sure there were solutions in $$$O(log^2)$$$ that passed so I can't figure out how these TLE tbh.

And also, both submissions above are the same. But one gets TLE on test 2, and the other gets TLE on test 13. (You can view their diff in codeforces' submissions compare).

Can someone please explain me the logic behind problem B?

I observed this 2x2 pattern from the given test-cases:

If you place this pattern of [[1, 0], [0, 1]] in the top left 2x2 sub-matrix, then you can alternatively place this pattern and its mirror — [[0, 1], [1, 0]], in the rest of the rows and columns. The design will spread such that all numbers will be guaranteed to have 2 different neighbors.

if in ques 1, if we take 0,0 and that number as addition of 3 with xor are equal to n, why is it wrong??

struck in D can anyone tell solution of D in simpler way?

How to prove a + b = a ⊕ b + 2⋅(a&b) ?

We can think of this in terms of individual bits.

0+0=0⊕0+2*(0&0)=0

0+1=0⊕1+2*(0&1)=1

1+0=1⊕0+2*(1&0)=1

1+1=1⊕1+2*(1&1)=2

Just testing out all of these possibilities, it can easily be seen that the equation holds true.

A more intuitive understanding of the formula would be: the 2*AND operator is there because the XOR operator effectively cancels out a 1 and a 1. Therefore, to account for the case of double 1's, we just need a 2*AND operator. Otherwise if at least a or b is zero, then a+b=a⊕b

Thanks!

a ⊕ b is the sum of individual bits and 2⋅(a&b) is the carry.

damnnnnn 3rd problem... The implementation is too good, my mind is blown. Awesome!!!!!

My solution for D gets AC https://codeforces.com/contest/1699/submission/162975412

but if fails on this testcase:

1

42

1 2 1 2 1 2 1 2 3 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 3 2 1 2 1 2 1 2 1

Hey Gheal, in div2E, why do we update

`smax`

only when`i <= mn`

?`smax`

wouldn't accurately describe the minim balance if`i > mn`

, as that would mean not every element has been taken into consideration (i.e. the minimum)The editorial's way of calculation of the final answer for C was actually pretty nice! I tried using some combination concepts and kept getting runtime errors and a messy code lol.

Can we solve D using doubly linked list? By iterating on the target value in final array?

can anyone one explain condition put in cout statment. For problum B in editorial

good editorial

Hi Just Curious ? how can i solve this gcd(a,b)+gcd(b,c)+gcd(a,c)=n. ?

For Problem E, in the last loop: for (int i = mx; i >= 1; i--) if we change it to i > 1, then we would got WA on testcase 8. So here are my 2-fold question: 1. why does it matter, i== 1 shouldn't update toggle, and hence ptr — i will only get larger. 2. how can i get the full testcase8 in its entirty? Currently, it is too long and shown as ... at the end. thanks

Mycode needs to consider`i = 1`

, as that could be the minimum value. It's true, it does not change the value, but it is the first time the code knows that we have conisdered ever decomposition (and put it in`toggle`

), and as such a better value than the originally considered`mx - mn`

might appear (more specifically, it will be the largest prime divizor — 1). Writing`i > 1`

will affect the code as such to ignore all the possible decompositions made by the code, and it will remain with the default value of`mx - mn`

thank you very much for your quick response!

I wonder is there a solution could make D better than $$$O(n^2)$$$

I guess so but I can't find any.

please anyone can describe the line " cout<<((i%4<=1)!=(j%4<=1))<<" \n"[j==m]; " ?