### SomethingNew's blog

By SomethingNew, history, 12 days ago, translation,

We apologize for the technical difficulties in Task B. We hope you enjoyed the rest of the contest. We will add hints soon.

1870A - MEXanized Array

Tutorial

1870B - Friendly Arrays

Tutorial

1870C - Colorful Table

Tutorial

1870D - Prefix Purchase

Tutorial

1870E - Another MEX Problem

Tutorial

1870F - Lazy Numbers

Tutorial

1870G - MEXanization

Tutorial
Proof of asymptotic complexity for the query

1870H - Standard Graph Problem

Tutorial

Please rate the problems, it will help us make the problems better next time!

Problem Feedback
• +202

 » 12 days ago, # |   -8 wow , very fast tutorial
 » 12 days ago, # |   -40 SpeedForces!!
 » 12 days ago, # |   +15 FastEditorialForces
 » 12 days ago, # |   0 Thanks for fast tutorial!
 » 12 days ago, # |   +11 bad tests for E
 » 12 days ago, # |   +2 Can someone explain the editorial of D in more detail?
•  » » 12 days ago, # ^ |   +3 Basically, the idea in this problem is to greedily choose which prefix to use. As the editorial explains, we first choose the minimum prefix that's the farthest from start (say it's like 3 4 3 6 5, k = 11, we choose the last 3). Now, whatever we have left over is k%3 because we are going to use as many as possible. With this remainder, we can improve our solution. in the example above, remainder is 2 and we can upgrade one of the 3s to a 5 because the difference is <= remainder. We repeat this process and each time the remainder keeps getting smaller. Also, another requirement is that the number of upgrades you can make from previous step to next step is upper bounded by the previous step. Think about why this makes sense. You cannot upgrade more things than that are currently existing. You can checkout my profile for a simple solution using maps and a special type of suffix array. Let me know if you need any clarifications.
•  » » » 11 days ago, # ^ |   0 Hello SaiAnoop, can you help explain why it is possible that the number of upgrades you can make from previous step to next step is not upper bounded by the previous step when ci>=ci-1？ I did not use this restriction and failed.
•  » » » » 11 days ago, # ^ |   +3 Actually, I don't know if you read it wrong or if I didn't say it correctly, but the number of upgrades you can make from a previous step to a next step is upper bounded by the previous step. In other words, say I have costs x,y,z x < y < z. First, I maximize number of x, then with the remainder k%x, we will try to replace some of the x with y. this number is remainder / (y-x). We continue this process until remainder equals 0 or we reach end of array. Now, to prove the point about why we need to upper bound, consider this example (this is what I used to figure out the logic during the contest): 99 99 99 10 99 99 15 99 99 16 99 99 99, k = 219 Now, based on our algorithm, we will first do 21 x 10 = 210 remainder = 9 Using these 9, the next best element is 15, so we do 9/5 = 1 9%5 = 4 now, if we don't upperbound we will end up doing 16 4 / (16-15) = 4 but this doesn't quite work because if you remember the original remainder was 9. now if we do 4*(16-10) that comes out as 24. So we are overcounting, so therefore, we need to upper bound by the previous step. Without using the math, to think in logical terms, we are trying to upgrade some of the previous steps into next steps, how can you possibly upgrades more next steps than there are total # of previous steps. I hope this helps.
•  » » » » » 11 days ago, # ^ |   +8 Thank you very much for your careful reply, especially the wonderful example. I have understood the solution.
•  » » » » » » 11 days ago, # ^ |   +8 ofc. glad I could help!
•  » » » » » » » 7 days ago, # ^ |   0 if(lastind != -1) { q = min(q, ans[lastind]); } can you explain why was this requiredi got WA when i commmented it but i dont understand why
•  » » » » » » » » 6 days ago, # ^ |   +1 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } if you see how i initialize lastind, initially set to -1 just as default value. if it's equal to -1, then it's a dummy value and not actually last index, so we check to make sure it's a real last index and not a dummy value.
•  » » » 11 days ago, # ^ | ← Rev. 2 →   0 i have made the same approach as you said, but i got some wrong test cases this is my submission: https://codeforces.com/contest/1870/submission/224067985every loop I repeat what I have done with the first minimum element but taken k % last_minimum_element then storing the answer in an vector of pair containing the value to print and the index to print up to itwhy it gives my wrong answer?
•  » » » » 10 days ago, # ^ |   0 Try this2 5 8 10 5 7 10 9 6 6 5 8 5 6 7 7 Correct answer1 1 1 1 0 1 1 1 1 1 1
•  » » » » » 9 days ago, # ^ |   0 https://codeforces.com/contest/1870/submission/224250810 Can u say where am I wrong Give me a test case
•  » » » » » » 9 days ago, # ^ |   0 Try this1 7 100000 114286 116667 117143 117262 117302 117321 799999 Correct answer7 6 5 4 3 2 1
•  » » » » » » » 8 days ago, # ^ |   0 Bro how do u test this solution and get the wrong test case, Can u please share the software for the same
•  » » » » » » » » 8 days ago, # ^ |   0 The above test case which I provided you is included in the main tests of the question itself. However by modifying this code you may generate some simple test cases. Also you may write some code to directly give you a test case where your code is failing by comparing it to an accepted code.
•  » » » 9 days ago, # ^ |   0 I have done the same approach as yours for D https://codeforces.com/contest/1870/submission/224250810 Can u say where am I wrong Give me a test case
 » 12 days ago, # |   +11 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.
