### DmitryGrigorev's blog

By DmitryGrigorev, history, 2 years ago,

(Idea of the problem A — ----------)

Code

(Idea of the problem B — IbragiMMamilov)

Code

(Idea of the problem C — usertab34)

Code

(Idea of the problem D — Denisson)

Code

(Idea of the problem E — Ralsei)

Code

• +61

 » 2 years ago, # |   0 Auto comment: topic has been updated by DmitryGrigorev (previous revision, new revision, compare).
 » 2 years ago, # |   0 Can anyone share other approaches for problem E .
 » 2 years ago, # |   +12 The code links are bringing me back to this blog, please fix them :D
 » 2 years ago, # |   +1 code link break
 » 2 years ago, # |   +1 finally the editorial!
•  » » 2 years ago, # ^ |   0 finally Petr
 » 2 years ago, # |   +6 Such a great second solution for D.
•  » » 10 months ago, # ^ |   0 Can you explain it further? I didn't get the tutorial.
 » 2 years ago, # | ← Rev. 2 →   +6 Why I am getting you're not allowed to view the requested page when I click on code of all question.
 » 2 years ago, # |   0 the links get back to this page??why is it so??
•  » » 2 years ago, # ^ |   0 Now its fixed
 » 2 years ago, # |   +3 Can someone share some intuitions for how to come up with a solution for problem E ? Implementing the editorial's solution is relatively simple but coming up with such a solution from scratch is not as simple.
•  » » 2 years ago, # ^ |   0 I found this comment really helpful.
 » 2 years ago, # |   0 Can anybody explain me how to do DFS on a complemented graph fast enough. I don't understand the explonation for the problem D. The realization that i can see takes $O(n k log m)$ time where k is amount reachable vertices. For example, n = 5 and 4 is reachable frome 5, 3 — from 5, 1 — from 3 and 2 — from 3. the algorithm start at 5. it looks through (1, 2, 3, 4), sees that 4 is reachable and goes to 4. it looks throuth (1, 2, 3) and doesn't see reachable and goes back to 5 and looks through (1, 2, 3), sees that 3 is reachable and goes to 3, looks through (1, 2) and sees that 2 is reachable and goes to 2, looks throuth (1), sees that 1 is unreachable, goes back to 3, looks through (1), 1 is reachable, goes to 1, looks through (), goes back to 3, then goes back to 5. End.In this way I have undertood the explanation. Then let's cosider a graph with n vertex wich has only edges from n to each node of set {n — k + 1, ..., n — 1}. For such graph the steps which described above takes O(n k log(m)) time.
 » 2 years ago, # |   +3 could you anyone give me example code of C please?? i can't understand the meaning of editorial.
•  » » 2 years ago, # ^ |   +1
•  » » » 2 years ago, # ^ |   +3 thank you so much.
 » 2 years ago, # |   +10 Best codeforces explanation I've ever seen. Thanks!
 » 2 years ago, # |   0 Can some one explain me how the complexity for first solution of problem D is O(n+m). Won't it be n^2 in worst case if set P keeps on increasing.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +2 We check if pupil adds to $P$ in $O(deg)$ time, where $deg$ is number of pupils, with which he can swap. Sum of $deg$ for all pupils is $O(m)$.
•  » » » 2 years ago, # ^ |   +10 Got it .. thanks a lot!!
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 "This solution works in O(n+m)" in solution 1 but assuming a scenario such that every element could swap with last element(Nastya) but could not swap with the element just previously inserted in set P(element behind ith elem in queue), then finding whether ith could swap with all elements of P would take O(n*n)==( 1 + 2 + 3 + ... + n-1). Correct me if my analogy is wrong. ex. 6 10 6 3 1 5 4 2 6 2 3 2 1 2 5 2 6 4 3 4 1 4 6 5 3 5 6 1 Wouldn't complexity be O(n*n) in such cases?Here is my Submission are there any other specific way implementation which could reduce complexity?
•  » » » » 2 years ago, # ^ |   0 I just got the idea, actually it will be O(n+m) but one point to note is that in worst case m could be equal to n*n.
 » 2 years ago, # |   +1 Can someone explain D's solutions with an example ?
