### Ormlis's blog

By Ormlis, history, 23 months ago, translation,

Thanks for the participation!

1754A - Technical Support was authored by KAN and prepared by DishonoredRighteous

1754B - Kevin and Permutation was authored and prepared by KLPP

1753A1 - Make Nonzero Sum (easy version) and 1753A2 - Make Nonzero Sum (hard version) were authored and prepared by Artyom123

1753B - Factorial Divisibility was authored and prepared by sevlll777

1753C - Wish I Knew How to Sort was authored and prepared by TheOneYouWant

1753D - The Beach was authored by Tikhon228 and prepared by Ormlis

1753E - N Machines was authored and prepared by Tikhon228

1753F - Minecraft Series was authored and prepared by teraqqq

• +217

| Write comment?
 » 23 months ago, # |   +23 i dont know why in 1d the ans with $\le 1$ op for each sunbed is optimal. can sb show me why?
 » 23 months ago, # | ← Rev. 3 →   0 My test cases are passing for 1753B - 27 - Factorial Divisibilityhttps://mirror.codeforces.com/contest/1753/submission/177676671but for 1 2 1000It returns No instead of Yes. I applied inverse modulo arithmetic approach. EDIT: I checked the constraints a[i] < x because of which, after dividing the number, the quotient will not cross the primes, which above test case doesn't fulfils.
 » 23 months ago, # |   +13 May I ask, how in the world solution of div1E runs ~150ms??? I mean the worst case is ~ 5k * 60 * 20 * 20 = 120kk, and there is a lot of jumping through memory in binary search. When I first thought about the solution I expected this would get TLE, or at least be very close to that. I mean the conclusion would be that you can do 10^9 jumps in array per second, which I think is not realistic?
 » 23 months ago, # |   +4 Can anyone explain Div1.C more detail?