•  » » 11 days ago, # ^ |   0 Could you elaborate more?
 » 12 days ago, # |   -18 MEXForces was fun, E and G were nice IMO
•  » » 12 days ago, # ^ |   -11 O sa vorbim cand ai locul 1 la bacterii2
 » 12 days ago, # | ← Rev. 2 →   0 Can anyone help why my submission for D is not working ? SubmissionI used binary search to determine the number of operations which must be transferred from ci to c(i+1), is this wrong ?
•  » » 11 days ago, # ^ |   0 You can take a look at this solution, I also used binary search for finding how much should be transferred, from current to the smallest element to right of current. https://codeforces.com/contest/1870/submission/224001124
•  » » » 11 days ago, # ^ | ← Rev. 2 →   0 Thanks, in your approach, you start resulting array from maximum element from the left, why don't we start resulting array from minimum element from the left ? Greedily we should start from minimum left I guess. Please correct me if i am wrong
•  » » » » 10 days ago, # ^ |   0 I am doing that only, I am taking the minimum element (mn) go to that and after that I get to the smallest element to the right of mn (which is obviously greater than mn as mn was the smallest number yet) make the transfers if possible and go on, if no transfer was possible then break
•  » » 9 days ago, # ^ |   0 Why is your code so long? :sob:
 » 12 days ago, # |   0 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
•  » » 12 days ago, # ^ | ← Rev. 5 →   0 I've managed to submit it on the last two minutes of the contest. So basically this rectangle should contain every element of same color (number less or equal to k). That means upper bound of this rectangle is equal the minimal i for all common numbers, as well as left bound = minimal j, bottom bound = maximal i, right bound = maximal j.So for example, if you have matrix like this: 1 1 1 1 1 1 2 1 1 2 1 2 1 1 2 1 The both sides of rectangle of color 2 will be equal to 3: * * * * * # # # * # # # * # # # Hope that helps.
 » 12 days ago, # | ← Rev. 8 →   -49 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
