Блог пользователя hexor

Some Problem for DAG
Автор hexor, 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

    → Ответить
»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

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.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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? :)

        → Ответить
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
10 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить