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

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

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://mirror.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

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://mirror.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

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 why is my Code failing on testCase-3 ? 223975030-->Problem-D

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

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.

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://mirror.codeforces.com/contest/1870/submission/224114880

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

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

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???