mahmoud13's blog

By mahmoud13, history, 7 months ago,

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!

• +5

 » 7 months ago, # |   +19 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)
•  » » 7 months ago, # ^ |   0 What about mine, I also got TLE on test 6 even though I made the DP approach. How to improve the time complexity? submission
•  » » » 7 months ago, # ^ |   +16 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)
•  » » » » 7 months ago, # ^ |   0 Yes! You are correct. I am so careless that my 'DP' did nothing. Finally Accepted after I let the function stop when reaching a dp solution if(dp[u] || par == u) return dp[u];
•  » » 7 months ago, # ^ |   0 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.
•  » » » 7 months ago, # ^ |   +6 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.
•  » » » » 7 months ago, # ^ |   0 OK, I see it now. Thanks!! :)
•  » » 7 months ago, # ^ |   0 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.
•  » » » 7 months ago, # ^ |   0 Why would it be N log N? There can be many leafs with large depth. See the comment above your for clarification.
 » 7 months ago, # | ← Rev. 2 →   0 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
•  » » 7 months ago, # ^ | ← Rev. 3 →   +3 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)
 » 7 months ago, # |   +5 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).
•  » » 7 months ago, # ^ |   0 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!
 » 7 months ago, # |   +3 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.
•  » » 7 months ago, # ^ |   +3 Hacked. (This will not affect your raiting as it was uphacking)
•  » » » 7 months ago, # ^ |   +3 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)
 » 7 months ago, # |   0 i got AC by pruning the branches, check my code below- https://mirror.codeforces.com/contest/1900/submission/234642669
•  » » 7 months ago, # ^ |   0 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.
•  » » » 7 months ago, # ^ |   0 can you hack https://mirror.codeforces.com/contest/1900/submission/234494379 this solution i went from leaf to root 1 .
 » 7 months ago, # |   0 because you are dump
•  » » 7 months ago, # ^ |   0 well you dont solve B what does that make you
•  » » » 7 months ago, # ^ |   0 genius you dump
•  » » 7 months ago, # ^ |   +3 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!
•  » » » 7 months ago, # ^ |   -10 when did i say that's stupidity you dump?