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!
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | nor | 157 |
| 4 | atcoder_official | 156 |
| 4 | cry | 156 |
| 6 | -is-this-fft- | 155 |
| 7 | maroonrk | 154 |
| 8 | adamant | 153 |
| 9 | Um_nik | 151 |
| 10 | djm03178 | 146 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 01.09.2024 01:38:15 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
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)
What about mine, I also got TLE on test 6 even though I made the DP approach. How to improve the time complexity? submission
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)
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];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.
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.
OK, I see it now. Thanks!! :)
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.
Why would it be N log N? There can be many leafs with large depth. See the comment above your for clarification.
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
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:
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 toO(n^2)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).
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!
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.
Hacked. (This will not affect your raiting as it was uphacking)
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)
i got AC by pruning the branches, check my code below- https://mirror.codeforces.com/contest/1900/submission/234642669
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.
can you hack https://mirror.codeforces.com/contest/1900/submission/234494379 this solution i went from leaf to root 1 .
because you are dump
well you dont solve B what does that make you
genius you dump
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!
when did i say that's stupidity you dump?