bashrc's blog

SPOJ: GHOSTS
By bashrc, 12 years ago, In English

I have been stuck on this problem for very long. I believe we need to simply maintain a dag at all times,and report any edge that will cause a cycle. For a undirected graph,the problem can be solved by using disjoint set data structure. Can we modify this solution to directed graphs? Here is my code which is giving me wrong answer ( Because I initially assumed the graph would be undirected,before realizing my mistake after reading the problem statement again)

EDIT : After reading goo.gl_SsAhv and himanshu's reply I have modified the code. However it is giving TLE. What else I can optimize?

EDIT2: Got AC by some minor modifications (Optimizing by some constant factor) in the above code :) . Thanx all.

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

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

use bitmasks. don't try to add edges between already connected rooms. for example if there already exists edges 1->2, and 2->3, you don't need to add edge 1->3, because it's changes nothing.

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

    But it won't form a loop? So we need to add this edge according to the problem statement

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

      I did not understand your question. try again.
      You don't need to add edge if it froms a loop.

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

        Okay the problem here lies in the insufficient sample case and ambiguity of "decide which of them do not build". I prefer the interpretation of "decide which teleporters that will cause an infinite loop if built in order", seeing from the sentence afterwards, but you can argue "decide which teleporters are not necessary to connect the rooms" and you can be justified too. I haven't solved the problem,so I don't know the correct interpretation; ask someone that have solved it?

        ...After reading the comments, seems like my (and pikachu's) interpretation is correct, since the proposer says "can't build it? Ignore". Only interpretation problem. Blame the proposer to make ambiguous statements then.

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

          i have solved this problem in the way for e in edges {if (ThereIsNoLoopIfWeAddThisEdge(e)) AddEdge(e)}

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

            doubt 1: so,pls tell me why in your first comment 1->2 2->3 1->3

            you are saying that you don't need to add edge 1->3 (clearly its not adding any loop here)

            doubt 2: for test data: 6 7 1 4 1 5 5 3 3 6 6 1 1 5 6 1 problems setter is saying solution to be 6 1 6 1 0 0 why shouldn't it be 6 1 1 5 6 1 0 0 doubt 3: what do you mean by bitmask here.we have 1000 nodes,so i don't think any in-built type will suffice for path existence boolean value. Are you saying to make our own data structure,so what is the problem with a table ???

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

              1) we do need to add edge 1->3 to graph, but it changes nothing, so you can skip call of the real function AddEdgeToGraph to optimise your code perfomance. There will be only O(n) calls of this function.
              2) because algorithm is for e in edges {if (ThereIsNoLoopIfWeAddThisEdge(e)) AddEdge(e)}
              3) you can to implement your own data structure, or use std::bitset, or an array int a[N][N /32]; if (a[x][y >> 5] & (1 << (y & 31))) ...

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

                That's gr8.In a matter of saying we are doing O(n^3) thing in O(n^2) just because of using bitwise operaions....:)

                → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Disjoint set is not needed to solve this problem. An important observation is that you don't need to add an edge a->b if a ~> b i.e. there is already a path from a to b. And if there is a path from b to a then this edge forms cycle. So, the only case when you need to update is when there is no path from b to a and from a to b. And there are O(n) such edges overall. In such a case, a and its ancestors can be updated in worst case O(n^2). To speed things up use bitmasks.

→ Reply