### Tlatoani's blog

By Tlatoani, 3 years ago, We hope you liked the problems! We apologize for the weak pretests for A and B -- that was a major oversight on our part. Hopefully you were still able to enjoy the contest regardless :)

We have to apologize to antontrygubO_o a bit here -- the rejection count mentioned in the editorial for Codeforces Round 655 (Div. 2) actually also included this round, as the problems from that round and problems A through G in this round were created together. We did have one more problem rejected after that round happened, bringing up the total to 73. For reference, here are the overall rejection counts for each problem:

Rejection Counts

Without further ado, here are the tutorials for each of the problems:

Solution (Kotlin) by golions
Solution (Java) by MagentaCobra
Solution (C++) by hugopm

Idea: MagentaCobra and qlf9

Preparation: MagentaCobra

Solution (Kotlin) by Tlatoani
Solution (Java) by MagentaCobra
Solution (C++) by tfg

Idea: MagentaCobra

Preparation: MagentaCobra

Solution (Kotlin) by Tlatoani
Solution (Java) by qlf9
Solution (C++) by tfg

Idea: qlf9

Preparation: qlf9

Solution (Kotlin) by Tlatoani
Solution (Java) by qlf9
Solution (C++) by Ari

Idea: Tlatoani

Preparation: Tlatoani

Solution (Kotlin) by Tlatoani
Solution (Java) by golions
Solution (C++) by hugopm

Idea: Tlatoani

Preparation: Tlatoani and golions

EDIT: The fact that the order of operations doesn't matter turned out to be harder to prove than I thought (thanks to the comments for pointing this out), so I decided to add the following proof:

If you have two sequences of maximal operations, then what we want to show is that they have to consist of the same operations (possibly in different orders). Since they are both maximal, they must either both be empty or both be nonempty. If they are both empty then we are done.

If they are both nonempty: consider the current state of the vector (before applying either sequence of operations). Since the sequences are nonempty, there is at least one operation $\alpha$ that can be immediately applied on the vector.

Here we should make the observation that applying an operation at some index cannot prevent operations at other indexes from being able to be applied (it can only allow other operations to be applied).

Therefore, applying other (different) operations cannot prevent operation $\alpha$ from being able to be applied, so operation $\alpha$ must occur in both sequences. From our observation, we can see that if, in either sequence, operation $\alpha$ does not occur initially, then operation $\alpha$ can be applied initially because by performing it earlier we are not preventing any of the operations in between from being applied.

Thus, the first operation of each sequence is now the same, so we can apply the same argument to the remainder of the sequence (since it must be finite).

Solution (Kotlin) by Tlatoani
Solution (Java) by qlf9
Solution (C++) by Devil

Idea: Tlatoani

Preparation: Tlatoani and qlf9

Solution (Kotlin) by Tlatoani
Solution (Java) by qlf9
Solution (C++) by mohammedehab2002

Idea: Tlatoani

Preparation: Tlatoani

Solution (C++) by zscoder
Solution (Java) by qlf9
Solution (Kotlin) by Tlatoani

Idea: zscoder

Preparation: zscoder

Solution (C++) by KLPP

Idea: KLPP

Preparation: KLPP Tutorial of Codeforces Global Round 10  Comments (207)
| Write comment?
 » Auto comment: topic has been updated by Tlatoani (previous revision, new revision, compare).
 » Thanks for the fast editorial! The contest was awesome!
 » Auto comment: topic has been updated by Tlatoani (previous revision, new revision, compare).
 » What a fast editorial!
 » To everyone who got hacked on problem 2 (me included) •  » » 3 years ago, # ^ | ← Rev. 2 →   wait how did everyone get hacked? like what was the test case?
•  » » 3 years ago, # ^ | ← Rev. 2 →   i also got hacked, but most hacked solutions won't pass system tests anyway so yeah.
 » tourist : 5 problem — 12 minutes...
•  » » My whole 3hr work ... LOL
 » 3 years ago, # | ← Rev. 2 →   Has anyone printed this for 1392E - Омкар и утка? (example with n = 10) 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 1 3 4 5 6 7 8 9 10 10 1 5 8 12 17 23 30 38 46 46 1 9 16 27 43 65 94 130 166 166 1 17 32 58 100 164 256 376 496 496 1 33 64 121 220 382 628 958 1288 1288 1 65 128 248 466 838 1420 2212 3004 3004 1 129 256 502 958 1750 3004 4720 6436 6436 1 257 511 1003 1915 3499 6007 9439 12871 12871 1 Submission: 90149344
•  » » 3 years ago, # ^ | ← Rev. 2 →   I used the same logic that you did except that I used the last element of each row equal to the second last element instead of using 1s.My submission — 90156646
•  » » I solved it as in the editorialCan you explain your solution?
•  » » » The matrix satisfies two properties -First, for any cell (i,j) the path which gives the smallest sum is always RRR...DDD... and the path which gives the largest sum is DDD...RRR...Secondly, for any cell (i,j) not lying in the topmost row or leftmost column, the maximum sum obtained in any path to the cell (i-1, j) is always 1 less than the minimum sum obtained in any path to the cell (i,j-1).After constructing such a grid, for each query we backtrack from (n,n) to (1,1) using these maximum and minimum sums.
•  » » » Let $S_{i, j}$ be the set of weights of all paths from (1, 1) to (i, j). The idea is that $S_{i, j}$ and $S_{i - 1, j + 1}$ should be disjoint. Also, $S_{i, j}$ can be obtained by merging $S_{i - 1, j}$ and $S_{i, j - 1}$ and adding a[i][j] to all weights. So, for each cell, you can greedily choose a[i][j] such that $min(S_{i, j}) = max(S_{i - 1, j + 1}) + 1$. It turns out that, for each cell, $S_{i, j}$ contains consecutive elements, so you can store efficiently these sets by storing only the minimum and the maximum.
•  » » Almost the same principle, but a little differences: zeroes in border path every number is just more than maximal path in upper part 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 2 3 4 5 6 7 8 9 10 0 4 7 11 16 22 29 37 46 56 0 8 15 26 42 64 93 130 176 232 0 16 31 57 99 163 256 386 562 794 0 32 63 120 219 382 638 1024 1586 2380 0 64 127 247 466 848 1486 2510 4096 6476 0 128 255 502 968 1816 3302 5812 9908 16384 0 256 511 1013 1981 3797 7099 12911 22819 39203 0 so my numbers bigger but still acceptable (max is 39_301_087_452_632 for 25x25)90174692
 » Problems were awesome, thanks for the fast editorial
 » can Anyone help me with some doubts I have. i attended a interview today and it has two question. can someone could say solution for it.https://codeforces.com/topic/82091/en2Thanks in Advance!!!!!