•  » » 23 months ago, # ^ | ← Rev. 2 →   +28 You want to get an array where the zeros are at the beginning and ones are at the end. Let's say there were $k$ zeros and $(n-k)$ ones in the initial array.Look at the array prefix of size $k$. Note that if you had $j$ ones in at any point, that number cannot increase after an operation since we only swap two numbers if the former is greater than the latter.Therefore, we can define a random variable $R_j$ to be the number of operations it takes for the number of ones in the prefix of size $k$ to decrease from $j$ to $(j-1)$. If we find a way to compute that, then the expected number $R$ of operations for the number of ones in the prefix of size $k$ to decrease from $j$ to 0 is the sum of the expectations of $R_j$: $E\left[R\right] = E\left[\sum\limits_{1}^{j} R_i\right] = \sum\limits_{1}^{j} E\left[R_i\right]$Now we know that in order for the number $j$ of ones in the prefix of size $k$ to decrease, the two selected indices have to be those of a one from the prefix and of a zero from the rest of the array (suffix of size $(n-k)$). The probability of that happening is: $p_j = \dfrac{j \cdot j}{n(n-1)/2}$Therefore we can define $E\left[R_j\right]$ as follows: $E\left[R_j\right] = p_j \cdot 1 + (1 - p_j) \cdot (1 + E\left[R_j\right]) = \dfrac{2j^2}{n(n-1)} \cdot 1 + \left(1 - \dfrac{2j^2}{n(n-1)}\right) \cdot (1 + E\left[R_j\right])$Eventually you get: $E\left[R_j\right] = \dfrac{n(n-1)}{2j^2}$Add them up and you get the answer.
•  » » » 23 months ago, # ^ | ← Rev. 2 →   0 Thanks for a brilliant explanation !
•  » » » 23 months ago, # ^ |   +4 Can anyone explain this part: E[Rj]=pj⋅1+(1−pj)⋅(1+E[Rj])
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   0 Now we have the probability of $p_j$ to turn $j$ into $j-1$, and otherwise (i.e. the probability of $1-p_j$) $j$ will not change.So, there's a probability of $p_j$ that $R_j=1$, and otherwise $R_j=E[R_j]+1$ since the state does not change and we have wasted an operation.So we get the equation.Forgive my poor English.
•  » » » 21 month(s) ago, # ^ |   0 $E[R_j]=p_j⋅1+(1−p_j)⋅(1+E[R_j])$In the above equation the only part that I don't understand it is $(1+E[R_j])$ ,why we add the same expectation since it leads to infinity ??
•  » » » » 17 months ago, # ^ |   0 I think, it is just E[1 + Rj] (due to the one wasted swap) = 1 + E[Rj] (since E[a + b] = E[a] + E[b])
•  » » » » 4 months ago, # ^ |   0 Actually you do add the same expectation infinitely. If you think about it, this makes sense because you have the chance to repeatedly keep wasting moves forever. In the author's case, I think they just rearranged their equation to account for this. I suck at math, so I can't explain why this works. However I think I have logical way to explain the result. Suppose you have $n$ possibilities and $m$ of them are good. What is the expected amount of tries before you pick a good element? The answer to this is $\frac{n}{m}$.Why? Here we have a $\frac{m}{n}$ chance to pick a good element. Thus, if we picked $n$ elements, we are expected to pick $m$ good ones. Which on average means we will pick a good one every $\frac{n}{m}$ times. This also corresponds to the final equation, which is $\frac{1}{p_j}$.
•  » » 22 months ago, # ^ | ← Rev. 2 →   +3 I have not read nhtrnm's solution. But the transitions described in editorial are fairly straightforward if you think in the following way : If there are $g$ zeros (total number of zeros in the array) in initial $g$ positions, then the array is sorted. Let's assume there are $k$ zeros in initial $g$ positions. Now we make a move (swap). By making this move, we either end up with $k+1$ zeros (by exchange of $1$ from first $g$ position with a $0$ in the positions after that), or we end up with $k$ zeros (by any other type of exchange). The probability that we end up with $k+1$ zeros is given by $p$. You can easily calculate $p$. If the number of expected moves to sort the array if there are $k$ zeros in initial $g$ position is $dp[k]$, we have, $dp]k] = p*dp[k+1] + (1-p)*dp[k] + 1$ First term : we reach state with $k+1$ zeros by probability $p$, meaning we make extra $p*dp[k+1]$ moves to sort.Second term : we reach state with $k$ zeros by probability $1-p$, meaning there are extra $(1-p)*dp[k]$ moves to sort.Third term : the move we make to reach the above states has been added.
•  » » » 13 months ago, # ^ | ← Rev. 3 →   0 If we are moving from K to K+1 with prob P then why are we multiplying dp[k+1] with P. isn't dp[k]*p term added to dp[k+1] ? dp["To" State] += dp["From" State] * prob ? 
•  » » » » 12 months ago, # ^ |   0 Why dont you understand editorial ?
•  » » » 10 months ago, # ^ |   0 Perfect! Thanks!!
 » 23 months ago, # |   +13 A nice way to think about Div. 1 D is that the sunbeds are a matching of the bipartite graph and we want to increase the size of the matching by one. To do this, we find an augmenting path in the corresponding flow network. In such an augmenting path, each edge that corresponds to an edge currently in the matching needs to be matched with the edge before it or after it in the path, indicating that the sunbed is moved to the position corresponding to that edge. This should have cost p or q depending on whether the sunbed moves or rotates. We can encode this by modifying the graph in a suitable way, so that a shortest path in the graph corresponds to an optimal augmenting path in the flow network.
 » 23 months ago, # | ← Rev. 2 →   +2 Can someone please explain the mathematics behind Div2E/Div1C?If the probability for 1 1 1 0 0 1 getting sorted in 3 operations would be (1/15).(1/15).(14/15) then the answer should be (Z - 1)/X^Z where X = nC2 and Z is the number of zeroes which are not in the positions where they would be if the array were sorted.
 » 23 months ago, # |   +1 Why in problem C answer is dependent only on number of zeros in first g positions?
