Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

AquaMoon's blog

By AquaMoon, 3 months 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! (*╹▽╹*)

• +201

 » 3 months ago, # |   +1 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.
•  » » 3 months ago, # ^ |   0 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.
•  » » 3 months ago, # ^ |   0 check my A
•  » » 3 months ago, # ^ |   0 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
•  » » 3 months ago, # ^ |   0 the solution does not exists if y-n(n-1)//2
•  » » 3 months ago, # ^ |   +19 Why do people downvote even for a fair question?
•  » » 3 months ago, # ^ |   0 Yes, I solved it somewhat mathematically. You can check my solution here https://codeforces.com/contest/1864/submission/220530206
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 Edit: got it. Sorry, but how did you come up with this condition: if(((n-1)*(n))/2 > y-x){ cout<<-1<
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Try to get better
•  » » » 3 months ago, # ^ |   +8 lol you have less rating than him
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   -14 OK
•  » » » » » 3 months ago, # ^ |   +8 unrelated
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 I'm so sorry
•  » » » 3 months ago, # ^ |   +8 thats rude
 » 3 months ago, # |   0 Todays questions was very tricky. Thanks for tutorial
 » 3 months ago, # |   +27 I have no idea what the editorial is talking about for H. I thought it was a "berlekamp massey go brrrr" problem.
•  » » 3 months ago, # ^ |   0 Can you elaborate on your solution?
•  » » » 3 months ago, # ^ | ← Rev. 3 →   +43 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.
 » 3 months ago, # |   0 Video tutorial for problems A&B&C explained: https://youtu.be/y5QoCUF7hpQ IN ENGLISH Thought would be useful
 » 3 months ago, # |   0 fast editorial. very thank you.
 » 3 months ago, # |   +53 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
•  » » 3 months ago, # ^ |   0 Sir I had applied the same but there is a wrong answer..
•  » » » 3 months ago, # ^ |   0 Here's my submission if you want to compare :https://codeforces.com/contest/1864/submission/220544686
•  » » 4 weeks ago, # ^ |   0 Problem C fails for the n=15 according to editorial the answer is 7 — 15 14 12 8 4 2 1but the min answer is 6 ie 6 — 15 10 5 4 2 1Then what about this??
•  » » » 4 weeks ago, # ^ |   0 you're right but the problem did not require us to minimise the number of operations.
 » 3 months ago, # |   0 In problem B, is there a proof that after some series of these 2 transformations any two adjacent elements will be swapped?
•  » » 3 months ago, # ^ |   0 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.
 » 3 months ago, # |   +6 Really cool round, enjoyed every problem C-F! Thank you very much authors!
 » 3 months ago, # |   0 Why TLE for problem D? Submission
•  » » 3 months ago, # ^ |   +5 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);)
•  » » » 3 months ago, # ^ |   0 thanks
 » 3 months ago, # |   0 Anyone solving problem D with $O(n^2logn)$ segtree solution? Got TLE but it should pass n = 3000... Perhaps my segtree template sucks.
•  » » 3 months ago, # ^ |   0 nice pfp
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 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 :) 
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 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
•  » » 3 months ago, # ^ | ← Rev. 2 →   +6 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.
 » 3 months ago, # |   +9 It's was a great round! Thanks for editorial. Problem C was pretty nice
 » 3 months ago, # | ← Rev. 2 →   +43 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?
•  » » 3 months ago, # ^ |   +33 So do I. Should I stop using cin/cout from now on?
•  » » 3 months ago, # ^ |   0 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.
•  » » » 3 months ago, # ^ |   +67 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).
•  » » » » 3 months ago, # ^ |   +38 using GNU C++14 can pass in 1560ms(220632696), using GNU C++20 (64) got TLE in 4 seconds(220632734)?
•  » » » » » 3 months ago, # ^ |   0 bruh sounds so weird
•  » » » » » 3 months ago, # ^ |   +10 When im upsolving problems i think that cpp20 is much faster that cpp14? See my submissions on 1265E ^^
•  » » 3 months ago, # ^ |   +10 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.
 » 3 months ago, # | ← Rev. 2 →   +8 Can someone share their O(sqrt(x)) solution for problem C? I had no clue that bit manipulation was to be used here.
•  » » 3 months ago, # ^ |   0 I think I was able to get a very readable solution: https://codeforces.com/contest/1864/submission/220570492
•  » » 3 months ago, # ^ |   0 https://codeforces.com/contest/1864/submission/220567377my idea seems stupid ,but it's right.
•  » » » 3 months ago, # ^ |   -8 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?
•  » » » » 3 months ago, # ^ |   0 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.
•  » » 3 months ago, # ^ |   0 $O(T \sqrt A)$
•  » » 3 months ago, # ^ |   0 Here's my code for C.Hope it helps 220573669
 » 3 months ago, # |   0 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!
 » 3 months ago, # |   0 Why does this submission for B fails,i was doin, exactly same as of tutorial,https://codeforces.com/contest/1864/submission/220591195
