Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

C21's blog

By C21, history, 5 weeks ago, In English,

Problem: https://www.codechef.com/problems/HLD/

I was only able to come up with the simple O(n^2) DP. I went through the editorial but didn't fully understand it.

Can someone share their ideas/approaches.

Any help would be appreciated.

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by C21 (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by C21 (previous revision, new revision, compare).

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

EDIT: Nevermind, I'm dumb.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain it in a bit more detail. Why log N times and how it's useful.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Nevermind, you're right. I'll get back to you if I'm able to think about the answer.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think you have misread the problem. We have to mark the edges heavy/light to get the minimum cost.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Any updates