•  » » 22 months ago, # ^ |   0 Symmetry. Because moves that don't change the number of zeroes there, also don't change transition probabilities between states with different k - transition probability from dp[k] into dp[k-1] only depends on number of 0's and 1's in each subarray and invariant to a particular permutation of elements in subarrays. So we we can just partition states by number of zeroes and only have to calculate a single value dp[k] for each partition.First g positions are important because it's kind of a progress marker towards fully sorted end state.Important for symmetry is that we are considering all n(n-1)/2 pairs at each step. If instead for example we'd be choosing uniformly only among pairs with inversions, that'd break the symmetry as denominators and probabilities would be changing at each step.
•  » » 22 months ago, # ^ |   0 Consider the array in two parts:1~n0 and n1~n. And we want to swap all 1s to the right part.Call an operation "good swaps" if a pair of 0 and 1 in different "parts" are swapped(1 to right, 0 to left), and other operations can be ignored since they don't make any progress in our consideration.The array is sorted after and only after m good swaps are performed, where m is the initial number of 0s in the first n0 (g for you).The expected number( $\frac{C_n^2}{mm^2}$ ) of operations to perform a good swap only depends on the "remaining number" mm of good swaps. Then add ones that mm=1,2,...,m we get the rational number as desired.
 » 23 months ago, # |   +5 For Div.1 D, the editorial said It can be shown that in the optimal answer we use no more than one operation with each sunbed. I'm curious about how to prove it.
