wow , very fast tutorial

SpeedForces!!

FastEditorialForces

Ура кукарек на Ешке

Thanks for fast tutorial!

bad tests for E

Can someone explain the editorial of D in more detail?

In G, it is possible to replace segtree with DSU to find nearest position with value smaller than $$$p$$$, using the fact that these $$$p$$$ are frequencies so sum of $$$p$$$ is small, and we never decrease them.

MEXForces was fun, E and G were nice IMO

Can anyone help why my submission for D is not working ? Submission

I used binary search to determine the number of operations which must be transferred from ci to c(i+1), is this wrong ?

any one lost problem 3 just because of not able to understand the point( must include all positions of same colour in the rectangle) or is it only me

Thanks for the fast Editorial.

SomethingNew, In problem 1870E - Another MEX Problem ,Why we cannot think DP in this way ?

dp(i,j) -> max bitwise xor till index i inclusive and the last subarray mex is j in getting that. But after defining this like that it will get stuck afterwards. So what is the intutiton of that you used a bool DP as does not come to my thought process.

Is it just try to apply a concept and then see if it works fine or something else need to consider.

Like another DP I think of was like :

dp(i,j,k) -> maximum bitwise XOR till index i inclusive and the last subarray is of length j and its mex is k and we will precalculate mex of all the ranges from 1 to n i.e. 2D mex table.

Why is it wrong ? Is it just that optimal substructure does not suffice in defining in this DP or we can't make transitions that's why?

Any help will be so kind of you and will be very helpful.
Thanking you

Thanks for the fast Editorial.

E tests are weak, it was necessary to add a test

0, 1, ..., n/4-1, 0, 1, ..., n/4-1, 0, 1, ..., n/4-1, 0, 1, ..., n/4-1

This breaks my solution

A similar easy version of the problem C : Max distance of a number greater than a given number in array

Do you remember when the MEX operation felt like something rare and fresh when it appeared ?

Ah, good times

