apnakaamkar's blog

By apnakaamkar, history, 13 months 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

»
13 months 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.

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

build a 2d matrix of size n x n. start from bottom like what if you had only one element in the array, then solve for two elements , then three then you will eventually develop a recurrence relations by just manually solving it. just to confirm you will only have to fill the half dp table when it is cut diagonally , step 1: fill 1,1 2,2 3,3 4,4 till n,n step 2 : fill 1,2 2,3 3,4 till n-1,n step3 while filling 1,3 and so on

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

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

»
9 months 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

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

    Update to cost=1e18; and it works.

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

Why cant we use priority queue here? like https://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/

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

    Choose two adjacent slimes, and combine them into a new slime. They must be adjacent.

»
4 weeks 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

  • »
    »
    4 weeks 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

»
4 weeks 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.

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

    Yeah, that was the base upon which I built this solution. Thanks for pointing out the error.