•  » » 11 days ago, # ^ | ← Rev. 3 →   0 "Is it just try to apply a concept and then see if it works fine or something else need to consider". Just practice!
•  » » » 11 days ago, # ^ | ← Rev. 2 →   -16 SomethingNew, Can you please reply? I have been stuck for a long time that's why I asked you about the mistake in thought process i am thinking
•  » » 11 days ago, # ^ |   +20 Xor is not like sum, Max xor isn't necessarily obtained by another maximum xor , it can possibly be obtained by any other xor value as well. That's why your dp is wrong.
•  » » » 11 days ago, # ^ | ← Rev. 3 →   -16 devesh_7, thanks for your time but can't we do like this as below :let DP(i,j,k) -> max bitwise xor till index i inclusive it and last subarray taken mex is j and of length k. And also pre-calculate 2D mex table so that we can access all mex value for ranges in constant time. Now the transitions will be like this : DP(i,j,k) = max( DP(i-k,p,q) XOR mex(i-k+1,i) ) where p ranges from 0 to n+1 and q ranges from 1 to i-k; What will be wrong in this because i am more interested why this will not work. SomethingNew and glebustim, can you please also look into this.
•  » » » » 11 days ago, # ^ |   +10 You missed the whole point of my comment. Max Xor is not necessarily obtained by another maximum Xor. That's why We are interested in all possible Xor values.
•  » » » » » 11 days ago, # ^ | ← Rev. 2 →   -19 devesh_7 No,I understood your above comment and not neglecting that but why this DP is wrong then or is the above one is not DP . It's just recursive brute-force ??
•  » » » » » » 11 days ago, # ^ | ← Rev. 2 →   -32 Ok I think this DP is not DP its just i have for the sake of formulating DP I have just somehow made it. Its like exponential recursive brute force that is not DP actually then. Am i correct here ? SomethingNew, glebustim, devesh_7, Sorry for pinning you guys again and again but till now no one original author , editorialist not replied but only downvoted me. (I don't know why? )
•  » » 11 days ago, # ^ |   -15 Have i asked a wrong question here on the site, Why so many downvotes ?? It is a question that i have been stuck for a long time and genuinely someone to guide upon. So can anyone explain the reason behind this.
•  » » 11 days ago, # ^ |   0 Curse of low rated questions, thats why it so downvoted:)
•  » » » 11 days ago, # ^ |   -13 Okay so everyone who downvoted knows the answer for the question then why they just did not reply to it.
•  » » 11 days ago, # ^ |   0 Why is it wrong ?It is not wrong. You can define DP in anyway you like. A given DP is said to have Optimal Substructure Property if the optimal solution of the given problem can be obtained by using the optimal solution to its subproblems instead of trying every possible way to solve the subproblems.Being able to make transitions and having optimal substructure have similar meaning. I think your problem was downvoted because your fundamentals are not clear. And also, you are tagging the author himself for such doubts. Generally, people are busy and don't have enough time to reply.
•  » » » 11 days ago, # ^ |   0 Okay , so finally someone replied to my question.Thank you so much adityagamer.
 » 12 days ago, # |   0 Thanks for the fast Editorial.
 » 12 days ago, # | ← Rev. 3 →   +66 E tests are weak, it was necessary to add a test0, 1, ..., n/4-1, 0, 1, ..., n/4-1, 0, 1, ..., n/4-1, 0, 1, ..., n/4-1This breaks my solution
•  » » 12 days ago, # ^ |   0 Can you please explain your solution and with does this case break your solution? I'm just curious.
•  » » » 11 days ago, # ^ |   0 If there are two segments [l, r1], [l, r2] (r1 < r2) with the same mex, then in DP I iterate only the first one. There can be O(n^2) such segments and my solution works in O(n^3)
•  » » » » 11 days ago, # ^ |   +8 Lol, I did that but with the roles of l and r reversed. Got TLE on pretest 8.
•  » » » » 10 days ago, # ^ |   0 Hey Hi, @dimss I saw you solution for problem E its really nice. but I am not getting how its working in O(n^2). can you please explain time comp. once please. I just have doubt where you are updating the other state using vector_pair.
•  » » » » » 10 days ago, # ^ |   0 It works in O(n^3)
 » 12 days ago, # | ← Rev. 6 →   -12 A similar easy version of the problem C : Max distance of a number greater than a given number in array
 » 12 days ago, # | ← Rev. 2 →   +63 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)
 » 12 days ago, # |   0 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 '+'). 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.
•  » » 12 days ago, # ^ |   0 homie are you sure, this is gonna work?, using boolean algebra, complexifies it instead of simplification.
•  » » 12 days ago, # ^ | ← Rev. 2 →   0 rather think it of as in this way,consider the numbers are even, if we, take any number from b and take its OR, then some set bits are gonna remain set, and some unset bits will get set, now xor of two set bits is 0, hence OR is always gonna be less. Whereas it's opposite in Odd's case.Now the maximum number that you can take for ORing is OR of array B.
•  » » » 12 days ago, # ^ | ← Rev. 2 →   0 Approach was right, silly mistake.. for calculating minimum and maximum, I initialized it to the xors, The fact is it can go below XOR of all the elements. That was stupid and cost me the contest :(
 » 12 days ago, # |   +11 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}$.