(This is just my salty comment, don't take it too seriously)

My approach is failing for the 1346th test in test case 2. Any one else ?

It is based on Boolean Algebra.: (Assume bitwise OR '|' is represented by '+').

1. For every bi there I got two cases (by expanding XOR and just doing some Boolean Algebra), when n is even and when n is odd a. When n is even : (a1+bi)^(a2+bi)^(a3+bi)^(a4+bi)^... = (a1^a2^...)&() b. When n is odd : (a1+bi)^(a2+bi)^(a3+bi)^(a4+bi)^...^(a(2x+1)+bi) = ((a1^a2^...^a(2x))^())^(a(2x+1)+bi)

As for going through all combinations of or, I have done something similar to the editorial. As the operation of OR is transitive, I sorted b and did the above operation for all is the b-ith and the cumulative Or up-till that point.

If anyone else has experienced the same, or could provide some insight, I'd be grateful.

Thank you very much.

Thanks for the contest! I noticed some small typos in the editorial for E:

• Where it says "there is at most one segment ... where $$$a_l \leq a_r$$$", it should be $$$a_l \geq a_r$$$.

• Where it says $$$MEX(l, r) > a_{r_2}$$$, it should be $$$MEX(l, r_1) > a_{r_2}$$$.

In editorial for E it $$$a_l$$$ is sometimes called smaller than $$$a_r$$$ and sometimes larger. I think it should always be larger for the proof to work

can Someone please provide their code or approach for DIV2C,i got the problem but somehow my code wasn't passing the pretests.

Editorial E:

Let's solve the problem using dynamic programming, let's store dp[i][j] such that dp[i][j]=1 if it is possible to obtain an XOR of MEX values from the prefix up to i (excluding i) equal to x.

Did you mean equal to j (instead of x)?

Anyway E is really bad for any kind of programming contest, since it's so much easier to come up with the correct solution and decide to submit it than it is to prove that it's correct. Your proof is really simple but it's pretty hard to come up with in my opinion

why my code gives wa on test 4

PROBLEM D

https://codeforces.com/contest/1870/submission/223922693

tried to solve problem D using binary search for the contribution of each element, but getting wa on test 3.
Can someone point out the mistake if you have also implemented the same idea 223895614

I have an alternative solution to problem E.

Notice that the maximum MEX of subarray will be O(n), and the maximum XOR of MEXs of subarrays will also be O(n).

You can notice that for a fixed Y, you only care about the first position X, such that you can make the XOR of chosen subarrays equal to Y, while the last subarray ends at position X. This is easy to prove, and I will leave that as an exercise for the reader.

You can also precalculate nxt[l][M] for each pair of (subarray starts at least at position l, MEX of subarray is M). This will store the least position R, such that there exists a subarray [L;R], where MEX is equal to M, and L >= l, if it exists, and -1(something to show that it's not possible) otherwise.

Now what you can do, is write a Dijkstra in O(n^2) where in dist[Y] you store the least position, such that you can chose some subarrays where the last of them ends at position dist[Y], and XOR of their MEXs is equal to Y. To make a transition, you iterate over value of the MEX of the next subarray, and using the precalculated nxt[l][M], you know whether you can make such a transition or not, and what the least next position could be.

I'm confused about the explanation for E and would appreciate it if anyone could explain where I am going wrong.

From my understanding, the tutorial is saying that for each position, it will only show up as the smallest extreme in only one irreplaceable segment. However, take [0, 1, 2]. Isn't 0 the smaller extreme in both [0, 1] and [0, 1, 2] which are both irreplaceable?

Can anyone tell me what is wrong in this soln? It is giving WA in test case 4 and idk how to debug it.

223949565

I came up with the solution to the problem $$$E$$$ with the complexity $$$O(NP)$$$ where $$$P$$$ stands for the number of segments $$$[l, r]$$$ so that $$$mex[l, r]$$$ is equal neither to $$$mex[l+1, r]$$$ nor $$$mex[l, r-1]$$$. Can anyone bound the number of such segments better than $$$O(N^2)$$$?

Can someone explain how we find the irreplaceable segments in Problem E? I understand how it's bounded by 2n but I am not sure how to actually find those segments.

I think calculating $$$\text{dfs}(x)$$$ in $$$O(\log n)$$$ is the hardest part of 1870F - Lazy Numbers. However, some people managed to compute it in $$$< 10$$$ lines using some magic (for example, getid in 223885585). Could anyone elaborate?

Can someone explain how we can find the irreplaceable segments in Problem E? I understand how it' s upper bounded by 2n but how can we find those segments so we can iterate over them.

I had different solution for problem E. In my approach dp[x] means minimum length of the prefix for which it is possible to obtain x as XOR of MEX values from the prefix. And I've precalculated the an array nxt where nxt[i][j] means the minimum value of r where $$$i <= l <= r$$$ and mex of subarray(l, r) is j.

Here's my submission

I had a different approach for problem E. In my approach dp[x] means minimum length of prefix from which it is possible to obtain x as XOR of MEX values from the prefix. I've also precalculated nxt where nxt[a][b] means minimum value of r for which there is an l such that $$$(a <= l <= r)$$$ and mex of subarray(l, r) is $$$b$$$.

Here's my submission

For each $$$a_i$$$, there is at most one irreplaceable segment where it is the smaller of the two extremes, and at most one where it is the larger. Therefore, the total number of irreplaceable segments is no more than $$$2\cdot n$$$.

I think it's not true. Think about $$$a=[0,1,2,3,4,5]$$$. For $$$a_1$$$，there are $$$6$$$ segments where it is the smaller of the two extremes because $$$0$$$ is always smaller, they are $$$[1,1],[1,2],\dots,[1,6]$$$.

I think it can be explained by a way like:

For each segment, we use a pair $$$(i,0/1)$$$ to describe that its greater extreme is $$$i$$$, and the other extreme is at its left side/right side. For a specific pair, there is at most one segment corresponds to it.

Mysterious E

Kindly help with code for problem C. I got the tutorial but need to know how to code prefixes and suffixes.

so fast tutorial! thx! good round.XD

Nowadays difficulty rating of the recent contest problems is not getting updated.

MEXForces

another solution for E. is to for each value v track the first position i where it is possible to create v.

we loop from 1 ~ n keeping track of the the minimum position to create a mex value 0 ~ n with n + 1 sliding windows. Then, if the current index is the first possible position to create a value v we xor the value v with every possible mex and update the min index array.

each value v will only have 1 possible first position so updates are bounded by O(n^2) and maintaining the sliding windows are also bounded by O(n^2) as it costs O(n) each so the final complexity is O(n^2).

https://codeforces.com/contest/1870/submission/223975557

Noob solution for B

223974675

In order for:
Maximising final XOR: we try maximising every bit. Keeping every bit on in the best case scenario.
Minimising final XOR: we try minimising every bit. Keeping every bit off in the best case scenario.

Imagine each of $$$a_i$$$ and $$$b_j$$$ in terms of their bitsets/binary representation.
What is needed for the $$$i^{th}$$$ bit of final XOR to be high/on ?:
At the end of the optimal set of operations (whatever that might be), if we look at the $$$i^{th}$$$ bit of all $$$a_i$$$'s and say $$$count$$$ is the number of high bits, then this $$$count$$$ must be odd.
Similarly, for minimising the $$$i^{th}$$$ bit of final xor: this $$$count$$$ must be even.

Suppose it is possible to get the best-case maximum final XOR (where all bits are high) with just a single operation if we choose an optimal or best number. Lets call the binary-representation of this best number as the $$$optimal$$$ string.

Defining $$$optimal$$$ binary-string/bitest to maximise final XOR:

• if $$$n$$$ is odd: if $$$i^{th}$$$ bit has on-count = odd, then optimal string's $$$i^{th}$$$ bit is unimportant (because no matter what you do, this on-count will stay odd only). Else it must be $$$1$$$ necessarily for optimality.

• if $$$n$$$ is even, then: if $$$i^{th}$$$ bit has on-count = odd, then optimal string's $$$i^{th}$$$ bit must $$$0$$$ necessarily. Else its unimportant(same reason as before).

Defining $$$optimal$$$ binary-string to minimise final XOR:

• if $$$n$$$ is odd, then: if $$$i^{th}$$$ bit has on-count = even, then optimal string's $$$i^{th}$$$ bit must be $$$0$$$ necessarily. Else its unimportant.

• if $$$n$$$ is even, then: if $$$i^{th}$$$ bit has on-count = even, then optimal string's $$$i^{th}$$$ bit must is unimportant. Else it must be $$$1$$$ necessarily.

At this point, I should have pivoted to notice/reinterpret the situation in terms of the fact used by editorial. But anyways since I couldn't see it, here is an alternate approach, although dumb, unnecessary and laborious.

The $$$optimal$$$ strings just defined may or may not actually exist in the array $$$b$$$. So, we have to find that set of elements of $$$b$$$ whose cumulative $$$OR$$$ satisfies these $$$optimal$$$ strings as best as possible.

Strategy for finding the best fit set of elements of $$$b$$$ for the optimal strings:

• Convert all elements of $$$b$$$ in to their bitsets or binary strings before going to next step.
• Those strings of $$$b$$$ that defy the $$$optimal$$$ strings at the positions where the $$$optimal$$$ string required a $$$0$$$ or off bit to be present, cannot be the part of the best-fit set of elements. (Because a high bit once produced cannot be reverted no matter what).
• However those strings of $$$b$$$ that defy the $$$optimal$$$ strings "only" at the position where the $$$optimal$$$ string required a $$$1$$$ to present, can be forgiven and included in the best-fit set.

Thus, we have the two different best-fit set of $$$b$$$-elements for maximising and minising the final XOR. Now, the solution is straightforward, just calculate the final XOR by applying the operation in problem statement for all elements of the best-fit sets.

223974675

IN D question :-i have taken best possible answers from min1 to min2 , min1 to min3 , min1 to min4 ....... then why it is giving error.?

vector<int>v;
for(int i=0;i<n;i++){
    int x;
    cin>>x;

    v.push_back(x);
}

    int ind=0;
    for(int i=0;i<v.size();i++){
       if(v[i]==p){
         ind=i;
       }
    }
    int c1=k/p;
    vector<int>temp(n,0);
    temp[ind]=c1;
    vector<int>temp2=temp;
    vector<pair<int,int>>v1;
    // till index=ind;
    v1.push_back({temp[ind],0});
    int rem=k%p;
    for(int i=ind+1;i<n;i++){
       int cost=v[i];
       if((p+rem)>=cost){
         v1.push_back({temp[ind],i});
         temp=temp2;
       }
    }

sort(v1.begin(),v1.end(),greater<pair<int,int>>());// to find best possible answer

debug(v1);
int b1=v1[0].first;
int b2=v1[0].second;
for(int i=ind;i>=0;i--){
    temp[i]=b1;
}
if(b2>0){
    debug(b2);
for(int i=b2;i>ind;i--){
    temp[i]=1;
}
}
for(auto &x:temp){
    cout<<x<<" ";
}cout<<endl;
}else{
    cout<<0<<endl;

}
}

