woofwoof321's blog

Need help with a question
By woofwoof321, history, 5 years ago, In English

I asked this from the best coder of my college and he was totally clueless and so am I. This is the question: https://mirror.codeforces.com/problemset/problem/4/A. My approach is to use a segment tree of balanced binary search trees and then apply heavy-light decomposition and binary lifting but it gives wrong answer on test 1.

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

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Same doubt. woofwoof321

→ Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Please sir, help me!

→ Reply
»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

I have also used similar approach and solved the problem. Actually you are doing it wrong you have to just create the equivalent binary tree and apply centroid decomposition on that tree. Final answer will be stored in a sparse table. I hope it helps. woofwoof321

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    nishantwrp I tried your approach but got TLE on test 69. Your approach is quite complicated compared to mine but I can guarantee you that my code didn't have any bugs. I think the time limit in this question is too strict. Can you please give me some tips on how to squeeze this solution in the time limit?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Oh I see. I had problems with that as well, got TLE a few times. I think you forgot to make your centroid decomposition persistent. Also make sure to use a lot of bitsets for speed boost. It will barely fit in the time limit. Happy to help. woofwoof321

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        Wow! Thank you so much for your help nishantwrp!I finally got this question accepted!! Using bitsets certainly helped a lot. I am flabbergasted I couldn't think of it on my own.

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

        Thank you for such a brilliant solution. I am glad that there are coders like you to help us.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        .

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks nishantwrp,this blog was really very helpful.when i first saw the question i barely could think of any approach,even after reading the tuitorial i was unable to understand the solution but your approach was very easy to understand..

        → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

nishantwrp Wow! Your approach is much simpler and way more intuitive than the one given in the editorial. Thanks for sharing such an awesome approach with the rest of the Codeforces community!

→ Reply
»
5 years ago, # |
  Vote: I like it -18 Vote: I do not like it

woofwoof321 , Jimmy Neutron, boy genius

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -33 Vote: I do not like it

Edit: sorry if I have offended anyone, I was just trying to meme it up.

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

what is this? a bullshit blog get 22 upvote?

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I did the following: maintain a cartesian treap for each node in the graph and compute the number of hamiltonian paths after compressing the SCC's. This is a standard technique taught in my hometown of Area 69.

→ Reply