•  » » 2 years ago, # ^ |   0 So we start from end of the queue, i.e., from Nastya. Now if person next to Nastya will let her move to front, then we will swap them. But if he doesn't then we'll add him to a set P. This set P signifies the set of all people that need to be swapped with a new person we encounter so that Nastya can move a step forward in the queue (as Nastya can move a step forward only if all the persons ahead of her, that can't be swapped with her, move a step forward). Note: Nastya was added initially to set P, as she always needs to be swapped to move a step forward.I will give an example if still needed.
•  » » » 2 years ago, # ^ |   0 please give the example and explain it
 » 2 years ago, # |   0 I have understood solution B of Problem D..But I am not able to understand the code!.Specifically what is "was" vector...and cnt and cnt2? Can anybody explain it? Thank You
 » 2 years ago, # |   0 can someone please explain C , i did not understood the editorial
•  » » 2 years ago, # ^ |   0 Just remember one thing. After taking any number of transposes the value of (i + j) doesn't change. Here (i, j) is the position of any cell in the matrix. So just store the count of every element for every (i + j) for both the given matrices and compare both. Here is my submission
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Why the value of (i+j) doesn't change.
•  » » » » 2 years ago, # ^ |   0 Suppose you are taking the transpose of a square submatrix whose upper left corner is (a, b). consider a point (i, j) who fall under the submatrix. Its coordinates w.r.t. to (a, b) would be (i — a, j — b). After talking transpose it would become (j — b, i — a). Now again the real coordinates of this point would be (j — b + a, i — a + b). So you can see initially the coordinates were (i, j) for which sum of coordinates was i + j. In the later case it is also i + j.
 » 2 years ago, # |   0 Is my understanding of solution 1 for Problem D correct?So we start from end of the queue, i.e., from Nastya. Now if person next to Nastya will let her move to front, then we will swap them. But if he doesn't then we'll add him to a set P. This set P signifies the set of all people that need to be swapped with a new person we encounter so that Nastya can move a step forward in the queue (as Nastya can move a step forward only if all the persons ahead of her, that can't be swapped with her, move a step forward). Note: Nastya was added initially to set P, as she always needs to be swapped to move a step forward.
 » 2 years ago, # |   0 Anyone explain me 1136C — Nastya Is Transposing Matrices, in more detail.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 you have to observe that in any case u transpose a matrix or a submatrix , the elements in the diagonals are always same . so given two matrix a and b , if every diagonal element of matrix a = diagonal element of matrix b , then matrix can be transposed in any scenario , else now .