•  » » 23 months ago, # ^ |   +18 If this situation exists, there will be at least two free cells around the sunbed. After some classified discussion, you will find out that we can always spend less to achieve the target.
•  » » » 23 months ago, # ^ |   +5 in most combinations of ops it's easy to prove that they are either replaceable by less costly one or requires two continuous free cells to do it, but i can't prove why $\pi\operatorname{-rad}$ rotation(i.e. fix the same end during two rotation in the same direction) is replaceable by better one.
•  » » » » 23 months ago, # ^ |   0 It can prove that you don't need fix the same end during two rotation in the same direction. If you want a cell to be empty, you only have to rotate it once at most, because if the cell itself is empty, you don't have to rotate it, otherwise you only have to rotate the sunbed on that cell once. It can be proved that the newly occupied lattice after rotation does not contribute to the adjacent lattice of the current lattice. So you don't have to rotate the sunbed anymore.I'm sorry for my poor English.
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   +5 This situation will never happen because we've run Dijkstra's algorithm twice. In the first time, we only visited the cell $(x,y)$ satisfied $(x+y)\bmod 2=0$. In the second time, we only visited the cell $(x,y)$ satisfied $(x+y)\bmod 2=1$. Obviously, no cell could satisfy these restrictions simultaneously.
•  » » » » 23 months ago, # ^ | ← Rev. 7 →   +8 Assume the map of the beach is painted in a chess coloring as the official editorial says, but red and blue.What you have already disproved is operating twice on two cells colored differently is impossible.Another two assumption is freeing one red cell first and then a neighboring blue one, and the destination of a move is already free(or else freed, by recurringly solve it (UPD:It can be shown that we can't operate on a sunbed moved during the first recursion, either, for the $\pi-\operatorname{rad}$ rotation you say of it is impossible for it changes arrangement of the red twice but doesn't affect the blue ones, and the other operations moves it twice, which you have already disproved)). Firstly, it's obvious that we can't free the other side of the same sunbed(the only moved one), for the destination is already another two continuous free cells as you say. When freeing a blue cell, a free red one(another one but the previously free one) can be useful only for placing another red end, but we want to change the arrangement of the blue ones, so it can only be used for another operation on the blue ones. That's the contradiction — the destination of the last move is two free cell, again(we don't need the first rotation instead of once or twice). So the second free red is useless except for freeing another red one.You rotate twice to free the first destination to free the first destination, but we have a better way. The further prove of the original problemThus, it can be shown that only the corresponding red occupied cell of a neighboring blue occupied one(but not the free ones) is the only needed info of the blue when we consider freeing a red one, and vice versa.So the all the needed information of red ones has been already fixed and the moved sunbed doesn't affect the following process. So we don't enumerate the red we free before applying the second Dijkstra's algo, and we only apply Dijkstra's algo twice.Sorry for my broken English and logic.
•  » » » » » 23 months ago, # ^ | ← Rev. 5 →   +8 A better logic of this proof:(Here, operations on sunbeds have the same meaning as the problem says, and operations on cells mean moving the free cell, the same as the editorial says.)Theorem: All the sequences of 2 or more operations on the same sunbed is replaceable.There's a simpler way to prove it, so the following proof needn't be done unless you wish the problem to get more complicated. Another proofPr: it's easy to prove they are replaceable except the reversion (called $\pi-\operatorname{rad}$ rotation above), which need tons of casework without the lemmas below.Lemma 1: 2 or more operations on differently colored ends of the same sunbed are replaceable(i.e. there exists one or more sequence of operations that is not worse than the current one).Proof: they are either replaceable by less costly one or requires two continuous free cells to do it. (As Dotswana said).we divide the original problem into freeing a red cell and a blue one below (we can prove that they can be solved separately according to the propositions below).Corollary 1: we can't go through the free red cell when we're freeing a blue one, and vice versa.Pr: we couldn't move the blue (Assume we're freeing the blue one in the proof) end of the corresponding moved red end again. So we could only operating on the red cells, but not blue cells, and they don't affect blue movements and can be deleted.Corollary 2: the useful information about red cells when freeing a blue one only contains the corresponding end of the red end of a sunbed (to get which type of operation we're doing), and vice versa.Lemma 2: movements for freeing two red cells simultaneously is replaceable by operating on only one of them.Pr: easier to prove with the Additional Proposition below, but here's another one: when we're freeing a blue one, we can't move any of them according to Corollary 1. So it's replaceable by only keep the one in the final answer free(which is a better answer).The Final Proof: if we operate on a red end twice, it's replaceable, for it either move the cell into the original place or is replaceable by operating only once. Additional PropositionAll the needed and irreplaceable information of red ones has been already fixed and the moved sunbed doesn't affect the following blue process.(Assume we free the red one first)Pr: the sunbed we've moved in the red turn couldn't be freed again for violating the Theorem, and the others remain unchanged.Therefore, we can consider the red and blue part independently.
•  » » » » » » 23 months ago, # ^ |   0 Clearer and easier to understand than mine. Thanks!
 » 23 months ago, # | ← Rev. 2 →   +13 [UPD: Please ignore I was wrong]
 » 23 months ago, # |   +3 Alternative solution to A2 (that doesn't require checking parity): Like A1, consider pairs of values, except now we look at pairs of non-zero values. Specifically, we have some non-zero value $a$, followed by $k$ 0s (possible to have no 0s), and then a non-zero value $b$. If $a \neq b$, simply take a segment of $a$ with all the $k$ 0s (if any), and a segment with only $b$. The values of these segments would cancel each other out. If $a = b$, we have two cases: If there are no 0s in between, this is like A1, where we can put them both in one segment with a value of $0$. If there is at least one 0 in between, take a segment of $a$ with the next $(k - 1)$ 0s (all but one), and then a segment of $[0, b]$. The sign on $b$ will flip, so the values of these segments cancel each other out. My submission: 177658418 (I used a 0-indexed vector, which might be confusing, sorry)