Can someone explain the editorial of D in more detail?

Please give the code for F, as "To find dfs(x) , we can traverse up from the trie node corresponding to x , and at each step, add the sizes of the subtrees that we have traversed in DFS before the subtree with the node x ." is too ambigious for me to make sense of.

Thanks for the good contest!

Can someone explain the editorial of E in more detail?

Problem C: how to find the longest prefix and suffix with elements < x for each color x?. I cant do this in O(n). I can do this in O(n^2). Please explain

Can someone explain why is my Code failing on testCase-3 ? 223975030-->Problem-D

Problem-D : Why is my code wrong ?? 223975030

Can we also have the code part in editorial ?

Can Anyone point out the error in my solution? It is failing at 113th position in test 2. We should be allowed to see all test cases after the contest is over. I have used a set to find the minimum price. Any help is appreciated.

Why every editorials is very fast in codeforces

Can someone please tell what is wrong in my code for problem D? my submission

I think i have implemented the exact same solution as given in editorial, but still it is failing in test 2. Any help is appreciated.

I have tried solving problem E by pre calculating mex's of all the subarrays and then use dp to pick some ranges and xor the mex of all the picked ranges.

Getting WA on TC 11.

Link to submission: E

What is wrong with this approach ? Can anyone please explain ?

why not use binary search in G ?