•  » » 12 days ago, # ^ |   +9 thanks bro
 » 12 days ago, # |   0 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
 » 12 days ago, # | ← Rev. 2 →   0 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)?
•  » » 12 days ago, # ^ |   0 yes
 » 12 days ago, # | ← Rev. 2 →   +139 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
•  » » 12 days ago, # ^ |   +72 I think this is the difference between programing and math. you don't need to proof something if it is reasonable.
•  » » » 12 days ago, # ^ | ← Rev. 2 →   0 What is reasonable? I came up with the correct solution pretty fast and I think that the fact that I couldn't find the proof for a much longer time means that it was not reasonable to assume that it works. Usually when I don't prove something during contest it's because I understand that I can prove it in a couple of minutes and that's what I would call reasonable. Otherwise it's no different from submitting every idea you have when you don't know how to counter it, and I think that penalties for wrong submissions are meant to disincentivize that kind of behaviour, so it's not intended for a non-IOI style contests
•  » » » » 12 days ago, # ^ |   +77
•  » » » » » 12 days ago, # ^ |   +2 Примерно такого ответа я и ожидал) the meme could've been in english though
•  » » » » 10 days ago, # ^ |   +23 You shouldn't necessarily submit every idea you can't come up with a break case for, instead if you suspect something is true (but don't have a proof), why not write some code to generate all arrays of size 9, and see that the maximum number of important subarrays is on the order of n rather than n^2 (affirming your suspicion), and then implement your solution. If you're still interested in it, you can work on/learn about the proof after the contest.The difference between a programming and math contest is in a programming contest you have a computer, you should use it.
•  » » » » » 10 days ago, # ^ |   +40 even that is unnecessarily 10mins wasted (assuming youre really fast in coding all that), and small numbers wont even tell you much, since the difference between O(n^2) (with small constant) and O(n) (with high constant) isnt even that large. if a proof is harder than the rest of the problem, thats a bad problem for a programming contest, or any contest where you dont need to write a proof.
•  » » » » » » 10 days ago, # ^ | ← Rev. 2 →   +25 I don't think it's a waste of 10 mins if it allows you to solve the problem, but the constant could obfuscate it (agree)I see your point about the proof, I personally feel like it's still an interesting problem, and it doesn't necessarily make it bad, but I see why you disagree
•  » » 12 days ago, # ^ |   +20 I came up with "there should be a small number of expandable intervals" pretty fast but didn't bother to prove it. Solved it in a different way using dp[xor] = the smallest prefix with xor obtainable.
•  » » 11 days ago, # ^ |   +15 I've come up with a solution that needs no proof though, just wanna share bcz it's really nice. Here is my code.(This is my first time writing a solution so sorry if it's too long lol, recommend reading the code first before coming back here for clarification. TLDR: use a traditionally approached dp and make sure not to repeat an $i$ $XOR$ $j$ operation with the same $(i,j)$ too many times.)Here are the steps: Calculate every achievable $XOR$ value of $MEX$ of subarrays of prefix up to $i$-th element. (In other words, replace the initial array with its prefix (1 to $i$) then calculate all possible values). DP $i$ from 1 to $n$ then store it in a vector $can[][]$. To compute $can[i]$, iterate backward $j$ from $i$ to 1, calculate $mex[j,i]$ (the transition from $j$ to $j-1$ can easily be done in $O(1)$), and then $XOR$ $mex[j,i]$ with every element of $can[j-1]$, then store the results in $can[i]$. $can$ stores $O(n^2)$ elements, let's make it $O(n)$: to avoid repetition, every elements of $can[j]$ with $j check$ if a number was stored while iterating dp. // It will be helpful later on to reduce time complexity. Here's the tricky part: the complexity of the above process is $O(n^3)$, so let's optimize it to $O(n^2)$. Note that the value of $mex[j,i]$ can't exceed $n$. Therefore, we can use another $vector > CHECK$ (sorry I was low on time while coding this lol) where $CHECK[i][j]$ returns true when the number j was already $XOR$-ed with all of the elements in $can[i]$ (and false otherwise). While iterating $MEX[j,i]$ $XOR$ with $can[i]$, (let $pt=MEX[j,i]$) if $CHECK[j-1][pt]==0$ then we $XOR$ $pt$ with $can[j-1]$ and then continue with $j-2$, if $CHECK[j-2][pt]==0$ then continue with $j-3$, and so on. It's easy to prove (ok probably the only part we need to prove lol) that after the process, we can ensure $pt$ was $XOR$-ed with all possible $XOR$ values of prefix up to $j-1$ (aka $CHECK[k][pt]==1$ for all $k$ from 1 to $j-1$) After the optimization, we can ensure that for every $j \in [1,n]$, every possible $XOR$ values (that is stored in $can[][]$) was $XOR$-ed with $j$ at most 1 time. Therefore the total number of $XOR$ operations we have to carry out is at most $O(n^2)$, resulting in the overall complexity $O(n^2)$. done phew. Thanks for reading all the way here xD. Plz let me know if there are any unclear parts. only if I had 15 minutes more to submit it during the contest T_T see you again yellow
 » 12 days ago, # |   -8 why my code gives wa on test 4PROBLEM Dhttps://codeforces.com/contest/1870/submission/223922693
 » 12 days ago, # |   +5 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
