mahmoud13's blog

TLE on Test 6, I don't know why is this happening
By mahmoud13, history, 13 months ago, In English

I got TLE on Test 6 for a problem of today's contest 1900C - Anji's Binary Tree. This is one of my submissions: 234472915. Thank you in advance for your time!

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

Comments Comments (19)
| Write comment?
»
13 months ago, # |
  Vote: I like it +19 Vote: I do not like it

u literally go from each node to the root so if u have a chain like this 1 -> 2-> 3-> 4-> 5-> 6 then your algorithm iterate from 6 to 1 and from 5 to 1 and from 4 to 1 and so on which mean u walk : n — 1 + n — 2 + ... + 1 = n * (n — 1) / 2 which can be considered o(n2)

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What about mine, I also got TLE on test 6 even though I made the DP approach. How to improve the time complexity? submission

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      sorry i am not sure i am totally understand what are u trying to do but if u look at the base case of ur recursive function it only stop when only reach the root which i don't think is different than the op solution ( correct me if i am wrong so i didn't even use dfs to solve it)

      → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wrote If condition which states that if the node doesn't have children( its l and r are equale to zero) then I can iterate through its parent..and so on. So I don't know why it is getting TLE.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Test 6 has 75000 such nodes each on path of length 150 000 from the root. So you are using 11250000000 operations which is too much.

      → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But we are only iterating from leaf nodes right, so it won't be O(n2), it will be O(nlogn). We should not get TLE.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why would it be N log N? There can be many leafs with large depth. See the comment above your for clarification.

      → Reply
»
13 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I went from every leaf node to node 1. Which complexity should be O(nlogn) in worst . But I also got tle in test case 6

→ Reply
  • »
    »
    13 months ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    I also made the same assumption at first, but I learned what's going on. It is not true that a binary tree has at most log(n) depth, this is a myth. A balanced binary tree is the data structure that does.

    Look at this example:

    View post on imgur.com
    Each node has at most two children, so it is, by definition, a binary tree, but notice that half the nodes are leafs, from that it's easy to realize that going from each leaf to the root converges to O(n^2)
    → Reply
»
13 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Funny thing is that initially all the trees were either not deep, or did not have many leaves. Around 6 hours before the contest I realized that solutions in O(sum_of_leaf_depths) might be able to pass. That is when I added test 6. Here is the description of it:

There is 1 testcase with N=300 000. Letters are assigned randomly. First I build a long path from vertex 1 to vertex 150 000. So basically 1 — 2 — 3 — ... — 150 000. I randomly decided if child will be right or left. Then at 150 000 I add a balanced binary tree with 150 000 verticies. That makes around 75 000 leafs with depth 150 000. Lastly, I shuffled the vertex numbers (but 1 keeps being the root).

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Need to have good brain to solve a problem, but need a super brain to create one! :) Even that I didn't solve it, but it was an amazing problem. Thanks!

    → Reply
»
13 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Go from each leaf, for a subtree if u already have found a minimal answer, don't look at the path for the right subtree. I got AC doing this.

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hacked. (This will not affect your raiting as it was uphacking)

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      hi sorry but can u try to hack my solution ? i got ac with a gready approach which is similar to dijkastra and multi source bfs but i have doubts maybe its not an optimal solution ( not even sure about this too)

      → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i got AC by pruning the branches, check my code below- https://mirror.codeforces.com/contest/1900/submission/234642669

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also hacked. (Again, this will not affect your raiting)

    Should have added more test data where sum_of_leaf_depths is big, just thought that everyone would run the DFS from the root and not bother doing contstant factor optimizations on O(N^2) solution.

    → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

because you are dump

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The stupidity is not by making mistakes, it is by not learning from them. So for the next time, try to learn, teach, or say nothing and leave!

    → Reply