•  » » 22 months ago, # ^ |   0 thanks. also how did you get to expert in 3 months. orz can u dm me tips
•  » » 20 months ago, # ^ |   0 Hey Andalus can you help me in my cod. It failing in WA2. Here is my submission i'd
•  » » » 20 months ago, # ^ |   0 First, let me teach you how to identify the problematic test-case. Please examine the following submission: 189156699. The code is copied from yours, but I changed the main function and added burn and reveal functions to show the problematic test case. Please use this technique in the future to reveal test-cases that your solution fails at.As for the actual issue with your code, it does not handle the case of $n = 1$ correctly.
•  » » » » 20 months ago, # ^ |   0 Sorry, But i'm not understand how burn and reveal function work in finding wrong test cases (can you please explain more so that i change those function according to my question in future). Although i handle the case of n=1 but still it gives wrong answer.
•  » » » » » 20 months ago, # ^ |   0 In the submission you linked (189085095), the test details indicated that your code failed in the second test suite, at test case 9576. So what I did was modify your code so that when $t == 9840$ (second test suite), the first 9575 cases will simply have their input read with no output being printed. Then, for the 9576th case, the program should read the input and then print the same input. When submitting this code, the program output for the second test suite will display the 9576th test-case, so you can identify exactly what the input is that caused your program to fail.Anyway, regarding your latest submission (189217586), you still did not correctly handle the case where the array is simply $[0]$. Here, the output is supposed to be: 1 1 1 indicating that there is only 1 segment, and its range is from index 1 to index 1. However, your output is: 1 1 which does not follow the correct format of specifying the number of segments first.
 » 23 months ago, # |   +1 In D1C, the answer for third test case is $\frac{75}{4}$ = 18.75 . I tried finding out the expected moves to swap by $10^6$ random experiments. I am getting values in the range [29.5, 30.05], which is too far from editorial answer. Where is my code wrong? I have tried seeding it with start time and also with the experiment number. In both, I am getting same. Here is code: https://pastebin.com/yBMgahy4 . It'll take around 4 seconds to run.
•  » » 23 months ago, # ^ |   +1 swap(a[i],a[j]); In the original problem, it only swaps when $a_i>a_j(i •  » » » 23 months ago, # ^ | +1 Thank you.  » 23 months ago, # | 0 I am not so good at math, help. At problem 1753C, in the recurrence equation:$dp[k]=1+dp[k]⋅(1−p)+dp[k+1]⋅p$. I kind of understand$dp[k]⋅(1−p)$and$dp[k+1]⋅p$. But I don't know what does the value$1$mean. Please explain :>. •  » » 23 months ago, # ^ | +1 dp[k] is defined as expected number of moves to reach n from k. dp[k] is defined recursively by the following: after making 1 move what is the expected moves to get to n. This is the 1 in the formula. •  » » » 23 months ago, # ^ | 0 Ohhh o:! Thanks a lot :).  » 23 months ago, # | 0 Div2 C1 and C2 have Dp as one of the tag, can someone suggest how to use dp in this problem? •  » » 12 months ago, # ^ | 0 I solved it using DP, but I think it can be optimised in terms of lines of code.  » 23 months ago, # | +18 If you failed 1D/2F on test 13 with your answer 3000000016，you may try this. 4 3 1 1 #U# .D# #U. #D#  •  » » 23 months ago, # ^ | 0 Thank you kind stranger! Just posted a question asking why the graph needs to be directed and then found this comment •  » » 21 month(s) ago, # ^ | 0 Thank you it is wounderful test case •  » » » 21 month(s) ago, # ^ | +3 Glad that it helped you :)  » 23 months ago, # | ← Rev. 2 → 0 A different way to think Div 2 E.The Initial Array with$1's$and$0's$has four scenarios$S_{ones}$-> count of$1's$already at sorted positions(don't need any swaps).$S_{zeros}$-> count of$0's$already at sorted positions(don't need any swaps).$NS_{ones}$-> count of$1's$not in sorted positions (They need a swap with some$0$).$NS_{zeros}$-> count of$0's$not in sorted positions (They need a swap with some$1$). Try to figure out yourself A swap between$NS_{ones}$and$NS_{zeros}$is the only valid swap we have which will help in sorting the array.$NS_{ones}$is always equal to$NS_{zeros}$. So when we randomly select$2$indices$i 177811759
•  » » 21 month(s) ago, # ^ |   0 The second possible case seems to be wrong as there will be no NS1 after a S1. And i guess there will be 12 possible cases. I may be wrong, can you plz check it once
•  » » 21 month(s) ago, # ^ |   0 Although the final formula for the answer is absolutely correct :). Thanks your explanation helped me!
 » 23 months ago, # |   +8 After reading the Div1 C task, I was kinda surprised that it was not well known. The tasks seems like something someone must have thought about already but in actuallity, has't. The problem was rather beautiful and elegant yet fresh. Kudos to the problem author :)
