Блог пользователя mahmoud13

TLE on Test 6, I don't know why is this happening
Автор mahmoud13, история, 12 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
12 месяцев назад, # |
  Проголосовать: нравится +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)

→ Ответить
  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 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

    → Ответить
    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится +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)

      → Ответить
      • »
        »
        »
        »
        12 месяцев назад, # ^ |
          Проголосовать: нравится 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];

        → Ответить
  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить
    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится +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.

      → Ответить
  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 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.

    → Ответить
    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
»
12 месяцев назад, # |
← 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

→ Ответить
  • »
    »
    12 месяцев назад, # ^ |
    ← 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)
    → Ответить
»
12 месяцев назад, # |
  Проголосовать: нравится +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).

→ Ответить
  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 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!

    → Ответить
»
12 месяцев назад, # |
  Проголосовать: нравится +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.

→ Ответить
  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится +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)

      → Ответить
»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

because you are dump

→ Ответить