•  » » anyone please!!!! just giving idea to solve will be a great help
•  » » » First at least post it so people can comment on it. It is currently just a revision
 » Auto comment: topic has been updated by Tlatoani (previous revision, new revision, compare).
 » An easier solution for $H$.First, the answer is the expected number of jokers times (the expected number of cards you draw before a joker + the joker).The expected number of jokers can be expressed as $\sum_{k\geq 0}$ Pr[S is not full after $k$ jokers].By PIE, Pr[S is not full after $k$ jokers]= $\sum_{i=1}^n {n \choose i} (-1)^{i-1} (\frac{m}{m+i})^k$.So we get the answer.
•  » » Can you explain how PIE formula works here?
•  » » boboniu!
 » Thanks for a good round and fast editorial!
 » In Problem A,According to editorial [7,4,3,7] gives '1'. But it should be 3 right! [7,4,3,7] => [7,7(4+3),7] gives 3 right! Please help!
•  » » it is 1. in the array [7,4,3,7], you can do these steps: step 1: [7+4,3,7] step 2: [11+3,7] step 3:  Answer = 1
•  » » Hi Akhil, How about [7,4,3,7] => [11,3,7] => [14,7] => ?You can take any two consecutive and have to minimize.
 » Fast editorials are always great ! :) Thanks Tlatoani
•  » » Thanks!
 » The answer for H can even be simplified to $\left(\frac{n}{m+1}+1\right)\cdot\left(m\cdot H_n+1\right)$ where $H_n = \frac11+\frac12+\dots+\frac1n$.
