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

UVa 12442 — Forwarding Emails
Автор determinism, история, 9 лет назад, По-английски

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?

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

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

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

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

    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.

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

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

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

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

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

          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.

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

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

→ Ответить