### DmitryGrigorev's blog

By DmitryGrigorev, history, 2 weeks ago, ,

(Idea of the problem A — osaaateiasavtnl.)

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 weeks ago, # |   0 Auto comment: topic has been updated by DmitryGrigorev (previous revision, new revision, compare).
 » 2 weeks ago, # |   0 Can anyone share other approaches for problem E .
 » 13 days ago, # |   +12 The code links are bringing me back to this blog, please fix them :D
 » 13 days ago, # |   +1 code link break
 » 13 days ago, # |   +1 finally the editorial!
•  » » 13 days ago, # ^ |   0 finally Petr
 » 13 days ago, # |   +6 Such a great second solution for D.
 » 13 days 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.
 » 13 days ago, # |   0 the links get back to this page??why is it so??
•  » » 13 days ago, # ^ |   0 Now its fixed
 » 13 days 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.
•  » » 13 days ago, # ^ |   0 I found this comment really helpful.
 » 13 days 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.
 » 13 days ago, # |   +3 could you anyone give me example code of C please?? i can't understand the meaning of editorial.
•  » » 13 days ago, # ^ |   +1
•  » » » 13 days ago, # ^ |   +3 thank you so much.
 » 13 days ago, # |   +10 Best codeforces explanation I've ever seen. Thanks!
 » 13 days 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.
•  » » 13 days 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)$.
•  » » » 13 days ago, # ^ |   +10 Got it .. thanks a lot!!
 » 13 days ago, # |   +1 Can someone explain D's solutions with an example ?
•  » » 9 days 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.
•  » » » 7 days ago, # ^ |   0 please give the example and explain it
 » 12 days 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
 » 10 days ago, # |   0 can someone please explain C , i did not understood the editorial
•  » » 10 days 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
•  » » » 7 days ago, # ^ | ← Rev. 2 →   0 Why the value of (i+j) doesn't change.
•  » » » » 6 days 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.
 » 9 days 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.
 » 7 days ago, # |   0 Anyone explain me 1136C — Nastya Is Transposing Matrices, in more detail.
•  » » 6 days 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 .
 » 6 days ago, # |   0 Can anyone give explanation of solution 1 of problem D?Whats the idea?