•  » » Is there any combinatorics proof for this? (I assume not but) or just algebra
•  » » » My solution did not involve any algebra. Call an iteration of the process to be drawing cards until we reshuffle. In each iteration, we draw each of the $n$ normal cards with probability $\frac1{m+1}$ and 1 joker. Thus in expectation every iteration takes $\left(\frac{n}{m+1}+1\right)$ seconds.We now need to calculate the expected number of iterations (and we can ignore how many cards we draw during each iteration). Let's say there are $k$ remaining useful cards we need when we start an iteration. With probability $\frac{m}{m+k}$ the first {useful card or joker} is a joker, and we start a new iteration. The rest of the time, the situation has converted to the start of an iteration where there are $k-1$ useful cards we need. If we let $I_k$ be the number of iterations we need when there are $k$ things not in our set, so we note that if each iteration has probability $\frac{m}{m+k}$ of ending uselessly, and probability $\frac{k}{m+k}$ of converting down, then the recursive formula is $I_k = \frac{m}{k} + I_{k-1}$. Noting $I_1 = m + 1$ gives us $I_k = m \cdot H_k + 1$.Multiplying these two numbers together gives us the answer.
•  » » » » Thank you so much for the explanation, amazing and clean answer.
•  » » » » Can you just multiply these two expected values together? These two values don't seem to be independent (1 iteration implies that you must have drawn n+1 cards).
•  » » » » » Let $E$ denote expected value and $P$ denote probability. \begin{align*} E[\text{# of seconds until game ends}]&=\sum_{i=1}^{\infty}E[\text{contribution of }i\text{-th iteration}]\\ &=\sum_{i=1}^{\infty}P[\text{game did not end after }i-1\text{ iterations}]\cdot E[\text{length of }i\text{-th iteration}|\text{game did not end after }i-1\text{ iterations}]\\ &=\sum_{i=1}^{\infty}P[\text{game did not end after }i-1\text{ iterations}]\cdot E[\text{length of any iteration}]\\ &=\left(\sum_{i=1}^{\infty}P[\text{game did not end after }i-1\text{ iterations}]\right)\cdot E[\text{length of any iteration}]\\ &=E[\text{# of iterations}]\cdot E[\text{length of any iteration}]\\ \end{align*}We used the fact that the length of the $i$-th iteration given that the game didn't end after $i-1$ iterations is still $\frac{n}{m+1}+1$. However, this does not imply that $E[\text{# of seconds until game ends}|\text{game ends after }i\text{ iterations}]=i\cdot E[\text{length of any iteration}],$which is what you wrote above.
•  » » » » » It's worth pointing out that having the type of independence you correctly note is absent would likely not even be useful. (Not that its absence is a poor reason to take caution!) Sure, if $N$, $X$ are two independent non-negative random variables, then $\operatorname{E}[\,N \cdot X\,] = \operatorname{E}[\,N\,] \cdot \operatorname{E}[\,X\,]$, but if $N$ is the number of iterations and $T = N \cdot X$ is the total time elapsed, then the necessary value $X = T / N$ is probably tricky to say anything useful about, and there is no better hope of multiplying the duration of any single iteration by something convenient and getting the total duration of all iterations.Of course, thinking about when (and how often) each iteration duration $X_i$ in the infinite i.i.d. sequence $\{X_i\}_{i=1}^\infty$ will contribute to the overall time leads directly to the argument Benq describes above, but may have the downside that it "doesn't feel like" multiplication as much as a kind of factorization.Another way of approaching this, which uses more advanced concepts, but which might be more intuitive, is to note that $Y_k = \sum_{i=1}^k X_i - \left(\frac{n}{m+1}+1\right)$ defines a martingale, that $N$ is a stopping time with respect to its natural filtration, and that $T = Y_N + N \cdot \left(\frac{n}{m+1}+1\right).$It's then easy to verify that $Y_N$ satisfies the conditions of the optional stopping theorem, so that $\operatorname{E}[\, T \,] = \operatorname{E}\left[\, Y_N + N \cdot \left(\frac{n}{m+1}+1\right) \,\right] = 0 + \operatorname{E}[\, N \,] \cdot \left(\frac{n}{m+1}+1\right).$These abstractions might seem intimidating, but they really aren't doing much more here than capturing why Benq's argument works.
•  » » » » » » It seems that the result is known as Wald's equation in martingale theory.
•  » » » » Why is I_k = m/k + I_(k-1)?When there are k useful cards,the probability of converting down is k/(m+k).Why the expected number of iterations to k-1 useful cards is not the reciprocal of k/(m+k),and I_k = m/k + 1 + I_(k-1)?
•  » » » » » $I_k=\frac{k}{m+k}\cdot I_{k-1}+\frac{m}{m+k}\cdot (I_k+1)$
•  » » » » Why is the expectation for the first part $\ (\frac{n}{m+1} + 1)$?
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   If you choose any card (aside from the jokers), the probability that it comes before all $m$ jokers is $\frac{1}{m+1}$. Sum this over all $n$ cards (by linearity of expectation).
•  » » » » » » why the probability is 1/(m+1)?
•  » » » » » » » For any set of $x$ cards, each card comes first with probability $\frac{1}{x}$.
•  » » Hello sir conqueror_of_tourist, Why don't you open a YouTube channel, like you are one of the red coder which codes in python. It will be helpful for many of us. Please think about it. Thanks
 » I hacked tfg's solution for B.by test 1 1 1 -1.Its answer is actually 0 but tfg's solution got 1.
 » 3 years ago, # | ← Rev. 2 →   Spoilerwhile(k--) { int mx = 0; for(int i = 0; i < n; i++) { mx = std::max(mx, a[i]); } for(int i = 0; i < n; i++) { a[i] = mx - a[i]; } } Don't you think that tfg code for problem B is incorrect. mx should be start from -1e9 because array value can be negative alsoUPDATE: Now, it has been corrected.
•  » » Yes,actually it is.I hack 4 solutions with this test.THIS SOLUTION IS WRONG!!!
 » For D I would like to share my approachYou can split the array into segments which do not interact with each other. Each segment must either be - "RRLL" - "RL" - "RRL" - "RLL"dp[i] records the minimum number of changes needed such that arr[:i] is made up of the above segments.We can assume that the first element in the array do not interact with the last element of the array, by shifting the array four times and calculating the optimal changes required for each.
•  » » I did this too! I think you only need to shift it three times because the requirement is that the solution starts with R, and there are at most two Ls in a row, but I also happened to shift it four times just to be safe.
•  » » Hi! Can you please give the submission link to you solution? I am trying to find it , but unable to do so right now. Thanks.
 » 3 years ago, # | ← Rev. 3 →   In the problem B tutorial (c++ one) max taken here is 0 and should be taken -INT_MAX most people got hacked for that only. (edit : its been corrected).
•  » » So tfg's solution is wrong
•  » » » it's now been corrected.
 » 3 years ago, # | ← Rev. 2 →   I think the tutorial of Question C is wrong, or maybe I'm wrong, so if possible please solve my query. If the maximum element of the input slides occurs somewhere in between, then the next subsequent elements have to at least as big as this element. So taking max(arr[i]-arr[i+1],0) won't work. Consider this example.11617 15 12 16 25 15 12 18 19 16 15 11 14 16 17 17Now if you go by the tutorial you will get the answer as 26. But look there's a 25 in between. Meaning all the subsequent supports have to increases to at least 25 to make it a non-decreasing array. In that the answer would more than 25. Could you help qlf9
•  » » 3 years ago, # ^ | ← Rev. 2 →   You don't know how to get 26 for this example? For every $a[i - 1] - a[i] > 0$ in decreasing order of $i$, perform $a[i - 1] - a[i]$ operations over the range $[i, n]$.
•  » » » I know Nson. I get where that logic is coming from. But all I am saying is that this logic is wrong. I am even providing you with a counter example. Try the counter example and see it for yourself. If my counter example is wrong then please tell me. 26 is wrong for this example. As I said earlier, the 5th element is 2(which is also the maximum), meaning all the subsequent elements have to increased at least to 25 to make it a non-decreasing array. If i am misunderstanding something tell me
•  » » » » I just provide you the algorithm to build the correct answer.I ran locally and got these resultsinitial array [17, 15, 12, 16, 25, 15, 12, 18, 19, 16, 15, 11, 14, 16, 17, 17] perform 4 operations on range [12, 16] [17, 15, 12, 16, 25, 15, 12, 18, 19, 16, 15, 15, 18, 20, 21, 21] perform 1 operations on range [11, 16] [17, 15, 12, 16, 25, 15, 12, 18, 19, 16, 16, 16, 19, 21, 22, 22] perform 3 operations on range [10, 16] [17, 15, 12, 16, 25, 15, 12, 18, 19, 19, 19, 19, 22, 24, 25, 25] perform 3 operations on range [7, 16] [17, 15, 12, 16, 25, 15, 15, 21, 22, 22, 22, 22, 25, 27, 28, 28] perform 10 operations on range [6, 16] [17, 15, 12, 16, 25, 25, 25, 31, 32, 32, 32, 32, 35, 37, 38, 38] perform 3 operations on range [3, 16] [17, 15, 15, 19, 28, 28, 28, 34, 35, 35, 35, 35, 38, 40, 41, 41] perform 2 operations on range [2, 16] [17, 17, 17, 21, 30, 30, 30, 36, 37, 37, 37, 37, 40, 42, 43, 43] 
•  » » » » The first four elements can be smaller than 25. And I don’t really know what you want to prove.
•  » » Read the problem statement carefully before commenting.
•  » » it is right that all subsequent elements have to be at least 25 but it does not mean that to make them at least 25 we have to perform 25 or more operations.[12,13,25,12,20] here we need only 13 operations. Hope I got you right!!!
•  » » Thanks for helping me out. You guys are the best!!
 » Why doesn't the following work for H?f(0) = 0 f(i) = 1 + i/(m+i) * f(i-1) + m/(m+i) * f(n)My logic was that, at f(i), we must use a move and then there is a i/(m+i) chance the problem is reduced to f(i-1) and an m/(m+i) chance that we must restart (hence f(n)). Could someone help me understand the flaw in this approach?
•  » » You most likely misread the problem. There is replacement when a joker is drawn, and you should get a 2D recurrence of this form instead.
•  » » The deck is replaced for a joker
 » How to deal with overthinking, sometimes I end up making very complex logic even for easier problems like A and B ..
•  » » Do it for fun not for rating then you will be relaxed and automatically think simple.
 » Thanks for the great round and the fast editorial. I really loved the interactive problem.
 » 3 years ago, # | ← Rev. 2 →   can someone help me I am getting TLE on test 16 in E....https://codeforces.com/contest/1392/submission/90165976I got it don't bother.
•  » » You are using left shift to calculate power of (i+j).When (i+j)==31 it will give a negative number because if the number is shifted more than the size of integer, the behaviour is undefined. Try to calculate power of (i+j) with the help of dp and your solution will get accepted!
•  » » » replacing 1 with 1LL worked.... thanks though.
 » For F, if you look at the list of height differences, then the problem is identical to Juggling Troupe from NWERC 2017, except jugglers are allowed to start with more than 2 balls.
•  » » It's probably easier to solve F if you haven't seen this problem ...
•  » » » Actually there was also an old GCJ problem. It helped me a lot but yet another insight is needed for today's F, that's nice.
•  » » » Ah, yes. F is easier because the heights start out strictly increasing (meaning each juggler starts with at least one ball in the transformed problem)... didn't notice this.
 » Explain D plz....i just changed LLL to LRL and RRR to RLR....couldnt find any other observations.
•  » » Probably, you forgot that beds are arranged in a circle and got wrong calculations on prefix/suffix
•  » » » i checked on circles too. I still can't figure out where that observation fails.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   Well, if you changed LLL to LRL too, but by just searching LLL and replacing them — this will fail at RLLLLLR (You will get RLRLRLR instead of RLLRLLR), so it is better to replace LLL to LLR.
•  » » » » » Thanks. But, what will be the resultant string for LLLRRRLLL?
•  » » » » » » You're right, this replacement fails at this example :) But my solution counts answer without any replacements, so I just supposed this was your problem.
•  » » » » » » » Can you briefly explain your solution, please?
•  » » » » » » » » Firstly, if there are both L and R in string I move the prefix that contain only L or only R to the end, if the last symbol is the same (like in your example LLLRRRLLL -> RRRLLLLLL). Then, I look at substrings containing only one symbol — if length of this substring is L, you need to add (L + 1) / 3 to answer — it is not hard to prove. And if the whole string is "LL...LL" or "RR...RR" answer is (n + 2) / 3, it is easy to prove, too.
 » Could the tutorial be any faster ? :D Amazing contest. Thanks a lot.
 » Can anyone please provide test case where my code would't give correct answer for problem A? 90106564
•  » » If biggest number comes in first position.
•  » » It looks like any decreasing sequence (e.g. 6 5 4) should fail your solution, because this check: long.Parse(s)>firstMax will be false and you'll never assign anything to secondMax.
 » I think the tutorial of Question C is wrong, or maybe I'm wrong, so if possible please solve my query. If the maximum element of the input slides occurs somewhere in between, then the next subsequent elements have to at least as big as this element. So taking max(arr[i]-arr[i+1],0) won't work. Consider this example.11617 15 12 16 25 15 12 18 19 16 15 11 14 16 17 17Now if you go by the tutorial you will get the answer as 26. But look there's a 25 in between. Meaning all the subsequent supports have to increases to at least 25 to make it a non-decreasing array. In that the answer would more than 25.Could you help qlf9 Tlatoani
•  » » 17 15 12 16 25 15 12 18 19 16 15 11 14 16 17 17after 4 moves17 15 12 16 25 15 12 18 19 16 15 15 18 20 21 21after 1 more move17 15 12 16 25 15 12 18 19 16 16 16 19 21 22 22after 3 more moves17 15 12 16 25 15 12 18 19 19 19 19 22 24 25 25Do the rest on your own.
 » Thanks for the fast editorial! Request: Can the written explanations be hidden inside spoilers?
 » CONTEST WAS EXCELLENT! gg.
 » I solved 'D' with dynamic programming by changing the string so it is comprised of four available good options: string good[] = { "RL", "RRL", "RLL", "RRLL" }; I then tried 4 (the longest good sequence) different string shifts to account for circular nature of the problem.
•  » » I did something similar. DP with 4 cases.https://codeforces.com/contest/1392/submission/90124447
•  » » » Cool!It would probably be enough to only call solve() once, but initialize dp for all four cases: dp[0b00]=!(a==0) + !(a==0); dp[0b10]=!(a==1) + !(a==0); dp[0b01]=!(a==0) + !(a==1); dp[0b11]=!(a==1) + !(a==1); 
•  » » » » Hey, do you know some easy equivalent problem without circular arrays? The code is very difficult to understand with circular arrays. I was unable to find a problem like given a 1D boolean array, find the minimum number of operations so that there are no 'k' consecutive characters... or any other, which can be solved using dp. TIA
•  » » » » » I don't know non-circular equivalent, but although you need to put some thinking into circular nature of the problem, the code to account for it is quite short. In my submission (https://codeforces.com/contest/1392/submission/90138778) it's just shifting the string 4 times. In the editorial it's these lines: while(s.size() && s == s.back()) { cnt++; s.pop_back(); } 
•  » » » » I solved D in different way. I used a deque and a 3 element window. When I am getting LLL or RRR in the window I changed the 3rd element of that window to tht opposite one. But it failed on TC2.Link for submission. https://codeforces.com/contest/1392/submission/90165043I want to know is the approach totally wrong or something corner is missing.
•  » » » » » LLLRRHere it is obviously better to change the second L.
•  » » » » » » On my first attempt I changed the middle one ..it failed Then changed the last one...still failing
•  » » Can You Explain Why Are You Shifting the String ?
•  » » » Good "group" may start at the end of the string.Example: LLRRLR — it can't be separated into four seqeunces above,but if you shift it: RLLRRL = RLL+RRLBecause the longest group length is 4 (RRLL), I need to try 4 different shifts
•  » » Your code is very clean...Thanks!
•  » » » Glad you liked it
•  » » I was thinking the same logic but dp=0 stands always or not? I am getting an error in it;
•  » » » 3 years ago, # ^ | ← Rev. 2 →   dp = 0How many characters do you need to change in first 0 characters to get a correct string? Because empty string is correct (in this problem) then it's 0
 » why tle in test case 9 in problem B? code
•  » » Because:  for(i=0;i
•  » » » oh thanks
•  » » » wow I feel like an idiot for doing this too
•  » » » » I feel like an idiot for asking
 » How did everyone get hacked on B?Mine failed system tests btw.
•  » » 3 years ago, # ^ | ← Rev. 2 →   Many have initialized variable to 0 for finding max in array
 » Thanks for the round! I liked H. Kudos to simple solutions in the comments...I came to the similar recurrence as in the editorial, while I simplified the computation part. When we have $\lvert S \rvert = x$, we can remove the cards with a number in $S$ and set the operation time to $1 + \frac{x}{m+(n-x)+1}$ seconds instead of $1$ second.
 » 3 years ago, # | ← Rev. 2 →   I am unable to understand why my solution for problem C does not work, what is the possible error. Someone's help with an example test case in which my solution gives wrong answer is highly appreciated.
•  » » Use long long, not int
 » Clearly C wasn't rejected enough. Explains why it's the weakest problem of the contest.
•  » » I didn't understand the Editorial of C clearly.Can you explain C?
 » I had a different fucked up idea for task E using meet in the middle. Give random numbers to the array and find the path by using meet in the middle. Still don't know why I thought that the complexity would be O(T*2^n/2) when it was O(T*2^n). So yeah it failed on test 18. The probability to get a unique path is very high. I thought about the correct approach but this seemed way easier and I still can't understand why
•  » » Bear in mind that if the sum on your path is k, but your path is different from the actual hidden path, then your solution is still wrong! in task E what is the point in making this bold , what is 'actual hidden path'?? somebody pls explain, I think I don't get it........
•  » » » There can be different paths with same K. Thus if the system selects one of the paths and output other, then its basically wrong. It just meant all path weights should be unique.
 » 1 2^2 2^4 2^6 ... 2^2n 1 2^2 2^4 2^6 ... 2^2n 1 2^2 2^4 2^6 ... 2^2n 1 2^2 2^4 2^6 ... 2^2n 1 2^2 2^4 2^6 ... 2^2n ...I did this for 1392E - Омкар и утка. Is it wrong ?
 » what » any idea of the interactor of problem E. i mean , to prove my solution wrong you have to find at least 2 path with same sum. My question is how can i check this ? cz the sum might be very large.
 » 3 years ago, # | ← Rev. 2 →   Looks like I overcomplicated C a little bit using RMQ.Used a well-known approach though.
•  » » 3 years ago, # ^ | ← Rev. 2 →   How did you do it? I tried to do it during contest, but kept getting TLE. I tried updating all the elements from $i$ to $n - 1$ but kept getting TLE. Help please. Thanks! I tried using the approach from this.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   let $b_i$ be the minimum number we have to add to $a_i$ to make the array $a$ sorted. Now the answer is the minimum number of operations to make all $b_i$ equal to $0$.We can find the answer using this recursive function: long long f(int l, int r, long long mn) { int p=qry(l,r); // p = position of the minimum value in the subarray b[l...r] long long x=b[p]-mn; if(p>l) x+=f(l,p-1,b[p]); if(p
•  » » » » Thank You!
 » Problem C should have dp tag.
 » Sheldon approves the rejection count 73. Big Bang Theory fans will get this. Also, press F to display your condolences for the problem setters.
 » Can any one help me figure a counter test case that fails my solution for D? in this code, I look for sub-strings of length 3 that are either LLL or RRR and if found, I increase the answer by 1 and moves the i to the next triplet of characters.
•  » » 3 years ago, # ^ | ← Rev. 2 →   1 6 LLLLRL 
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Thank you!
•  » » » » That was a mistake. I updated the case, check now.
 » 3 years ago, # | ← Rev. 2 →   Here's my approach for problem E (Much less intuitive: I dont know how one thinks of a solution like given in the editorial).Idea is same: All paths should have different sums.Set row_1 and col_n to 0. Now we fill elements starting from col_n-1 to col_1 and row_2 to row_nCurrent max sum path through (i,j) is [(1,1)->(1,j)->(i,j)->(i,j+1)->(n,j+1)->(n,n)]Minimum sum path through (i,j) is [(1,1)->(1,j)->(i,j)->(i,n)->(n,n)]Value(i,j) should be such that minimum sum through (i,j) should be greater than current maximum sum through (i-1,j). Subtract the sum in 2 paths and add 1 to get Value(i,j)Now processing queries is easy. From (x,y) you go down if sum from [(x,y+1)..(n,n)] < required sum else you go right.For example n=6 0 0 0 0 0 0 70 35 15 5 1 0 70 35 15 5 1 0 50 25 11 4 1 0 30 15 7 3 1 0 16 8 4 2 1 0 1392E - Омкар и уткаMy solution
•  » » 3 years ago, # ^ | ← Rev. 2 →   I dont know how one thinks of a solution like given in the editorial A possible approach to come with that solution: - it could be useful to use powers of 2 (since different sums of distinct powers of 2 correspond to different numbers) - distinct powers of 2: this means that you could put a different power of 2 on each diagonal (since we visit each diagonal only once, the powers are distinct) - but this doesn't work because, if you are on some cell, at the next move you can go to 2 cells with an equal value, so you obtain 2 equal sums (i. e. the cells $(i + 1, j)$ and $(i, j + 1)$ have equal sums) - so, you need to "turn off" one of these two cells for each $i, j$ - after drawing some cases it's easy to realize that you can "turn off" cells with odd $x$I came out with your solution (link to comment) because I thought that $2^{50} > 10^{16}$, so I tried to put prefix sums of Pascal's triangle in the grid instead, then I optimized that approach.
•  » » » Completely forgot that distinct 2-power sums are unique. ThanksYeah your is exactly the same solution, extra 1 added. xd
 » Kudos for providing solutions in other languages than C++!!PS. But please don't write C++ in Java xD
 » My solution for B was hacked. How to view which test case failed?
•  » » Resubmit your code, you will get to know about the WA Testcases...
 » On E, I wrote a WA program but returned TLE. Why? TLE on test 1(WA) AC
•  » » You output the wrong answer, but your program doesn't stop.I think the problem description should remind participants of this.
 » I'm just curious about how the tests for problem E were made. I'm thinking of finding two paths with equal sum then asking for this sum. Is this how the tests were made or it's just random? I don't think it's random so if the testers can satisfy my curiosity I'd be glad.
•  » » I'm not the tester but I did write something like interacotor( which can generate data and test a program ) locally. It turns out that the data generated randomly is already strong enough for every wrong approach I know.
 » I had another approach for C: codell n; cin >> n; vector a(n); for(ll i = 0; i < n; i++) cin >> a[i]; if(n == 1) { cout << 0 << "\n"; continue; } ll ans = 0; for(ll i = 1; i < n; i++) { if(a[i] >= a[i-1]) { ll j = i; while(j < n && a[j] >= a[j-1]) j++; if(j == n) break; i = j-1; } else { ll j = i; while(j < n && a[j] < a[j-1]) j++; ans += a[i-1] - a[j-1]; if(j == n) break; i = j-1; } } cout << ans << "\n"; This is based on the fact that to increase the lowest point in a valley (the value go down then go up), all nearby value would be increase. So you just need to calculate the difference between the lowest point of the valley and the previous peak.
•  » » Please explain why this idea will work?? thanks in advance!!
•  » » » i explained it:This is based on the fact that to increase the lowest point in a valley (the value go down then go up), all nearby value would be increase. So you just need to calculate the difference between the lowest point of the valley and the previous peak.
 » I couldn't understand the solution of F, before I read the problem statement once again and realized that the constraint was not $h_1\leq h_2\leq\cdots\leq h_n$ but $h_1  » https://codeforces.com/contest/1392/submission/90188584 why this code giving memory limit exceeded •  » » you are declaring an unordered_map where key values in the range of 1e9. •  » » You can reduce memory usage by erasing map entries with value==0. erase() •  » » » thank you  » Hello, can someone help me with alternate explanation for C ?? I am not able to keep up with the explanation given in editorial  » About the proof of F, why is it clear that the order does not matter? •  » » I was also curious about that — it is plausible (a priori) there could be a way to get stuck depending on your order (or at least, it's not immediately clear why that's false).I proved that there can only be one difference of 0 in the end in a different way — I showed by induction that any two points with a difference of 0 must have a point in between with a difference of 2 or more.It took a long time though — if I knew that order didn't matter, the conclusion would be much faster. •  » » » Can you please elaborate your inductive proof? •  » » » » Consider the sequence of differences a[i+1]-a[i]. Let's call that sequence b[i].The claim is that if at any point i=2.Suppose this claim is false, and consider the first moment where this property fails — that means that b[i]=b[j]=0, and for all k, i b[k] <= 1. That means that the last move must have been somewhere on the interval [i,j]. Recall that a move at k reduces b[k] by 2 and increases b[k-1] and b[k+1] by 1. Since b[k-1] and b[k+1] are <=1, b[k-1] and b[k+1] must have been 0 before the move, and b[k] was 2 or more. But that means that the property was false on the previous turn too! A contradiction.With the claim, since the last moment has only 1s and 0s, we know there can't be 2 0s. •  » » 3 years ago, # ^ | ← Rev. 2 → viewing those operations as operator(function on vector), we only need to prove that operators are communicative, that is to say we only need to verify that for all index$i,j$, the operating order on$(h_i,h_{i+1})$and$(h_j, h_{j+1})$does not matter, which can be seen clearly for both$|i-j|=1$and$|i-j| \neq 1$cases. •  » » » If h=[1,3,4], then the only order is [1,3,4]->[2,2,4]->[2,3,3]. The other order [1,3,4]->[1,4,3]->[2,3,3] contains an invalid operation. •  » » » » It does not matter much as we only care the output after these operations, and do not care the validness of those operations (just do them formally). •  » » » » » Why do we not care the validness? If we swap two adjacent operations, one of them may become invalid and force the process to end. Tlatoani would you help explain why is it clear that the order does not matter? It is definitely true but i think it requires a (nontrivial) proof. •  » » » » » » If I get it correct, what the editorial does is just rearranging those operations, and what we need to make sure is that the output after rearranged operations is identical to the one after operations mentioned in the statement. Therefore, we may formally define operations$op_i$on all states instead of valid states and check the communicative property. Once we get that property, we can claim that rearrangement does not affect the final result, and the valid rearrangement is just a special case of this. •  » » » » » » This turned out to be harder to prove than I thought, but I think you can do something like this:If you have two sequences of maximal operations, then what we want to show is that they have to consist of the same operations (possibly in different orders). Since they are both maximal, they must either both be empty or both be nonempty. If they are both empty then we are done.If they are both nonempty: consider the current state of the vector (before applying either sequence of operations). Since the sequences are nonempty, there is at least one operation$\alpha$that can be immediately applied on the vector.Here we should make the observation that applying an operation at some index cannot prevent operations at other indexes from being able to be applied (it can only allow other operations to be applied).Therefore, applying other (different) operations cannot prevent operation$\alpha$from being able to be applied, so operation$\alpha$must occur in both sequences. From our observation, we can see that if, in either sequence, operation$\alpha$does not occur initially, then operation$\alpha$can be applied initially because by performing it earlier we are not preventing any of the operations in between from being applied.Thus, the first operation of each sequence is now the same, so we can apply the same argument to the remainder of the sequence (since it must be finite).Thank you for pointing out how this is nontrivial, I will probably update the editorial with this proof. •  » » » » » » » Can you please explain what does "maximal operations" mean? •  » » » » » » » » A sequence of operations such that you cannoy perform any additional operations at the end.  » In problem D. Omkar and Bed Wars. Can someone tell me how they come with this formula floor(n/3) or ceil(n/3). During contest i was very confused about this. Do we have to come up with this formula directly with intuition or their is some simple thinking strategy which can be used for other problems also. •  » » I assume you agree that the illogical strategy happens when there is$LLL$or$RRR$.So if the given string has all characters same, then you split it into, say, buckets of length 3 and flip the 3rd character, i.e.$RRR$->$RRL$. This way, if n is not divisible by 3, then there's at least one character left, and it wraps around to beginning where there are two same of them. In other words, the last, then first and second characters are the same so we need to deal with this. So it becomes$ceil(n/3)$or$(n + 2) / 3$. This is the case when the string has all same characters.If the string doesn't have all characters same, and has a maximal segment of length k of same characters. Then we do the same operation as we did above, however, this time, since both sides of the segment has different character and there'd be at most two characters at the end (and in the beginning), we don't have to deal with what's left at the end. Thus, the answer for this segment is$k / 3$. •  » » » okk !! now i understood how to think in a more better way. Thank you !  » For F, I didn't realize the heights were strictly increasing, I just thought they were non-decreasing. I believe my solution works for those cases too, if anyone is curious (or can find a counterexample).Slightly cleaned up submission: 90191364(I break the array into subarrays and solve each subarray. When the heights are strictly increasing, as in the actual problem, it just ends up doing a single subarray, haha.)  » 3 years ago, # | ← Rev. 3 → Can anyone spare some time to figure out why my solution is not working in C. My solution can be easily understood. Here is my code. Thanks in advance to that great soul who helps me. •  » » It is asked to find the minimum number of operations to make the sequnce non decreasing. You do not calculate that. Instead, you calculate the number of operations to make all elements equal.  » Can someone explain why in D we are rounding up instead of down? •  » » Here's my explanation.  » 3 years ago, # | ← Rev. 2 → Can anyone help me find error in my code for C problem thanks in advance here is the link https://ide.geeksforgeeks.org/M9zO7OyT2Z •  » » Please validate the output for following test case: 13 1 2 3 5 6 3 2 1 3 4 5 0 6 •  » » » I got 6 as the answer which i think is the correct ans •  » » » » 3 years ago, # ^ | ← Rev. 2 → 1 2 3 5 6 3 2 1 3 4 5 0 6 <- Input array 1 2 3 5 6 3 2 1 3 4 5 5 6 <- add 5 (at index 11) 1 2 3 5 6 3 2 2 3 4 5 5 6 <- add 1 (7) 1 2 3 5 6 3 3 3 3 4 5 5 6 <- add 1 (6-7) 1 2 3 5 6 4 4 4 4 4 5 5 6 <- add 1 (5-9) 1 2 3 5 6 5 5 5 5 5 5 5 6 <- add 1 (5-10) 1 2 3 5 6 6 6 6 6 6 6 6 6 <- add 1 (5-11) So, Ans = (5+1+1+1+1+1) = 10   » 3 years ago, # | ← Rev. 2 → Thanks for fast Editorial,Explanation for problem F is too good.  » Problem E when I tried to generate 2^50 with bit shift i.e. 1<<50, I got a negative value. Then I had to use the pow() fn.I wanted to ask : 1) Can I do the same with bitshift? If yes, How? 2) Is there any limit of pow() fn also? •  » » Yes, use 1LL << 50 •  » » » Oh right! Makes sense. Thanks :)  » Somehow in the problem B I though that the maximum element in the array minus 0 equal 0 :T  » 3 years ago, # | ← Rev. 2 → What is the idea behind this solution of F90126141  » For Problem E, the matrix can also be$ \begin{array}{ccc} 2^0 & 2^1 & 2^2 & 2^3 & 2^4 & 2^5 \\ 2^2 & 2^3 & 2^4 & 2^5 & 2^6 & 2^7 \\ 2^2 & 2^3 & 2^4 & 2^5 & 2^6 & 2^7 \\ 2^4 & 2^5 & 2^6 & 2^7 & 2^8 & 2^9 \\ 2^4 & 2^5 & 2^6 & 2^7 & 2^8 & 2^9 \\ 2^6 & 2^7 & 2^8 & 2^9 & 2^{10} & 2^{11} \\\end{array} $when$n=6$, since the duck is at$(x,y)\forall x,y\in [1,n]$, we can know the direction the duck walk to next step from the lowest bit of the sum of left problems.(Submission:90156663) It's a really interesting constructive problem, thanks for preparing this awesome round. =) • » » Upsolved it this way: $2^12^22^32^42^5000002^32^42^52^62^7000002^52^62^72^82^9$Just follow the bits of the path sum to find the path. It was a really interesting problem and I regret not spending enough time on it during the contest. •  » » » 3 years ago, # ^ | ← Rev. 2 → I solved it this way for lets say 4*4 matrix the matrix is1 2 4 8 0 0 0 164 8 0 320 16 0 64See paths diagonally!  » For I, KLPP could you please explain furthuer what does However, some faces are not interesting, namely the 2×2 square of adjacent cells. mean? Sorry for my bluntness, but I'm just sort of threw out the track right here QAQ. Thanks in advance. •  » » 2x2 squares of cells that either all have temperature >=x or temperature •  » » » 3 years ago, # ^ | ← Rev. 3 → Thanks, I think I'm kind of gettig it right :) •  » » » » Consider a face in, for example, the graph with vertices with temperatures >=x. You can see that this face is an area enclosed by vertices, which means that inside it there is a bad connected component or nothing(in the case of the 2x2 square). Let, for example, H represent cells with temperatures >=x and C otherwise:HHHHHHCCCHHC CHHCCCHHHHHHHere you can see that the face enclosed by the 'H' correspond to a bad connected component in the 'C'. However, in this particular case:HHHHThere is nothing inside, and thus it is not an interesting face. Sorry for my poor editing skills. •  » » » » » Oh, I think I've just realized what you mean the moment before you started to provide further explanation. So sorry for my stupid problem on understanding that formula. Anyway, thanks a million for your help, and it is a really educational and inspiring problem!  » what should be the answer for question d in the case 1 6 RRRRRR •  » » I think it should be 3 but most accepted codes print the answer 2 •  » » » 2 — RLRRLR •  » » » » Or one of the two other possible rotations: LRRLRR, RRLRRL  » "Fun fact: This problem was originally proposed as B"It might have had 5k+ ACs then....lol  » Can someone tell me why this solution 90172327 is wrong in problem C ? I loop on the numbers from the smallest and merge the equal numbers using DSU, so that they can be increased at the same time, and for each number I see the number to the left (after merging equal elements) if it was larger, then I need to increase that number, if the difference between the current number and the number on the right is smaller that between it and the number to the left, so I increase it to be equal to the number to the right  » "Clearly, the order in which we perform the slides (transfers of one square meter of dirt from$a_j+1$to$a_j$for some$j$) does not matter." Why ? Can someone explain ?  » who is getting the random t-shirts ?Please don't reply "random people"  » 3 years ago, # | ← Rev. 3 → In Problem C Editorial "Now let's look at the pair$a_j,a_{j+1}$. If$a_j≤a_{j+1}$(or if j=n), applying an operation would not change ans". Does the equality${a_j}=a_{j+1}$holds here?  » My blog discusses the solution to 1392F - Омкар и оползень if the original heights are non-decreasing instead of strictly increasing.  » 1 6 RLLLRRwhy does this give 1  » I solved H by brute-forcing for small$n,m$and I found this formula$f(n,m)=\frac{(m A_n + n!)(m+n+1)}{n!(m+1)}$,where$A_n$is A000254  » For problem I,whats meaning of C1 and C2?Can anyone help me? •  » » I think the connected components of graph 1 and 2?  » For the proof of Problem F, the editorial details an argument which requires the fact that "the order of operations does not matter". It is actually hard to prove this, and even with this lemma, it is a long and convoluted way to prove.I have a much simpler and intuitive proof!First, a lemma: If position$i$and position$i+1$have the same value (say$q$) in iteration number$j$, then in iteration number$j-1$: it is necessary that position$i$has value$q-1$and position$i+1$has value$q+1$. The proof of this lemma is simplicity itself and is left as an exercise to the reader (it is really easy, I am not tricking you).Now, for the sake of contradiction, let's say that we have as the final array a situation with more than one pair of equal elements. Because of the lemma, we can't have more than two consecutive equal elements. Now if the equal elements are as such$a$|$a$|$a+1$|$a+2$|$a+3$|$a+4$|$a+4\$then we by going backwards, we can reach an impossible state (where the array is not non-decreasing), hence the contradiction.And yeah, I use the fact that the array is always non-decreasing. It is also very easy to prove. (just use induction on iteration number).
 » can anyone explain reason behind the working of logic in problem c(https://codeforces.com/contest/1392/problem/C) in more detail by taking an example,im not understanding the editorial?
•  » » 16 months ago, # ^ | ← Rev. 9 →   Notice that the last element of the array will be the maximum element in the end of all operaions, so increment the array elements from right to left of array.for example in this test case:45 3 2 51- aa increment the segment[3:n] by(a-a) ,now array =[5,3,3,6]3-a>a increment the segment[2:n] by(a-a) ,now array =[5,5,5,8] now total operations =3.Here is my code ,it's very easy to understand it.
 » can anyone explain me problem 1392D - Omkar and Bed Wars