hexor's blog

Some Problem for DAG
By hexor, 10 years ago, In English

I want the ask aquestion. "You have a DAG(directed acyclic graph) which is the contain n(1<=n<=300.000) nod. How many nodes can you go if you will start nod i(1<=i<=n). You must find answer for all nod."

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

»
10 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Problem statement is not clear. Do you have a link to the original problem?

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

    It seems to be "for each i, count vertices that can be reached from vertex i", which is at least O(N2). Whoops.

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +9 Vote: I do not like it

we can use dfs like idea i think. For every node there will be a mask which will indicate which nodes are reachable from this node. To calculate the mask of a node 'U' we can recursively calculate the info (mask) for the child nodes of 'U'. And to find the mask of U we can use bitwise OR operation.

The problem is as total node is 300000 we have to use an array of integers to define the mask. if we use int then the mask array will be of size 300000/32 = 9375. if we use long long then the mask array will be of size 300000/64 = 4688. is this a Online judge problem? may be the limit is not that big. can you provide the link if it is an online judge problem.

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

    Then I guess ML for this problem is 10Gb.

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

    Ooow. it's very cool question and solution. But this solution isn't fast.

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

Your question is exactly the same with http://www.spoj.com/problems/DAGCNT2/.

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

    And does this problem actually have a better solution than O(N * M)? Or is it just about constant optimizations?

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

      Someone told me they had proved the lower bound is OmegaO(|V||E|). But I didn't read the paper.

      Actually, the problem setter said that his solution was based on std::bitset.

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

        Thank you for answering, I was pondering on that question for a while. It does seem intuitive that you can't do better than that, a proof does seem complicated indeed though. Could you please link to the paper if you come across it? :)

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

          The "someone" just told me. :) I didn't have the exact paper. Sorry about that.

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

    In the problem on SPOJ, n=20000, very smaller than n in this problem. Time limit DAGCNT2 is 26s, and memory limit is 256MB. If we use the same implementation to submit on above problem. TL should be 390s (6.5 minutes) and ML should be 3840MB (3.8GB).

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

I think you can use a DP approach for this problem. I should be O( |V| + |E| ).

For each node that hasn't been calculate you run a dfs( u ). Where dfs(u) will return how many nodes you can reach from there and for each of its children you will run a dfs( ) that will save the number of nodes that each of its children can reach.

Well, this is my idea. Sorry if i have some grammar or spelling mistakes. I am trying to fix it.

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

    This algorithm will not run correctly. for example we have four nodes. first node have two children which are second and third node. Second and third node have a child which is fourth node. fourth node haven't got a child. we called dfs( 1 ).

    dfs(1) = dfs(2)+dfs(3)+1.

    dfs(2) = dfs(4)+1 = 2.

    dfs(3) = dfs(4)+1 = 2.

    dfs(1) = 5.

    for first node we count the fourth node twice. normally dfs(1)=4 but we find dfs(1)=5

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

      So, I think that a solution could be that if you actually reach that node you don't have to count it.

      In this example you will have:

      dfs(1) = dfs(2)+dfs(3)+1.
dfs(2) = dfs(4)+1 = 1 + 1 = 2.
dfs(3) = dfs(4)+1 = 0 + 1 = 1. (because you reach the node before)
dfs(1) = 4.

      Well, I think that should work.

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

Someone told me a randomized algorithm can run really fast, and for at least 90% of n, its answers' relative error is at most 10%. However, I could not remember the algorithm......

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

Process vertices in inverse topological order.

For each vertex the result is 1 + sum of results for children

O(N + M) or I missed something?

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

    for 4 node

    roads

    1 -> 2

    1 -> 3

    2 -> 4

    3 -> 4

    u counting two times node 4 for calculate node 1

    → Reply