### AquaMoon's blog

By AquaMoon, 4 weeks ago, Thank you for participation and we hope you enjoy this round ヽ(^ o ^)/.

During the contest, there was a small issue in problem D. For those affected, we have skipped your duplicate submissions (if your duplicate submissions were not skipped, please let us know). We apologize again for any inconvenience caused.

In addition, we are honored to invite you to our unofficial round tomorrow (*╹▽╹*) Invitation to TheForces Round #22 (Interesting-Forces)

Idea : wuhudsm

Tutorial
solution

### 1864B-Swap and Reverse

Idea : Parisa_Amiri, chromate00

Tutorial
solution
bonus

Idea : wuhudsm

Tutorial
solution

Idea : AquaMoon

Tutorial
solution

Idea : wuhudsm

Tutorial
solution

### 1864F-Exotic Queries

Idea : ODT, AquaMoon

Hint
Tutorial
solution

Idea : AquaMoon

Hint1
Hint2
Hint3
Tutorial
solution

### 1864H-Asterism Stream

Idea : bogocubic1 Solution: Psychotic_D, amenotiomoi

Tutorial
solution

### 1864I-Future Dominators

Idea : Psychotic_D, amenotiomoi

Tutorial
solution

Feel free to ask if you have any questions! (*╹▽╹*)  Comments (152)
 » Is there any mathematical solution for A ?For example : I tried to figure out whether the gap=y-x-1 is >= required_gap. Where required_gap = ((n-2)*(n-1))/2 ( n-2 because nth and 1st element are already set ) I tried this way but failed pretest 2.