•  » » 3 months ago, # ^ |   0 if(n & 1) u print new linebut u don't print new line in other case, where next query solution merges with that query
•  » » » 3 months ago, # ^ |   0 oh f!
•  » » 3 months ago, # ^ |   0 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 
 » 3 months ago, # |   -18 Does anything change in problem B with n=k? I couldn't think of a difference
•  » » 3 months ago, # ^ |   +9 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.
•  » » » 3 months ago, # ^ |   0 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!
 » 3 months ago, # | ← Rev. 2 →   +1 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; 
 » 3 months ago, # |   +1 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.
•  » » 3 months ago, # ^ |   0
•  » » » 3 months ago, # ^ |   0 Thank you very much, now it's clearer.
 » 3 months ago, # |   +200 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
•  » » 3 months ago, # ^ |   +13 Wow, very cool! Thank you for sharing.
•  » » 3 months ago, # ^ | ← Rev. 5 →   +18 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.
•  » » 3 months ago, # ^ |   0 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 ?
•  » » » 3 months ago, # ^ |   +18 He shifted all the numbers down by one, so the floor division actually becomes ceil diving.
•  » » 3 months ago, # ^ |   0 The method of undetermined coefficients (待定系数法) also works: https://codeforces.com/blog/entry/119850
 » 3 months ago, # |   0 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 :)
 » 3 months ago, # | ← Rev. 2 →   +3 I have another solution to E SolutionInstead of creating a bit trie I create an array a[n][logA], where a[i][0] = 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
 » 3 months ago, # |   0 How do we sort ACBDE TO ABCDE with k as 4?
