determinism's blog

By determinism, history, 3 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  

»
3 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

  • »
    »
    3 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.

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

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

      • »
        »
        »
        »
        3 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?

        • »
          »
          »
          »
          »
          3 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.

          • »
            »
            »
            »
            »
            »
            9 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            can you please explain more the part of parent forward to k vertices

            and root forward to k+1 vertices does you count the "clan chieftain" as a parent ?

            and the first node in the cyclic or what we assume that it`s as a root ? and if that is right how could root it forward to k+1 which (k+1) could you apply your saying on the first example in the problem please thanks in advance