Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

m0ew's blog

By m0ew, history, 3 months ago, In English,

Hi everyone, This is my first post.I was trying to solve the Road Cutting problem on interviewbit.com.

Here is the problem link — https://www.interviewbit.com/problems/rod-cutting/

I read the editorial as well but i wasn't able to understand it. Detailed approach to this problem is appreciated.

Thanks in advance!

 
 
 
 

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretty standard dp problem. Try reading about optimal binary search tree. The recurrence for that problem is similar to this one.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I think this youtube video might help https://www.youtube.com/watch?v=IRwVmTmN6go

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

    Thanks, I will check it out.

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Struggling with this type of problem for the first time is totally ok. I'm giving you a few resources that can help you. First of all, this problem can be solved easily with dynamic programming, so you have to read and understand dynamic programming properly. This problem falls under a classic dynamic programming section named matrix chain multiplication.

  1. https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/
  2. https://www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/
  3. https://www.youtube.com/watch?v=vgLJZMUfnsU
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank for the list of resources, I will follow them one by one. Also, may I know, in which attempt you solved this question?

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

      It was a very familiar problem to me because I solve many problems on MCM dp ( matrix chain multiplication). So this time no significant time needed (Don't get frustrated seeing this, if you practice enough you will feel the same)

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

        That's Great, I will also keep practicing. :)

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

    I'm also struggling on the same problem. The problem is similar to MCM but we've been asked to return the array of elements instead of final cost. Storing the values(3-D vector) may be one approach to solve the problem. Is there a way to create the path using only cost matrix?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Easier dp. quite similar Uva problem: 10003.