•  » » 23 months ago, # ^ |   0 :)
 » 23 months ago, # |   0 For D1E, it's probably worthwhile to note that this idea is Alien trick in disguise. In fact, for most of those problems where the naive is "take the first X elements from this heap", you can optimize it by binary searching on the last thing that will be selected from the heap (i.e. Alien trick).
 » 23 months ago, # |   0 In Div1.C，my recurrence formula is $dp[i] = p * dp[i - 1] + (1 - p) * dp[i] + 1$The number of zeros in the array is $g$, and $o$ is the initial number of zeros in the first $g$ positions.$dp[i]$ means the expected number of operations I need to make origin array's first $g$ positions exist $i$ zeros.so $dp[o] = 0$ and the final answer is $dp[g]$. but it seems wrong, I don't know why.
 » 23 months ago, # |   0 Hi, I still don't understand the problem 1753B — Factorial Divisibility. I don't understand the case when there are leftovers, why do we can say that if that happens, it's no divisible by x! ? For example how to know that 3*7! + 4*5! are not divided by 8!?Could someone help me please?
•  » » 23 months ago, # ^ | ← Rev. 2 →   +1 3*7! + 4*5! < 7*7! + 5*5! < 1*1! + 2*2! + ... + 7*7! < 8! (proof of last transition is in editorial)If number is less than 8! it can be divided by 8! only if it's a zero
 » 23 months ago, # |   0 In problem div1 E, what does "continue estimating this value fairly" mean? I think $4608$ is the proper upper bound. What is that $15000$? Is that a simpler (but more rough) estimate of $F(C)$?
 » 23 months ago, # |   0 Div1 E.the $profit_j$ should be $(lmul - 1) \cdot rmul \cdot a_j$.
 » 22 months ago, # |   0 In Div1-C, how to find $x$ such that $pq^{-1} \equiv x$ (mod $M$) if we have $p$ and $q$?
 » 22 months ago, # | ← Rev. 3 →   0 In the last problem, there are no tests countering 16-bit storage (see my submissions, it's not really an optimisation, just a bug — I misread bounds at first). One such test: 3 3 65538 3 1 1 1 2 2 1 [x 2^15] 3 3 1 [x 2^15] 3 3 2 Btw my solution's pretty dumb semibrute force — for each diagonal, I do a 2-pointers-like algorithm to find maximal bad squares with a bitset for MEX, time $O(\mathrm{min}(N,M) K + NMT/\omega)$.
 » 9 months ago, # | ← Rev. 2 →   0 Can someone explain why in DIV1C linearity of expectation can't be used. My explanation:M is number of ones K is number of zeros in [(N-M), N] region Expected move of all zero = (moving first 0 out of places to left of (n-m) + moving second zero + ... moving subsequent zeros)My understanding from https://www.youtube.com/watch?v=LX2q356N2rU video is.If all the events happening in a set contributes to individually to concerned move.for eg if we have 3 green and 4 red balls and if we pick 2 balls at random one after the another. Then expected number of red balls = (4/7) + (4/7); Since in DIV1C, we can't decompose every event, such that every event contributes to individual zeroed value's expected sum, we can't use linearity of expectation.
 » 5 weeks ago, # |   0 for C, does anyone know why they are using $dp[k]$ on the right side of the recurrence relation?