•  » » 11 days ago, # ^ | ← Rev. 2 →   +1 We made the same mistake.This is happening because we started replacing elements from the end, which might lead to a smaller array lexicographically. This happens when you use the same number of coins, but there exists a position between two positions in your solution such that you could've taken extra coins from the larger index to increase the prefix spanned by the smaller index. For example-Consider n = 5, c = [10 2 2 2 3] & k = 7The answer is [3 3 2 2 0] in this casebut you find the answer to be [3 3 1 1 1]Edit: This example is wrong. However, a correct example is in the following comments!
•  » » » 11 days ago, # ^ |   +3 But the ans will be [3 3 3 3 1] and my code is working right for this test case.
•  » » » » 11 days ago, # ^ | ← Rev. 3 →   +1 Ah, okay, so my example was wrong, but the whole idea why the solution doesn't work is the same.Try this instead-n = 4c = [40 41 46 47]k = 253Your code(I tested this time) answers [6 2 2 1]But if I buy five c2 and one c4, I'd use a total of 243 coins and get the answer [6 6 1 1] And that is lexicographically larger.
•  » » » » » 11 days ago, # ^ |   0 Thank you so much for pointing the mistake.
•  » » » » » 11 days ago, # ^ |   0 Excuse me, but isn't the answer for this test is$ans = [6,6,1,1]$You can buy $c_2$ $5$ times which equals $205$, so you have remaining coins equals $253 - 205 = 48$ which is sufficient to buy $c_4$ onceSo by that we obtained larger lexicographically ansCorrect me if I misunderstand something
•  » » » » » » 11 days ago, # ^ |   0 Yes, thank you for pointing out the mistake. I was trying to show that there exists a better answer- I wasn't looking at the final solution. My bad!
•  » » » » » » » 11 days ago, # ^ |   0 No problem my friend, thanks for that test btw, it showed me the wrong in my approach and it pointed me to the right solution!So, I'm the one who needs to thank you ^^
 » 12 days ago, # |   +185 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.
•  » » 12 days ago, # ^ |   +38 Oh, this is so much more intuitive than the intended solution. Honestly, I even feel bad now for not thinking about that during the contest...
•  » » 11 days ago, # ^ |   0 Could you share the intuition why this approach works?
•  » » 9 days ago, # ^ |   0 I implemented it but got tle at test 10
•  » » » 9 days ago, # ^ | ← Rev. 2 →   +3 Hey, so, first of all, you don't have to use set to get MEX of all subarrays, you can do it in $O(n^2)$ total time complexity, by fixing one border of subarray, iterating over the other, and MEX can only increase, so it's possible to use two pointers(store in some bool array values that you have already, or smth like that).Secondly, you don't need to use Dijkstra with priority_queue, the given graph is not sparse(in fact it's complete), so it would be better to use Dijkstra in $O(n^2 + m)$, without priority_queue.
•  » » » » 9 days ago, # ^ |   0 Thanks
 » 12 days ago, # |   0 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?
•  » » 11 days ago, # ^ | ← Rev. 3 →   +1 It should actually be, "$a_i$ can be the larger element and the left extreme atmost once, and it can be the larger element and the right extreme atmost once." SomethingNew
•  » » » 11 days ago, # ^ |   0 Yes, thanks
 » 12 days ago, # |   -8 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
