atlasworld's blog

Problem E of yesterdays contest
By atlasworld, history, 6 years ago, In English

Can anyone explain me how binary search will lead to answer.

https://codeforces.net/problemset/problem/1100/E

  • Vote: I like it
  • -19
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i think for each k we are checking whether there is a loop with any edge greater than k . if no then we shift high else if yes then we shif low. please correct if something is missing! what to do after that. how to make top. sort work on cyclic graph?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Just to be clear, in the binary search you have to check if a graph with only the edges that are higher than mid is cyclic or not, if it is cyclic, you do the binary search from mid+1 to right, else, left to mid, because you can decrease the value of k in this case.

    After the binary search, knowing the lowest k possible, you do a topological sort with only the edges higher than k, that way the graph is acyclic.

    With the topological order you go through all the edges smaller or equal to k (the ones you can invert), if it creates a cycle (edge is (u, v) but in the topological sort the v goes before u) you put in the list of edges to invert, if not, ignore it.

    One way to implement this last part is having an array or map indexing each vertex to the respective position on the topological order, that way if vert[v] < vert[u], you know that v goes before u.

    An article about it in geeksforgeeeks: https://www.geeksforgeeks.org/assign-directions-to-edges-so-that-the-directed-graph-remains-acyclic/

    My implementation: https://codeforces.net/contest/1100/submission/48365428

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

      lclpsoz means you are saying that once we find our best k , then its guarantee that any edge value > k will not be reversed otherwise its a contradiction!

      so when we build a new graph with edges > k , we will get an acyclic graph ..

      upto this much i understand ...

      now what i understand after this is : (Ps : please correct me if wrong )

      now since we made out new graph with all edges > k , the graph is acyclic . (the first part what we wanted we get) . we then find the topological ordering of the graph !

      now the source u mentioned of G4G , i am thinking that you are trying to say , the edges with weights <=k , we should make them undirected , now we should assign their directions in such a way that the graph remains acyclic , this can be done by the above mentioned link.

      And then finally print the answer . please tell if something is missing ! !

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yes, it's correct.

        Just be careful to only print the edges (<= k) that the assigned direction is inverted compared with the original direction.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          lclpsoz , but i have a doubt , while making a graph with edges > k , it is possible that every node may be not in our topolozical sort list , some nodes may get eliminated .

          like in the 2nd example edges with weights >3(k) 

          5 7
2 1 5
3 2 3
1 3 3
2 4 1
4 3 5
5 4 1
1 5 3

          are 2--->1 and 4--->3 but they are in different connected components , and 5 is not in our list . what to do in this case .

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            This is why you need to iterate over all nodes in the topological sort, so that no component of your graph get ignored.

            Remember that in a lot of cases (like when the graph have multiple components) there are multiple valid topological orders.

            Here are some valid topological orders for your example:

            • 2 1 4 3 5
            • 4 5 3 2 1
            • 4 2 5 3 1

            Notice that only two "orders" are defined, 2 have to come before 1 and 4 have to come before 3, because of the two edges (2, 1) and (4, 3).

            To be clear, the topological order is a permutation of the vertices respecting the order of the existing edges, in this case, 2 -> 1 and 4 -> 3, so if the graph had no edges and had N vertices, it would have N! valid topological orders.

            I really recommend that you read this article (translated from e-maxx) about topological sort, understand it completely and solve some of the proposed problems before trying to implement 1100E, the logic behind topological sort is very useful in a lot of problems.

            → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The way I see it is that in general you can check if a directed graph contains cycles by removing all nodes that only have incoming edges or only outgoing edges. Then do that procedure over and over again. If you end up with no nodes left then it didn't contain any cycles.

For this problem we can use binary search to figure out which edges we are freely allowed to switch the direction of. Note that in the procedure above these edges basically becomes wildcards so they can mostly be ignored, you just need to note down what direction you want them to be.

→ Reply