•  » » I had a mathematical solution close to this, I had required_gap = y-x and n(n-1)/2 <= required_gap. You might have been slightly off with your implementation, but I think the logic works.
•  » » check my A
•  » » start from the end and set last element of ans to b.then iterating backwards set v[i]=v[i+1]-gap and increment gap at each step .if it is possible that first element could be greater than equal to a then set first element as a
•  » » the solution does not exists if y-n(n-1)//2
•  » » Why do people downvote even for a fair question?
•  » » Yes, I solved it somewhat mathematically. You can check my solution here https://codeforces.com/contest/1864/submission/220530206
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   Edit: got it. Sorry, but how did you come up with this condition: if(((n-1)*(n))/2 > y-x){ cout<<-1<
•  » » skill issue
•  » » » lol you have less rating than him
•  » » » » lol your dad is 11 feet shorter than me
•  » » » » » unrelated
•  » » » » » » lol who cares
•  » » » thats rude
 » Todays questions was very tricky. Thanks for tutorial
 » I have no idea what the editorial is talking about for H. I thought it was a "berlekamp massey go brrrr" problem.
•  » » Can you elaborate on your solution?
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   Short version:By linearity of expected value, we can sum up the probability of reaching each state with value < N and that's the answerdp[i][j] = probability of reaching a state that sum operations summed up to at most j and there were exactly i operations of multiply by 2. In other words, exactly i multiply by 2 operations and the number is <= 2^i + j.dp[i][j] = (dp[i][j-2^i] + dp[i-1][j]) / 2The answer is sum dp[i][N-2^i] for every i.Define F_i[n] = dp[i][N % (2^i) + n * 2^i]. F_0 is a recurrence (F_0[n] = F_0[n-1] / 2 + 1).F_i[n] = (F_i[n-1] + dp[i-1][N % (2^i) + n * 2^i]) / 2 = (F_i[n-1] + F_(i-1)[a_i + 2 * n]) / 2 for some a_i that is 1 or 0, because N % 2^i is either N % 2^(i-1) or N % 2^(i-1) + 2^(i-1).Hope that the following works:R'[n] = R[a + b * n] for constant a, b. If R is a recurrence of degree D, R' is also a recurrence of degree D.R'[n] = R'[n-1] + R[n]. If R is a recurrence of degree D, R' is a recurrence of degree D+1.it shouldn't be hard to prove that. I think I'm able to prove it using generating functions.then the solution is: compute the first 2*i values of F_i using the first 4*i values of F_(i-1) then interpolate the recurrence using berlekamp massey.
 » Video tutorial for problems A&B&C explained: https://youtu.be/y5QoCUF7hpQ IN ENGLISH Thought would be useful
 » fast editorial. very thank you.
 » Another way to understand problem C :If we are faced with number $2n$, take a sequence of operations that takes $n$ to $1$, multiply every factor by $2$ so that you get a sequence that takes $2n$ to $2$, then decrease by $1$. If we have number $2n + 1$, just decrease by $1$.We can see that no divisor will appear more than twice because of the multiplications by $2$ that make them bigger as it goes.It in fact creates the same sequence as the one in the editorial, but that's how I found it anyway
•  » » Sir I had applied the same but there is a wrong answer..
•  » » » Here's my submission if you want to compare :https://codeforces.com/contest/1864/submission/220544686
 » In problem B, is there a proof that after some series of these 2 transformations any two adjacent elements will be swapped?
•  » » Notice that every element with the same indices modulo $2$ are already "congruent" (i.e. can be swapped over freely). Now, lets say the original string was $abcdefghij$. If we apply the same operations with the editorial, the string becomes $fedcbaghij$, and then $fgabcdehij$. See how $f$ originally had an even index, but now an odd index. Now after we swap things over, we can make $abcdegfhij$, only leaving this pair of $f$ and $g$ swapped. We can generalize this to swap any two adjacent indices. The rest of the proof is left for the reader.
 » Really cool round, enjoyed every problem C-F! Thank you very much authors!
 » Why TLE for problem D? Submission
•  » » It gets AC in 64-bit C++, or if you add the fast-IO line which is unfortunate :/. See 220609340, you should keep that line in pretty much all submissions. (ios_base::sync_with_stdio(false); cin.tie(NULL);)
•  » » » thanks
 » Anyone solving problem D with $O(n^2logn)$ segtree solution? Got TLE but it should pass n = 3000... Perhaps my segtree template sucks.
•  » » nice pfp
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   Bro i got tle during contest . I realises that i can drop the log factor in my code now. Now i get accepted. MY approach is playing with diagonals. x-i > abs(y-j) let do what if we have (x,y) as point and we see points that can update his value solving this inequality in reverse order x+y < i+j x-y > i-j As we see these are some diagonals Interesting fact: if we get the sum of elements on which we apply opertion before (by some how) we can check if its value is 1 or 0. if 1 we apply here Curr = (x,y) : to get the sum, I see that Total = sum [ val(i+j) >= (x+y) ] - sum [ val(i-j+n-1) < (x-y+n-1)] Its like range update with point query n^2 logn (TLE) we know that the thing that The Total above want doesn't depend upon current row we can use difference array type things and get the answer n^2 Accepted :) 
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   You can check my sumbission 220585884 It passed all the tests however very close to TLE. At first, I thought it should work without any problems, but now I understand I'm lucky it didn't fail
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   Removing the lazy part of this template is enough to make it work 220620036 (this works because you are only adding to ranges of length 1, so no actual lazy propagation takes place). It is also storing / updating node lengths everywhere, which is also not needed, and removing it would probably speed it up even further.
 » It's was a great round! Thanks for editorial. Problem C was pretty nice
 » 4 weeks ago, # | ← Rev. 2 →   I got TLE on test 49 in F(220571360), I can pass in less than 1000ms by using fread(220608103). But test 48 need to read more things than test 49. What's the reason?
•  » » So do I. Should I stop using cin/cout from now on?
•  » » I got the same TLE due to using std::sort. It might be the first time I'm seeing a NlogN intended solution not allowing std::sort.
•  » » » I don't think your TLE is due to std::sort. Your code passes with a small change (seems to be the same thing as here).
•  » » » » using GNU C++14 can pass in 1560ms(220632696), using GNU C++20 (64) got TLE in 4 seconds(220632734)?
•  » » » » » bruh sounds so weird
•  » » » » » When im upsolving problems i think that cpp20 is much faster that cpp14? See my submissions on 1265E ^^
•  » » Hay, I also met the same issue. And I also tested different IO methods and different implementations of segment tree. The result is on this blog. I don't know the reason, but you could have a look if you are interested.
 » 4 weeks ago, # | ← Rev. 2 →   Can someone share their O(sqrt(x)) solution for problem C? I had no clue that bit manipulation was to be used here.
•  » » I think I was able to get a very readable solution: https://codeforces.com/contest/1864/submission/220570492
•  » » https://codeforces.com/contest/1864/submission/220567377my idea seems stupid ,but it's right.
•  » » » I've rewritten your solution in a more straightforward way: https://codeforces.com/contest/1864/submission/220633771though, anyone has any ideas/intuitions why it works?
•  » » » » Thanks. During the contest, I was trying to get the largest factor and not the largest prime factor which led to repetition. If someone can explain the intuition as well then it would be great.
•  » » $O(T \sqrt A)$
•  » » Here's my code for C.Hope it helps 220573669
 » The statements in the problems are short and informative to easily understand, and I like problem C the most.Looking forward to seeing you guys as the problem setters again more and more!Thank you very much everyone!
 » Why does this submission for B fails,i was doin, exactly same as of tutorial,https://codeforces.com/contest/1864/submission/220591195
•  » » if(n & 1) u print new linebut u don't print new line in other case, where next query solution merges with that query
•  » » » oh f!
•  » » If $k$ is odd and $n$ is even, you don't print a newline character at the end: Input: 2 2 1 aa 2 1 aa Correct Output: aa aa Your Output: aaaa 
 » Does anything change in problem B with n=k? I couldn't think of a difference
•  » » Yes, it changes a bitFor odd $k$ nothing indeed changes: one can sort even and odd parts separately and nothing more can be done.For even $k$ the method, provided in the editorial, fails. There don't exist two segments of kind $[i; i + k - 1]$ and $[i + 1; i + k]$. Now it's not always possible to change parity of two characters (to move one from odd to even position, and another in the opposite direction). The only possible option is to do it in bulk, i. e. change parities of many characters at once. That could fail to lead to totally sorted string.One can consider a string like $\texttt{cdba}$ and $k = 4$. It is possible to change it to $\texttt{cabd}$, $\texttt{bdca}$, or $\texttt{bacd}$ using only swaps. Now you see that $\texttt{abcd}$ is unreachable (and so is $\texttt{dcba}$), though $k$ is even.
•  » » » Thanks, you're right. I should've tried to observe with a small example. SoThe odd and even positions could be swapped altogether in that case, but not completely mixed. Interesting!
 » 4 weeks ago, # | ← Rev. 2 →   Maybe my solution for D using bitsets would be easier to understand for some people Codebitset<3000> inv, inva, invb; int n, ans = 0; cin >> n; for(int i = 0; i < n; ++i) { inva <<= 1; invb >>= 1; inv ^= inva; inv ^= invb; for(int j = 0; j < n; ++j) { char c; cin >> c; if(inv[j] ^ (c == '1')) { inv[j] ^= 1; inva[j] ^= 1; invb[j] ^= 1; ++ans; } } } cout << ans << endl; 
 » I'm not really getting the solution to D. I don't understand why prefix sums are mentioned and how they are used. The code did not clarify anything, it just confused me more. It would be very helpful if someone could give a more detailed explanation.
•  » »
•  » » » Thank you very much, now it's clearer.
 » A more understandable solution to H, and didn't require too much knowledge or math.First, we can consider subtracting $1$ from $n$ or dividing $n$ by $2$, and compute the expected step to make $n$ be $0$. We can build a recurrence $f(n) = 1 + \frac{1}{2} (f(n - 1) + f(\lfloor n/ 2 \rfloor))$. And the answer to the original problem is $f(n - 1)$.It seems it's hard to compute $f(n)$ by some matrix or the linear recurrence trick. But here is the magic, you can maintain $b_{n} = [f(n), f(\lfloor n/2 \rfloor), f(\lfloor n/4 \rfloor), \dots, 1]^T$. So we can build the transition from $b_{n-1}$ to $b_n$. And it's not hard to see, that the transition matrix only depends on the number of trailing zeros of $n$ in its binary representation. The answer is $\prod_{i=1}^n M_{ctz(i)}$.We can precompute $\prod_{i=1}^{2^k} M_{ctz(i)}$ in $O(\log^4 n)$, and solve each query in $O(\log^3 n)$.Submission: 220569504
•  » » Wow, very cool! Thank you for sharing.
•  » » 4 weeks ago, # ^ | ← Rev. 5 →   I think my solution is very similar to yours, though I do not 100% understand your sol. My solution represents the dp like this: $f(x + 1) = 1 + \frac{1}{2}(f(x) + f(\left \lceil{\frac{x}{2}}\right \rceil)$ (exactly the same as yours essentially) with a restriction of I will assume that $x \equiv 0 \;(\bmod\; 2)$. Then I calculate a new function $f(x + 2) = 1 + \frac{1}{2}(f(x + 1) + f(\left \lceil{\frac{x + 1}{2}}\right \rceil).$ Then I will assume that $x \equiv 0 \;(\bmod\; 4)$ and rewrite the formula like this: $f(x + 2) = 1 + \frac{1}{2}(f(x + 1) + f(\left \lceil{\frac{x}{2}}\right \rceil + 1).$ Note that now both of the recurrences can be substituted with the first function, and when all simplified it leads to $f(x + 2) = 2 + \frac{1}{4}(f(\left \lceil{\frac{x}{4}}\right \rceil) + 2f(\left \lceil{\frac{x}{2}}\right \rceil) + f(x))$. Then again I will assume that $x \equiv 0 \;(\bmod\; 8)$ and re-expand the formula and repeat. This leads to log n different functions that can jump from $f(x) \rightarrow f(x + 2^{k})$ when $x \equiv 0 \;(\bmod\; 2^{k})$ (given that you know $f(\left \lceil{\frac{x}{2^{i}}}\right \rceil)$ for all i <= k).Submission: 220629661It really took me a long time to wrap my head around the pattern between expansion and how to code it up but I think it is quite beautiful how apply somewhat arbitrary modulo restrictions onto the equation allows for kind of a "binary exponentiation" trick.
•  » » why your f(n) = 1 + (1/2) * (f(n — 1) + f(n / 2)) ? why do not you consider the case which n is a add number ?
•  » » » He shifted all the numbers down by one, so the floor division actually becomes ceil diving.
•  » » The method of undetermined coefficients (待定系数法) also works: https://codeforces.com/blog/entry/119850
 » Problem C is Preety Good. I didn't get any approach during contest I solved A, not able to B , C then i got D :) Though rank is very bad but solved D :)
 » 4 weeks ago, # | ← Rev. 2 →   I have another solution to E SolutionInstead of creating a bit trie I create an array a[n][logA], where a[i] = v[i] for each i and a[i][j] = a[i][j — 1] >> 1 for each j 0 < j < logA, so lets look at number of such elements a[k][j] that a[i][j]=a[k][j] and a[i][j-1] != a[k][j — 1]: these elements have the same highest elements (and same number of '1' on the same places). So we can calculate the answer easier in O(nlogA) time and memory
 » How do we sort ACBDE TO ABCDE with k as 4?
•  » » ACBDE -> AEDBC reverse CBDE to EDBC AEDBC -> AECBD swap C and D AECBD -> BCEAD reverse AECB to BCEA BCEAD -> DCBAE swap D and E, and swap B and D DCBAE -> ABCDE reverse DCBA to ABCD
 » 4 weeks ago, # | ← Rev. 13 →   An alternative solution of 1864E - Guess GameFrom the very beginning let us sort our sequence $s$.For two integers $a$ and $b$ denote by $f(a, b)$ the number of $1$-s in the largest common prefix of $a$ and $b$. Then the answer is $ans = \sum_{i, j} \bigl(f(s_i, s_j) + [s_i < s_j]\bigr).$Denote $a_i = f(s_i, s_{i+1}).$The key step is to note that since $s$ is sorted, then for $i < j$ we have $f(s_i, s_j) = \min_{i\leq k  » I solved D using the data structures. Let's consider that we have already found all the cells that will have the value$1$and will have row index smaller than$x$. Let's denote the number of that cells as$currentCount$. Now, we want to find all the cells equal to$1$in the row$x$.Let's consider the cell$(x, y)$, and understand which cells can force the cell$(x, y)$to flip its value. The value in the cell$(x, y)$will be equal to the initial value in the cell$(x, y)$plus the number of cells$(i, j)$(mod 2) satisfying the following condition:$i < xx - i \geq |y - j|$For the second condition, we can note that the equation is met either for$x - i \geq y - j$or for$x - i \geq j - y$, since we know that$x - i > 0$and$min(y - j, j - y) \leq 0$. So we need to find the number of cells, for which both equations are met:$x - i \geq y - j$, we can transform into this$x - y \geq i - jx - i \geq j - y$, we can transform into this$x + y \geq i + j$So we can keep two Fenwick trees, and for each cell in the first Fenwick tree add$1$in position$i - j$and for the second one in position$i + j$.Now, the new value for the position$(x, y)$will be equal to the following:$ initialValue[x][y] + get1(x - y) + get2(x + y) - currentCount (mod 2) $where$get1(x)$is equal to the sum of values in the first Fenwick tree, for which the indices are smaller than or equal to$x$.$get2(x)$is the same for the second Fenwick tree. •  » » Yaa I do the same. You can still improve it like instead of 4 values in the expression use diagonals to get the value.I do it this way. By seeing as diagonal we remain with just 2 values •  » » Why should we subtract currentCount? •  » » » Because for each cell we may count it twice, and we guarantee know that we count each cell at least once. Our goal is to calculate only the cells for which both equations are met, because of it we subtract$currentCount$. •  » » » » 4 weeks ago, # ^ | ← Rev. 2 → Shouldn't currentCount count the answer so far above the current row, which may contain flipped cells not affecting cell (x, y)? Why remove cells not even flipping current one? •  » » » » » 4 weeks ago, # ^ | ← Rev. 3 → Because for each cell we know that at least one of these equations is true:$x - i \geq y - jx - i \geq j - yx - i$is always greater than 0, while the minimum of$y - j$and$j - y$is always smaller than or equal to 0. •  » » » » » » Oh, got it now, that's smart, thanks for the explanation  » Tutorial of F: Consider all adjacent equal pairs$(l, r)$, and$m$is the minimum element between$(l, r)$.$m$should be the maximum element between$(l, r)$satisfying$m < a_l$•  » » That confused me as well •  » » Sorry for the mistake! Fixed. Thank you (〃'▽'〃)o •  » » » It seems like you didn't fully fix it. Now the tutorial says:... and$m$is the maximum element between$(l, r)$You changed minimum to maximum, but didn't add the constraint$m < a_l$•  » » » » Oh thank you! Fixed (〃•ω‹〃)  » 4 weeks ago, # | ← Rev. 2 → An O(nlog(max(ai)) solution for E, without tries.  » shouldn't 30*N*log(N) pass the time limit? can someone check the solutionfor prefixes i am converting them to number and storing in map •  » » I didn't read the code too carefully but you can try to check whether mp[x] exists before doing operations like += mp[x]. This prevents the map from creating extra elements. I also had TLE with map and this helped. •  » » » Yep that worked for me too.  » The word "graph" appears only once in this tutorial, for 9 problem  » How can I "Reduce$x$to$2L$." in problem C? •  » » for some x, say 19 whose binary representation is 10011 = 2^4 + 2^1 + 2^0. You can see that 2^1 divide 2^4, 2^0 divide 2^4, 2^0 divide 2^4. So the answer is you just minus the rightmost bit to x, in this case, is 2^0 and 2^1 until x has only one bit in binary representation.P/S: Sorry for my bad English. Hope you understand this explanation •  » » » Thank you.  » In F, which can be easily calculated with a segment tree and sweeping lines. Can someone explain how sweeping lines are used here? A link would also be appreciated. •  » » I think my solution implements that 220623962. sweepline used for dectime. •  » » The first part of the solution is finding$m$(the maximum value in$(l, r)$that is less than$a_l = a_r$) for all adjacent equal pairs$(a_l, a_r)$. I did this using a segment tree and stored the pairs$(m, a_l)$. Now, you need to count the number of pairs that satisfy$m < L \leq a_l = a_r \leq R$for each query.Sort the queries by increasing the left endpoint and also sort the pairs found earlier. Now, you can do sweepline and add the values of$a_l = a_r$to an ordered set once$m$is less than the current query's$l$. The answer for each query is the position of the upper bound of$r$in the set.220616946 sorry if the code is a bit messy. •  » » » I think I see it, thank you.  » 4 weeks ago, # | ← Rev. 3 → Another implement for D whose time complexity is O(n^2) but only O(n) space 220627524. The logic in this code may cause you confused, in this case, ask me(and vote) •  » » O(n) space? It takes O(n^2) memory just to store the matrix lol. •  » » » Sorry for my mistake. I had to fix it and now this code uses only 156KB of memory 220627524 •  » » Why we need to store the minus and the add in different arrays. Should that not be possible using a single prefix sum array like what I have done in this solution. It is giving WA but I am not able to understand why it is wrong. Can you please help me? •  » » » I don't know how to explain this clearly. But the key is the minus and the add extend in a different direction  » Problem F is somewhat similar to this: http://www.usaco.org/index.php?page=viewproblem2&cpid=1116 (It is the same problem but [l, r] matters on position rather than value. The basic idea (incrementing R and maintaining L in a fenwick tree / segment tree) persists in this problem too which I find to be pretty cool (The only addition is that you need to use a min segment tree to determine the ranges to add).  » problem i should not exist  » Feedback on the problems:A and B: Fine easy problems. Not especially interesting, but not too bad (and quick enough that I was able to move on to the more exciting problems without too much delay).C: Good easy problem. In some sense, the observation to use powers of two wasn't especially motivated, but for problems like this I often find it helpful to try to reduce the problem to some special case I know how to handle easily, so in that sense reducing$n$to the next lower power of two felt like a reasonable thing to do.D: Not terrible, but not my favorite problem ever. The idea to go top to bottom and flip cells that needed to be flipped along the way was fairly intuitive, and so it felt like most of the task was just working out details.E: Good problem. I always enjoy this kind of logic puzzle, and I found both solving the problem and implementing the solution to be fairly satisfying.F: Nice DS problem. The idea is both well-motivated and elegant, and all in all the implementation isn't too bad.G: I enjoyed this problem very much, with the reservation that I think the statement was very contrived. It felt like the conditions in the problem basically came from having the solution in mind and trying to stretch the setting of the problem to fit it. Once I parsed the task, though, I really enjoyed the process of working on it (even though I wasted time in contest implementing a completely incorrect idea, then failed to debug my correct solution before the end of the round :p). It was very satisfying to gradually understand the setup of the problem better until I was finally able to make the observations necessary to solve the problem.H: Decent problem. The setup is nice, but I wasn't a huge fan of the main observation (realizing that the relevant sequence can be expressed as sums of geometric sequences) because it didn't feel like I was unlocking some deep structure of the problem--instead, it felt as though I was doing the bare minimum to get the problem to fit into some high-powered technology (e.g. Berlekamp-Massey as other commenters have noticed; I was able to use Gauss-Jordan elimination to achieve essentially equivalent effect).I haven't paid close attention to the preparation (e.g. I didn't check to see how many FSTs there were), and there was obviously an issue with the original test data in D, but overall I enjoyed the problems (especially EFG) and the round as a whole (despite performing below my standards and taking a substantial rating loss). Thanks to the authors! •  » » Thanks for your precious feedback. •  » » F constraints are too large for seemingly no reason imo. Too many people had trouble because of obscure differences between the 64bit compiler and 32bit one. I've still not seen a decent explanation about what's happening. •  » » » •  » » » » What about it? That blog doesn't contain sufficient explanation about what's happening, just some guesses of what might cause it. •  » » » » » Actually, I'm not the author of problem F, so maybe AquaMoon can help you ... •  » » I thought C was fairly motivated if you reach the solution recursively such as a commenter did above: https://codeforces.com/blog/entry/119772?#comment-1062597  » If only the constraint for k in C was 64, I would've done it faster. Anyways, nice problems!  » Can someone explain me D?How are we achieving the required conditions? And it is my request to authors to please be consistent. It is easier to understand the code when it is based on tutorial. •  » » Let me explain a bit informally.We greedily look from above, inverting every cell with$1$by using the operation right on that cell. This is because, if we do not use the operation on this cell, we cannot affect this cell at all afterwards, therefore we must use the operation on this cell.Now for how we will simulate the operations. Try rotating the matrix by$45$degrees, and now the range of the operations will be a rectangle (though clipped out due to the borders), which is a very good situation to use a 2D prefix sum on. This should help you to understand the rest of the solution. •  » » » Still not able to understand the simulation. I am finding it difficult to imagine it. Can you explain me what the editorial code is trying to do? I will try understanding it using dry testing. •  » » » » you can look at my code which does the same thing but in a less contrived way https://codeforces.com/blog/entry/119772?#comment-1062644  » Great contest!~ qwq i love the problem D and i think the expectation problem E is also great. by the way congratulate to le0n for getting to grandmaster~  » I have a different solution for D. Suppose I am at (x,y) and I want to check the parity of the number of cells before it which have affected this cell. Observe that, if a cell "covers" (x-1, y) (a cell covers a cell (a,b) if the diagonal lines coming out of it enclose (a,b)), then it also covers (x,y). Now, what are those points which cover only (x,y) but do not cover (x-1,y)? They are precisely those whose right diagonal (line with slope -1) passes through (x-1,y-1) and (x,y), and those whose left diagonal (line with slope 1) passes through (x-1, y+1) and (x,y). So, we need to store and do the following updates: For the previous row, store how many times (x-1, y) was operated upon, add its parity, and also add the parity of the number of operated cells which are diagonal to (x,y), which can be stored in a map using the fact that the sum/difference of the indices on the diagonals remains constant. https://codeforces.com/contest/1864/submission/220595343  » I loved problem D proposed by AquaMoon and obviously the problem H proposed by you buddy amenotiomoi, and the Editorial justifies it <3 •  » » I am so delighted that you love my problem！~o(〃'▽'〃)o •  » » » Its obvious for me to like ヽ(´▽)ノ <3  » 4 weeks ago, # | ← Rev. 3 → can anyone tell me this why https://codeforces.com/contest/1864/submission/220617780 solution of b is giving time complexity? •  » » Use fast IO, add this ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0); in your main, then you'll pass, read more about it here : https://www.geeksforgeeks.org/fast-io-for-competitive-programming/  » I was having fun solving those problems. Enjoyable round.  » I thought about B's bonus and came out with a solution:Solve the problem with$k=3$. Then flip the string. Solve the problem again. Then find the minimum among the two.If$n\le 2$, then you can just sort the string.  » how tf can people have negative rating when in this contest i didn't solve a single problem but got +112 and got to +875 ? •  » » https://codeforces.com/blog/entry/77890?locale=enSo you actually got 112-250 = -138.  » By mistake, I solved F for index range queries, instead of value range. Does anyone have link to that kind of a problem ? •  » » Problem linked here: https://codeforces.com/blog/entry/119772?#comment-1062685. •  » » » Thanks man!  » 4 weeks ago, # | ← Rev. 3 → i know how D works but i dont understand the prefix sum part, i have been tried for many hours and i couldn't figure it out, please give me some help :( •  » » A 1 in the current line can result in 111 in the next line, and 11111 in the line after next. Since these number of 1`s are O(n), we can try to reduce it to O(1) by using prefix sums. •  » » » i understood the 11111 part, but struggling with O(1) prefix sum update :(, ill try my best to figure it out, thanks for paying attention  » Did anyone solve problem C with dp?  » F Why the maximum element between (l,r) and max  » please can some one explain why in the editorial code- in the case of i>=2 for j==0 sum[i][j] ^= sum[i-2][j] is written shouldn't it be sum[i][j] ^= sum[i-1][j] and similarly for j==n-1..  » in problem B what is the proof that with even K it is always possible to sort the elements in order? can any one help me with that... •  » » Swap$(s_{i}, s_{i+2})$means we can sort all the chars in odd and even positions. If$k$is even we can change the parity of any char we want (i.e. from odd to even and from even to odd) thus we can sort all string. •  » » » but why does size of k does not matter suppose if n=6 and k=4 then how can we sort them •  » » » » I was trying explaining it by myself, but editorial is better. In the first pic the red is what have changed, blue is what remaining the same. So we can just swap the modulo 2 of two adj. indexes we want, and with swap$(s_{i}, s_{i+2})$we can place any chars we want. For you i made the same with$n = 6$and$k = 4$. •  » » » » » understood. thank you for your efforts •  » » » » » I still don't get that, I tried to apply this to dfcbea using k=4 but didn't get abcdef. How can I? •  » » » » » »  » I understand how to prepare and utilize 2D prefix sums for range queries, as well as how to prepare and utilize 1D difference arrays for range updates. However, Problem D here seems to require 2D difference arrays, which I haven't quite figured out yet, and the editorial seems to be rather vague. Can anyone please provide any resources to learn about 2D difference arrays and/or elaborate on the details for it? •  » » Well, 2D prefix sums and 2D difference arrays are essentially the exact same. Let's say you add 1 to p[x][y]. When computing the prefix sum of p, you would have added 1 to all a[i][j] where i >= x and j >= y. Using this in a similar method to how 2d prefix sums allows you to do rectangular updates.Example:p++;p--;p++;p--;if you compute the prefix sum of p, you will end up with1 1 01 1 00 0 0(top-left is (0, 0))  » Bonus for F: try to solve it as if it were an interactive problem, i.e. you must answer a query in order to read the next one. SolutionJust like in the editorial, we iterate through all$i$from$1$to$n$and for all adjacent pairs$(l, r)$where$a_l=a_r=i$, we shall find the maximum element$m$between$(l, r)$that satisfies$m
 » Can someone suggest some more problems like E. I found the use of Trie to calculate the total number of turns very unintuitive.
 » 4 weeks ago, # | ← Rev. 3 →   Join my telegram channel to discuss questions of contest https://web.telegram.org/a/#-1957338640_3
 » I have another solution for problem E without tries:Consider p/q — expected value. Let's sort an array. Taking s[i] as one of the element in the game we can calculate value added to p. We know that in sorted array going from the beginning the end-game bit (XOR == 1) is moving right. So, let's brute force a position of end-game bit from the most significant one. Consider _b as bit value of s[i]. We can easily precompute how many steps we have to do before reaching this bit or even do it greedily because common prefix of two numbers is getting bigger. As we don't want to have collisions and our left bound is going right we want to know how many numbers in [l,i) have (_b^1) value in the bit. Let's make prefix sums! pref[val][bit][i] (val — {0, 1}, bit — {0...31}) And after calculating update left bound using binary search (just make pos[val][bit] and push all required numbers positions). Time complexity — O(32*NlogN)Submission 221065798
 » Can anyone help me in getting error in this submission for Problem E, it is failing on testcase 6.I solved it using tries..
 » 3 weeks ago, # | ← Rev. 2 →   Hi, I submitted my solution to D in Java 8, it's giving TLE on testcase 8. But, when I submit the code in C++ using the same logic which I used in my Java solution, it's giving AC. Any insights on how can I pass it in Java ?Java SolutionC++ solution
 » For D, Similar problem in 1D array Restaurant Customers