•  » » 11 days ago, # ^ |   0 Try this: 1 3 10 15 16 49
•  » » » 11 days ago, # ^ |   0 output is 4 1 0 , isnt it correct?
•  » » » » 11 days ago, # ^ |   0 nope, ans will be 4 1 1
•  » » » » » 11 days ago, # ^ |   0 okay, thanks found my mistake..
•  » » » 11 days ago, # ^ |   0 224037810 mine give the right output on your case but still WA on the same test as his.
•  » » » » 10 days ago, # ^ |   0 Try this1 6 6 5 8 5 6 7 7 Correct answer1 1 1 1 1 1
 » 12 days ago, # |   +9 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)$?
•  » » 12 days ago, # ^ |   +18 Your segments coincide with the segments in the editorial.
•  » » » 11 days ago, # ^ |   0 Yup, my bad
 » 12 days ago, # | ← Rev. 2 →   +10 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?
•  » » 11 days ago, # ^ |   +20 Suppose that $x$ has $d$ digits, we count all $y$ such that $y$ comes before $x$ in dfs order. We iterate over the number of digits of $y$, let's denote it by $e$. We have inequality $k^{e-1} \leqslant y \leqslant min(x', n)$, where:Case $e \leqslant d$: $x'=floor(x/k^{d-e})$, i.e. the prefix of $x$ of length $e$.Case $e > d$: $x'=x\cdot k^{e-d} + k^{e-d} - 1$, i.e. $(k-1)$'s appended to the back of $x$.
•  » » 10 days ago, # ^ |   0 Maybe you can read jiangly's code, I think it's clear enough.
 » 12 days ago, # |   0 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.
•  » » 12 days ago, # ^ | ← Rev. 2 →   +8 You just need to check $[l, r-1]$ and $[l+1, r]$. Proof: if $\text{mex}(l, r) = \text{mex}(l', r')$, and $l \leq l' \leq r' \leq r$, then $\text{mex}(l'', r'') = \text{mex}(l, r)$ for every $l \leq l'' \leq l'$ and $r' \leq r'' \leq r$.
•  » » 10 days ago, # ^ |   0 Hi SaiAnoop , can you please explain how its upper bounded by 2n, Thanks!!
 » 12 days ago, # | ← Rev. 3 →   +25 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
 » 11 days ago, # | ← Rev. 2 →   +10 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.
 » 11 days ago, # |   0 Mysterious E
 » 11 days ago, # |   0 Kindly help with code for problem C. I got the tutorial but need to know how to code prefixes and suffixes.
 » 11 days ago, # |   0 so fast tutorial! thx! good round.XD
 » 11 days ago, # |   +10 Nowadays difficulty rating of the recent contest problems is not getting updated.
 » 11 days ago, # |   +28 MEXForces
 » 11 days ago, # |   0 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).
•  » » 11 days ago, # ^ |   0 whoops, did not notice someone else alr posted about this
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 alternative proof for number of irreplaceable sub-arrays:let mex[l][r] be the mex of a[l], a[l + 1], ... a[r], the array mex[l][1 ... n] can have at most n distinct valueseach first distinct value of mex[l] that differs from what it becomes in mex[l + 1] will be counted as an irreplaceable subarray notice that each value that changes between mex[l] and mex[l + 1] will become the same value namely a[l] in mex[l + 1] because we're removing a[l] from being considered in the mex calculations.let dec[i] be the number of distinct numbers that change between mex[l] and mex[l + 1], the number of distinct numbers of mex[l + 1] will be less than the number of distinct numbers in mex[l] — dec[i] + 1.the number of distinct numbers in mex[n] will be less than the number of distinct numbers in mex[1] — dec[1] + 1 — dec[2] + 1 ... — dec[n] + 1. This implies the sum of dec[1 ... n] is less than n (initial distinct number count) + n (possible increase in distinct numbers).
»
11 days ago, # |
Rev. 3   +3
##### 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

 » 11 days ago, # |   0 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.? Spoilervoid solve(){ int n; cin>>n; vectorv; for(int i=0;i>x; v.push_back(x); } int k; cin>>k; int p=*min_element(v.begin(),v.end()); if(p<=k){ int ind=0; for(int i=0;itemp(n,0); temp[ind]=c1; vectortemp2=temp; vector>v1; // till index=ind; v1.push_back({temp[ind],0}); int rem=k%p; for(int i=ind+1;i=cost){ v1.push_back({temp[ind],i}); temp=temp2; } } sort(v1.begin(),v1.end(),greater>());// 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<
 » 11 days ago, # |   0 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!
 » 11 days ago, # |   0 Can someone explain the editorial of E in more detail?
 » 11 days ago, # |   0 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
 » 11 days ago, # |   0 Problem-D : Why is my code wrong ?? 223975030
