Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

C21's blog

By C21, history, 10 months 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

»
10 months 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).

»
10 months 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).

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

EDIT: Nevermind, I'm dumb.

  • »
    »
    10 months 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.

    • »
      »
      »
      10 months 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.

      • »
        »
        »
        »
        10 months 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.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Any updates