gop2024's blog

By gop2024, history, 5 years ago, In English

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

Tutorial is loading...

Code

(Idea of the problem B — IbragiMMamilov)

Tutorial is loading...

Code

(Idea of the problem C — usertab34)

Tutorial is loading...

Code

(Idea of the problem D — Denisson)

Tutorial is loading...

Code

(Idea of the problem E — Ralsei)

Tutorial is loading...

Code

  • Vote: I like it
  • +61
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gop2024 (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

The code links are bringing me back to this blog, please fix them :D

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

code link break

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

finally the editorial!

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Such a great second solution for D.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain it further? I didn't get the tutorial.

»
5 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Why I am getting you're not allowed to view the requested page when I click on code of all question.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the links get back to this page??why is it so??

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

could you anyone give me example code of C please?? i can't understand the meaning of editorial.

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Best codeforces explanation I've ever seen. Thanks!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    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)$$$.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain D's solutions with an example ?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain C , i did not understood the editorial

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Why the value of (i+j) doesn't change.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone explain me 1136C — Nastya Is Transposing Matrices, in more detail.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give explanation of solution 1 of problem D?Whats the idea?

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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/52883893

My 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.

»
3 years ago, # |
Rev. 7   Vote: I like it +1 Vote: I do not like it

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: