fakeac's blog

By fakeac, history, 8 years ago, In English

I have written the code to solve this problem, but it gives TLE. I think the complexity of my soln. is O(n). My approach is as follows:

Let dp[from][to] = 1 if all nodes in the subtree of "to" (including "to") are of the same color when we perform dfs from node "from" and "to" is the child of node "from". dp[from][to] = 0, otherwise.

To calculate dp[from][to] we use dfs. Let node "to" have k children, then let's compute dp[to][child] for all children of "to". Then dp[from][to] = 1 if and only if dp[to][child]==1 for all children of "to" and the color[child]==color[to] for all children of "to". Otherwise, dp[from][to]=0;

Now, to compute the final answer, Let's iterate over all "from" nodes, and for each "to" such that "to" is adjacent to "from", if dp[from][to]==1, then final answer="YES", and node="from".

If no such "from" is found then answer="NO";

But this looks like O(n^2) solution. But, if we observe carefully, we see that each "from","to" pair of nodes corresponds to a directed edge going from node "from" to node "to". Since there are exactly n-1 edges, the no. of "from","to" pairs = 2*(n-1).

Here is my submission ----> http://codeforces.me/contest/764/submission/24382711.

NOTE: In this solution instead of passing -> "from","to" to dfs function, I have passed "from","index of 'to' in adj[from]". I have made multiple dfs calls but each call is computed exactly once, since I have made a vis[] array which keeps track of it.

NOTE: If we put a break statement in dfs for loop, we get AC. Lol :P Here is the AC submission. I don't know why it does not get TLE, as the time complexity remains the same, but it is slightly optimized.

Please tell where I am wrong in calculating the time complexity? Thanks in advance.

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by fakeac (previous revision, new revision, compare).

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

TLE occurs for cases where the root has many subtrees.

Consider N=10,000 with the edges being 1-2, 1-3, 1-4 and all the nodes/vertices having different color. In this case, DFS on Node 1 will be called N times, which is fine. The problem then occurs, when the DFS is called on Node 2-node N. Since dp(K, 1) for 2<=k<=N has never been called before, the loop for(i=0;i<adj[to].size();i++) is called for all these nodes, and in this case, adj[to].size() = adj[1].size() = N-1. So the complexity of the program becomes O(N^2).

Adding the break statement in that loop prevents the loop from running N times for every call of dp(k,1)and makes the complexity of the program O(N).

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    dp(K,N) will be called if and only if there is an edge between Node K and Node N. So, this cannot be the reason for TLE. Correct me if I am wrong.

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

      I meant dp(k,1). I edited the comment. There is an edge between k and 1 for 2<=k<=N, so all those DPs will be called, which in turn will call that loop which runs N-1 times.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by fakeac (previous revision, new revision, compare).