devil_17's blog

By devil_17, 4 years ago, In English

I was solving this problem 219D - Choosing Capital for Treeland. Here's my submission 83899446 which resulted in TLE. My logic is pretty straight forward. dp[par][u] is basically the number of inversions required in the subtree having u as the root after we cut off the edge between u and par. Since N can be upto 1e5, I used an array of maps instead of a 2-D matrix.

Now if we analyze the number of entries in this dp data-structure, it would be of the order of the number of edges i.e. N-1 (actually two times it as for every two neighboring vertices, there can be two entries).

Since the time complexity of any algorithm depends upon the number of subproblems being solved, shouldn't it run in O(N)? Please correct me if I am wrong.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Someone please help me out here.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Notice that the graph you're failing on is a star, specifically one that's centered at the vertex $$$200000$$$. So your algorithm is roughly: for i from $$$1$$$ to $$$199999$$$, enter dfs(i, 200000), visit all the $$$199999$$$ neighbors of $$$200000$$$, and then fill your dp state for $$$dp(i, 200000)$$$.

So your complexity analysis is wrong because it could take up to $$$O(n)$$$ to fill each dp state, and there are $$$O(n)$$$ of them.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ok so if I understood you right, there would be O(N2) dfs(par,u) calls in worst case although the number of entries in dp could still be of the order of N.

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

      I suppose so, yes, and you'll end up revisiting already-computed states a lot.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        So my precomputations won't save me from getting TLE :(

        Anyways, thank you for the clarification buddy.