why not use binary search in G ?

Any counter Test, or place at what i done mistake for D

https://codeforces.com/contest/1870/submission/224114880

.

What's 114th input in testcase2 of D?wtf man

can any one explain why this brute force got accepted. https://codeforces.com/contest/1870/submission/224151942

can someone tell why my submsission for c is giving tle https://codeforces.com/contest/1870/submission/224157785

wrong answer 807th numbers differ — expected: '1', found: '0' , in D ????help! here's my pycode

can someone tell error in my submission for problem c https://codeforces.com/contest/1870/submission/224161992

In 1870B - Friendly Arrays, why are we so sure that we will be using all b[j], maybe there is a case where using only one element from b[] gives us a min and max XOR respectively. Or am I reading the question wrong, because the question only says "You can choose any element bj from array b (1≤j≤m), and for all 1≤i≤n perform ai=ai|bj for all bi You can perform any number of such operations."

hi, I am unable to understand the tutorial of problem C. I'll be really glad if someone could explain in more depth than the tutorial. Thanks.

Another (more complicated but still pretty cool) solution to G:

One of the initial ideas that I had was to define the value of a number which will be 2^v. Then if the sum of the values of all the numbers is = 2^m where m is the mex, then potentially we can create m.

This does not work though, because lets say we try to create m, and we have two (m — 1)'s. This, though has the same value sum as 0, 1, 2,.... m — 1, does not create m. This leads us to another definition: space. Let space be equal to the maximum number of is that we can have. This then gives us that after processing number i, x = 2 * x — min(x, cnt[i]). Then, if we compute the space of all i (in reverse) up to 0, the space must be equal to or less than the number of zeros we can create. Now, you can create a bunch of functions f(x), which essentially represents this: 2 * x — min(x, cnt[i]) for each i. Now, an issue is that we also need to count the number of zeros we can create. The number of zeros we can create is the number of this not in the range [1, m — 1] PLUS when calculating f(x), which x < cnt[i], we wont use cnt[i] — x numbers, and we can turn those into zeros aswell. This means we need to a datastructure to support the following: maintain f0(f1(f2(f3(...fn(x)...))) (where fi(x) is the space function for number i), but also the zeros, which will be g0(f1(x)) + g1(x) for the n = 2 case. We can simply do this with a segment tree. This leads to a solution (with a couple constant optimizations) that passes. The issue is, theoretically, if each of these functions that we maintain have size O(n) (which I do not this is true but not sure how to prove) re-merging all of the functions every time an update happens should theoretically be O(n). This can be fixed with sqrt decomp, splitting it up into sqrt(n) functions, where to compute the final answer we use binary search on each of those functions. Every update is O(sqrt(n)) but every query is O(sqrt(n) log n) because of binary search, but this, with optimal blocking will result in O(sqrt(n log n)) (the logn factor is quite optimal because its simple binary search on an array). This leads to a slightly faster solution, saving around 150ms.