•  » » 11 days ago, # ^ |   0 my logic is same like you . and got the same error on the same testcase. after last 2 hrs debugging i dont find the exact reason but it may be the code is giving runtime error on some testcases (it is 52 after dbeugging in my code). which results in to automatically jumping of testcases to 93(it sounds wierd).
•  » » 11 days ago, # ^ |   -11 try case 1410 12 13 14 99answer should be 9 3 2 1
•  » » » 11 days ago, # ^ |   +1 i think the answer should be 9 4 1 0 ,and this is my code 224008681,i can't find my fault,can anyone tell me what is wrong in my code?
•  » » » » 11 days ago, # ^ |   0 You need to perform ans[0]=1e9+5 inside the while(t--) loop, since ans[las] -= tmp; may change the value of ans[0]. Also, inside the while(1) loop, you need if(cnt>=n) break; instead of if(cnt>n) break;.
 » 11 days ago, # |   0 Can we also have the code part in editorial ?
 » 11 days ago, # | ← Rev. 2 →   0 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.
•  » » 10 days ago, # ^ |   0 i m failing at 114.lol
 » 11 days ago, # |   +3 Can someone please tell what is wrong in my code for problem D? my submissionI think i have implemented the exact same solution as given in editorial, but still it is failing in test 2. Any help is appreciated.
•  » » 11 days ago, # ^ |   +3 Try to declare int cnt = 1e9; at the beginning of the solve() function, and instead to perform int cnt = k/(curr - prev);, use cnt = min(cnt, k/(curr - prev)); since the variable cnt means that you "replace" cnt previous purchases into the current ones, so the current cnt mustn't exceed the previous cnt.
•  » » » 11 days ago, # ^ |   +3 Thanks prairie2022, it worked!
•  » » » » 11 days ago, # ^ |   +3 You're welcome.
•  » » » 10 days ago, # ^ | ← Rev. 2 →   0 Can you see mine https://codeforces.com/contest/1870/submission/224114880
 » 11 days ago, # |   0 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 ?
 » 10 days ago, # | ← Rev. 2 →   0 Any counter Test, or place at what i done mistake for D https://codeforces.com/contest/1870/submission/224114880
 » 10 days ago, # | ← Rev. 2 →   0 .
•  » » 10 days ago, # ^ |   0 why is this solution wrong for D ? https://codeforces.com/contest/1870/submission/224184528
•  » » » 10 days ago, # ^ |   0 ignore solved.
 » 10 days ago, # |   0 What's 114th input in testcase2 of D?wtf man
 » 10 days ago, # |   0 can any one explain why this brute force got accepted. https://codeforces.com/contest/1870/submission/224151942
 » 10 days ago, # |   0 wrong answer 807th numbers differ — expected: '1', found: '0' , in D ????help! here's my pycode
 » 10 days ago, # |   0 can someone tell error in my submission for problem c https://codeforces.com/contest/1870/submission/224161992
 » 10 days ago, # |   0 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."
•  » » 2 hours ago, # ^ |   0 Performing more OR with a number turns more bit ON(1), which will increase the number. And we have to perform OR to all a[i], so after performing the operations all a[i] will become same(lets say it is x). Now, we know that if there are even no. of x's, the xor will be 0. Thus if the array length of a is odd, the xor will be x(which will give maximum possible value) otherwise it will be 0(which will give minimum possible value).
 » 9 days ago, # |   0 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.
 » 9 days ago, # | ← Rev. 2 →   0 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: 224529457With sqrt decomp: 224527332
 » 5 days ago, # |   0 where is the code
 » 36 hours ago, # |   0 I have implemented Problem D using stack. Code#include using namespace std; void solution() { int n; cin >> n; map 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> 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 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; }