apnakaamkar's blog

N-Slimes(Atcoder)
By apnakaamkar, history, 4 years ago, In English

Could anyone please exlain me how to solve this dp problem? Link:https://atcoder.jp/contests/dp/tasks/dp_n Help?

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Check this out... https://www.codechef.com/JULY19B/problems/CIRMERGE/

It also has a nice editorial.

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

Its easier to understand the recurrence relation from a solution done made with recursion (and memoisation), so here you go — https://atcoder.jp/contests/dp/submissions/15834404

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

    please can you tell me what's the problem with greedy solution in this problem? when i use this solution it give me WA

    the greedy solution based on at each move we select 2 adjacent elements with the lowest sum, and merge them until one element remaining.

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

      In greedy approach, we are making sure that cost incurred in each of the progressive step is minimum but this may not result in minimum total cost incurred.

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

this video by Errichto helped me a lot while solving the dp atcoder contest : https://www.youtube.com/watch?v=FAQxdm0bTaw&t=8731s

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

    hint for someone who wants to try: dp[i][j] state refers to the minimum total cost of combining interval [i,j] into one vertex. answer will be dp[0][n-1]

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

Is there anything I am missing? If someone can help ?

Link : My solution

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

    Update to cost=1e18; and it works.

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

Am i missing something in this solution: https://atcoder.jp/contests/dp/submissions/22675988

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

    lli i,a, b = sum[endi]-sum[start-1],c=INT_MAX; c can be larger than INT_MAX

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

If you want to learn the concept behind this problem then go through Matrix chain multiplication DP, it is a very famous DP problem and has clear explanations(you can check Cormen or any online articles). This N-slimes problem is very similar to that but instead of multiplication, we do addition.

→ Reply