•  » » 2 years ago, # ^ |   0 You have two types of diagonals, ones with i+j constant(top right to bottom left) and ones with i-j constant(top left to bottom right). When you take any square sub matrix and apply transpose, you find that elements on the 2nd type of diagonal change positions. But they remain on the same diagonal. In other words, [0][0] can't change it's place. [1][0] and [0][1] can swap places among themselves but not with any other element. We can also obtain any permutation of an (i+j) diagonal by starting with the top left corner and progressively fixing elements in the next diagonal by picking matrix of size 2x2 and swapping elements which aren't on the main diagonal of it. So we only need to check if the corresponding multisets of diagonal (i+j) are same.
 » 2 years ago, # |   0 Can anyone give explanation of solution 1 of problem D?Whats the idea?
 » 2 years ago, # | ← Rev. 2 →   0 Explanation of problem C:Very first and only one thing you need to understand is that "Elements along any diagonal from top-right to bottom-left will always remain in that diagonal, no matter how many transposes we perform on whatever submatrices". This is true because we can always choose a sub-matrix of size 2x2 and change order of elements in that diagonal (from top-right to bottom-left) and get original matrix. ex 1 2 3 4 after transpose will change to 1 3 2 4 we swapped 2 and 3 while 1 and 4 are still in place.For an example of 3x3 matrix see fig. Figure So only thing which matters is that we have same elements in every diagonals in whatever order.Here is my submission
 » 2 years ago, # | ← Rev. 2 →   0 DmitryGrigorev In the editorial for the graph approach of problem 1136D, could you please tell what you meant by standard algorithm "DFS by complement graph". Thank you.
 » 2 years ago, # | ← Rev. 2 →   0 I wrote a recursive solution for D. I think the overall complexity of my approach is )(n+m) but I am getting Time Limit Exceeded. https://codeforces.com/contest/1136/submission/52883893My recursive function on a given position tries to move the pupil at that position ahead in the queue by one place by either:- 1. trying to swap with the person in right in front. 2. trying to get the person right in front to move ahead so that another pupil comes right in front and then try the same thing with the new pupil.Can someone help me why it's getting TLE? Thanks.
 » 2 years ago, # |   0 Am I the only one who used Binary search in first question?
 » 11 months ago, # |   0 Ralsei Can you Clarify how the complexity of Problem D is O(n+m). According to my calculation, it must be O(nm log(m))
 » 9 months ago, # |   0 Can you tell how to find minimum no. of transpose operations to do in a matrix so that it becomes another given matrix? Always it will be. Please give me an idea.
 » 4 months ago, # |   0 Can anyone explain the 2nd solution of D?I couldn't figure it out.
 » 7 days ago, # | ← Rev. 7 →   +1 My solution to Problem E — Nastya Hasn't Written a Legend supports modifications of k (assuming each modification makes things still stay valid or there's another conditional update that makes things stay valid) and this solution is completely different than the editorial's solution. Furthermore, the complexity of my solution is $O(n\log(n))$ My Solution:let's say index $i$ is special if and only if $a_{i+1} - a_{i} > k_{i}$at each update, we say index i changed state if and only if it was special before the update and after the update it's not special, or if it wasn't special before the update and after the update, it became special (i.e, the special status of $i$ flipped).let $t_i$ be the total number of indices that changed state in the $i$'th update.Claim: $\sum_{i=1}^{q}{t_i} = O(n+q)$ (i.e, the total number of changes in all updates is linear)Proof: At each update, at most one index becomes special. If $i > 0$ & $i-1$ was not special & $x>0$, then $i-1$ becomes special. I claim all other indices don't become special if they weren't. All indices $< i-1$ trivially don't change state as they don't change value. Indicies $> i$ are only updated because of carrying and the need for the difference to be exactly k, namely no difference $> k$ is ever being created therefore non of these indices will become special. so the total number of indices that become special is in the worst-case $O(q)$, and we initially start in the worst case with $O(n)$ special indices. Each change of special -> not special requires the index to have been special and the total number of things becoming special or initially being special is $O(n+q)$ therefore the total number of these differences (special-> non-special) is also $O(n+q)$ in the worst case, therefore, the total number of changes is $O(n+q)$ and we are done. $\blacksquare$How do we use this fact? The main observation is that in order to update a continuous range of nonspecial indices, we simply need to add X to all of them.we maintain the division of the array indices into segments in which all elements are not special except the last element. We also maintain a data structure (in my code, a lazy segment tree) that supports range add & range sum query. for an update, we initially find the segment the updated index belongs to, if the element before it is in the same segment (i.e it's not special), we split the segment into two segments accordingly (where i-1 is the last element in the left split part). we update all elements with an index bigger than or equal to it that are not the last element by doing a range add on our data structure. then for the last element in the segment, we add to it the maximum value we can such that the difference is >= k and subtract what we added from the variable that stores the amount we need to add. if it became nonspecial we merge the segment and the segment after it if it exists and then we recursively solve again if we still have something to add. Now the beautiful part: because of our observation, the total number of merges and splits will be $O(n+q)$, therefore the complexity of this solution is $O((n+q)\log(n))$ $\blacksquare$. I initially left some of the details in this part vague in order to let you explore and see the beauty in utilizing these two observations. Note that the definition of special only depends on current k, therefore, updating k values is easy.