Without sqrt decomp: 224529457

With sqrt decomp: 224527332

where is the code

I have implemented Problem D using stack.

#include<bits/stdc++.h>
using namespace std;

void solution() {
    int n; cin >> n;
    map<int, int> loc;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        loc[x] = i;
    }
    loc[1e9] = -1;
    int k; cin >> k;
    int idx = -1;
    stack<pair<int, int>> s;
    s.push({0, 1e9});
    for (auto [x, i] : loc) {
        if (i < idx) {
            continue;
        }
        idx = i;
        auto [minE, minI] = s.top(); s.pop();
        int diff = (x - minE);
        int lim = min(minI, k / diff);
        k -= diff * lim;
        s.push({minE, minI - lim});
        s.push({x, lim});
    }
    vector<int> a(n);
    while (s.size() > 1) {
        auto [x, i] = s.top(); s.pop();
        a[loc[x]] = i;
    }
    for (int i = n - 1; i > 0; i--) {
        a[i - 1] += a[i];
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int __; cin >> __;
    while (__--) {
        solution();
    }
    return 0;
}

Can someone help me in finding a test case for which my solution fails.

Approach: Go from right and take the element that can give maximum buys. After that if there is a remainder, take 1 less buy and try to recursively again find an element from the right that gives maximum buy. Do this till we have k >= 0 or we don't repeat a number.

One can solve D recursively:

• Take the rightmost element with the lowest cost $$$c_i$$$ as much as possible.

Now, upgrading to an index $$$j$$$ further to the right costs $$$c_j-c_i$$$.

• If we have coins left, decrease all costs to the right by $$$c_i$$$ and solve the new problem (with remaining coins) recursively until no further upgrade is possible.

include<bits/stdc++.h>

using namespace std; int main() {

int t ;
cin>>t;
while(t--)
{

   int n;
   cin>>n;
   int a[n];
   for(int i=0;i<n;i++)
   {

       cin>>a[i];
   }

   int k;
   cin>>k;
   int mn=INT_MIN;
   int inx=-1;
   int ss=-1;

   for(int i=0;i<n;i++)
   {

       if(k/a[i]>=mn)
       {

           mn=k/a[i];
           ss=a[i];
           inx=i;

       }
   }

      int p=k/ss;

      int dd=(p%ss)+ss;
      int lst=-1;


      for(int i=inx;i<n;i++)
      {

           if(a[i]<=dd)
           {


                 lst=i;



           }


      }



         for(int i=0;i<n;i++)
         {

             if(i<=inx)
             {
                 cout<<p<<" ";
             }

             else if(i>inx && i<=lst)
             {



                 cout<<1<<" ";
             }


             else
             {

                 cout<<0<<" ";
             }


         }
            cout<<endl;



}

} why this solution doesnot work for D???