### apnakaamkar's blog

By apnakaamkar, history, 13 months ago,

• -3

 » 13 months ago, # |   +3 Check this out... https://www.codechef.com/JULY19B/problems/CIRMERGE/It also has a nice editorial.
•  » » 13 months ago, # ^ |   0 thanks
 » 13 months ago, # |   0 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
•  » » 13 months ago, # ^ |   0 thanks
 » 10 months ago, # |   0 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, # |   0
 » 10 months ago, # |   +3 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, # |   0 Is there anything I am missing? If someone can help ? Link : My solution
•  » » 4 weeks ago, # ^ |   0 Update to cost=1e18; and it works.
 » 3 months ago, # |   -8 Why cant we use priority queue here? like https://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/
•  » » 2 months ago, # ^ |   0 Choose two adjacent slimes, and combine them into a new slime. They must be adjacent.
 » 4 weeks ago, # |   0 Am i missing something in this solution: https://atcoder.jp/contests/dp/submissions/22675988
•  » » 4 weeks ago, # ^ |   0 lli i,a, b = sum[endi]-sum[start-1],c=INT_MAX; c can be larger than INT_MAX
 » 4 weeks ago, # |   0 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, # ^ |   0 Yeah, that was the base upon which I built this solution. Thanks for pointing out the error.