•  » » 3 months ago, # ^ |   0 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
 » 3 months ago, # | ← Rev. 13 →   +6 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  » 3 months ago, # | +14 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. •  » » 3 months ago, # ^ | 0 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 •  » » 3 months ago, # ^ | +3 Why should we subtract currentCount? •  » » » 3 months ago, # ^ | 0 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$. •  » » » » 3 months ago, # ^ | ← Rev. 2 → 0 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? •  » » » » » 3 months ago, # ^ | ← Rev. 3 → +1 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. •  » » » » » » 3 months ago, # ^ | 0 Oh, got it now, that's smart, thanks for the explanation  » 3 months ago, # | +31 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$•  » » 3 months ago, # ^ | 0 That confused me as well •  » » 3 months ago, # ^ | +10 Sorry for the mistake! Fixed. Thank you (〃'▽'〃)o •  » » » 3 months ago, # ^ | +8 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$•  » » » » 3 months ago, # ^ | +10 Oh thank you! Fixed (〃•ω‹〃)  » 3 months ago, # | ← Rev. 2 → +3 An O(nlog(max(ai)) solution for E, without tries.  » 3 months ago, # | 0 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 •  » » 3 months ago, # ^ | 0 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. •  » » » 3 months ago, # ^ | 0 Yep that worked for me too.  » 3 months ago, # | 0 The word "graph" appears only once in this tutorial, for 9 problem  » 3 months ago, # | 0 How can I "Reduce$x$to$2L$." in problem C? •  » » 3 months ago, # ^ | +1 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 •  » » » 3 months ago, # ^ | 0 Thank you.  » 3 months ago, # | +5 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. •  » » 3 months ago, # ^ | 0 I think my solution implements that 220623962. sweepline used for dectime. •  » » 3 months ago, # ^ | +3 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. •  » » » 3 months ago, # ^ | 0 I think I see it, thank you.  » 3 months ago, # | ← Rev. 3 → +5 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) •  » » 3 months ago, # ^ | 0 O(n) space? It takes O(n^2) memory just to store the matrix lol. •  » » » 3 months ago, # ^ | 0 Sorry for my mistake. I had to fix it and now this code uses only 156KB of memory 220627524 •  » » 3 months ago, # ^ | 0 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? •  » » » 3 months ago, # ^ | 0 I don't know how to explain this clearly. But the key is the minus and the add extend in a different direction •  » » 6 weeks ago, # ^ | 0 Hey, can you explain your solution? It really would be helpful. Thanks  » 3 months ago, # | 0 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).  » 3 months ago, # | -44 problem i should not exist  » 3 months ago, # | +60 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! •  » » 3 months ago, # ^ | 0 Thanks for your precious feedback. •  » » 3 months ago, # ^ | +8 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. •  » » » 3 months ago, # ^ | 0 •  » » » » 3 months ago, # ^ | 0 What about it? That blog doesn't contain sufficient explanation about what's happening, just some guesses of what might cause it. •  » » » » » 3 months ago, # ^ | 0 Actually, I'm not the author of problem F, so maybe AquaMoon can help you ... •  » » 3 months ago, # ^ | 0 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  » 3 months ago, # | 0 If only the constraint for k in C was 64, I would've done it faster. Anyways, nice problems!  » 3 months ago, # | 0 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. •  » » 3 months ago, # ^ | +14 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. •  » » » 3 months ago, # ^ | 0 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. •  » » » » 3 months ago, # ^ | 0 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  » 3 months ago, # | 0 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~  » 3 months ago, # | +1 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  » 3 months ago, # | 0 I loved problem D proposed by AquaMoon and obviously the problem H proposed by you buddy amenotiomoi, and the Editorial justifies it <3 •  » » 3 months ago, # ^ | 0 I am so delighted that you love my problem！~o(〃'▽'〃)o •  » » » 3 months ago, # ^ | 0 Its obvious for me to like ヽ(´▽)ノ <3  » 3 months ago, # | ← Rev. 3 → 0 can anyone tell me this why https://codeforces.com/contest/1864/submission/220617780 solution of b is giving time complexity? •  » » 3 months ago, # ^ | 0 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/  » 3 months ago, # | +2 I was having fun solving those problems. Enjoyable round.  » 3 months ago, # | +13 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.  » 3 months ago, # | 0 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 ? •  » » 3 months ago, # ^ | +10 https://codeforces.com/blog/entry/77890?locale=enSo you actually got 112-250 = -138.  » 3 months ago, # | 0 By mistake, I solved F for index range queries, instead of value range. Does anyone have link to that kind of a problem ? •  » » 3 months ago, # ^ | +1 Problem linked here: https://codeforces.com/blog/entry/119772?#comment-1062685. •  » » » 3 months ago, # ^ | 0 Thanks man!  » 3 months ago, # | ← Rev. 3 → 0 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 :( •  » » 3 months ago, # ^ | +1 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. •  » » » 3 months ago, # ^ | 0 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  » 3 months ago, # | 0 Did anyone solve problem C with dp?  » 3 months ago, # | 0 F Why the maximum element between (l,r) and max  » 3 months ago, # | 0 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..  » 3 months ago, # | 0 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... •  » » 3 months ago, # ^ | 0 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. •  » » » 3 months ago, # ^ | 0 but why does size of k does not matter suppose if n=6 and k=4 then how can we sort them •  » » » » 3 months ago, # ^ | 0 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$. •  » » » » » 3 months ago, # ^ | 0 understood. thank you for your efforts •  » » » » » 3 months ago, # ^ | 0 I still don't get that, I tried to apply this to dfcbea using k=4 but didn't get abcdef. How can I? •  » » » » » » 3 months ago, # ^ | 0  » 3 months ago, # | 0 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? •  » » 3 months ago, # ^ | 0 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[0][0]++;p[2][0]--;p[2][2]++;p[0][2]--;if you compute the prefix sum of p, you will end up with1 1 01 1 00 0 0(top-left is (0, 0))  » 3 months ago, # | +13 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
 » 3 months ago, # |   0 Can someone suggest some more problems like E. I found the use of Trie to calculate the total number of turns very unintuitive.
 » 3 months ago, # | ← Rev. 3 →   0 Join my telegram channel to discuss questions of contest https://web.telegram.org/a/#-1957338640_3
 » 3 months ago, # |   0 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
 » 3 months ago, # |   0 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 months ago, # | ← Rev. 2 →   0 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
 » 2 months ago, # |   0 For D, Similar problem in 1D array Restaurant Customers
 » 4 weeks ago, # | ← Rev. 2 →   0 Problem C fails for the n=15 according to editorial the answer is 7 - 15 14 12 8 4 2 1but the min answer is 6 ie 6 — 15 10 5 4 2 1Then what about this??
•  » » 4 weeks ago, # ^ |   0 In this problem you don't need to minimize the number of operations.
»
4 weeks ago, # |
Rev. 4   0
Relatively easier explanation for observation that could lead to the solution for C:

Lets say $x$ is even, and $x = 2^p\cdot 3^q\cdot 5^r \ldots$. Suppose we take $d = 2^p$. Then the updated value $(x-d) = d\cdot(some\;odd\;divisor - 1)$. Which means, that this updated value is guaranteed to have atleast one, (if not more) extra exponents/powers of 2 in its prime factorisation. That enables us to repeat the same operation again and again. Ultimately we will reach a point when the $(some\;odd\;divisor - 1)$ thing will have erase all odd factors from the number and our $x$ is now a pure power of $2$.

From this point on, it is trival to see that we could keep dividing a pure power of $2$ like $2^i$ by $2^{i-1}$, untill we reach $2^1$. This is when we subtact $1$ and get the final answer.

Note, that every divisor used in taking $x \rightarrow 2^i$ is unique since we get a larger "even" divisor everytime due to the $(some\;odd\;divisor-1)$ thing. Similarly in taking $2^i \rightarrow 2^1$, we use any divisor only once. This guarantees that even if repeat a divisor in the $x \rightarrow 2^i$ path and $2^i \rightarrow 2$ path, the constraint of using a divisor only twice atmax is respected.

Now notice we have used $1$ only single time at the last step. Thus, it is available for converting any odd input to even. And then we can easily take the even number down to $1$.