determinism's blog

UVa 12442 — Forwarding Emails
By determinism, history, 9 years ago, In English

I was trying solve this problem and I've thought of O(T * N) solution that uses Tarjan+DP. I thought O(T * N2) wouldn't work because . But solutions on this blog and this blog seem to me as O(T * N2).

How do they get accepted? Is it just because of weak test cases, or is there something else I'm missing here?

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

Comments Comments (9)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Their dfs does not visit a vertex twice, that's why it's O(N) not O(N2) nvm

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

    It can visit a vertex twice. These codes don't directly use previously memorized values because it's not necessarily a DAG. It just doesn't call dfs for ith node if it's traversed in the loop in main function. For example, if we have a graph like this, every vertex is visited more than once.

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

      Yeah, you are right. Apparently test data is weak.

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

        Is there any other O(T * N) solution other than Tarjan+DP?

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

          I think this is mostly the same as your solution, but here is mine:

          Notice that the graph consists of directed cycles along with trees (directed up towards the root) where the root is contained in one of the directed cycles. These cycles and trees can be found via DFS. Each vertex in a cycle of length k will forward emails to k-1 vertices. Each vertex in a tree (except the root) whose parent forwards emails to k vertices will forward emails to k+1 vertices. These values can be propagated down the trees with any tree traversal. Then a linear search for the vertex that forwards the maximum number of emails will give us the answer.

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

We can do that in O(N) time by finding SCC's(strongly connected components). here is the code

→ Reply