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

### want_2b_expert's blog

By want_2b_expert, history, 8 months ago, ,

http://codeforces.com/contest/337/problem/A

There are three tags for this problem( Greedy, Graph matching, dp). I have solved it using a greedy technique. Please help me to solve it using dp. Thanks, advanced!!!

N:B You can also suggest the graph matching solution.

•
• -3
•

 » 8 months ago, # |   0 The tutorial itself is a dp approach, isn't it?
•  » » 8 months ago, # ^ |   0 Editorial is given on greedy approach.
 » 8 months ago, # |   -8 Noob here ..I think the problem is simple and a sort followed by a pass over every k-consicutive elements will give you an O(nlogn + n) solution which is enough for the small input size Why are you trying to find a more complicated solution?
•  » » 8 months ago, # ^ |   0 I already solved it but I am practicing DP and trying to solve this one using dp
 » 8 months ago, # |   0 If you want to practice DP, I suggest finding other problems where the desired approach involves DP, instead of overcomplicating a simple greedy problem.
 » 8 months ago, # |   0 You can make a dp(i, k, mnm, mxm). i is the index of the puzzle "you are currently at", k is the remaining number of puzzles you need to take, mnm is the index of the smallest puzzle you took so far, and mxm is the index of the largest one. The value of the dp() is the minimum difference you can achieve, from this state.When (i == n + 1) && (k = 0), dp() is equal to (mxm — mnm). Other "ending states" are equal to infinity. To calculate a single state of dp(), you just need to choose either to "take" or "not to take" the current element. If you take it, your dp(i, k, mnm, mxm) is equal to dp(i + 1, k — 1, new_mnm, new_mxm), where new_mnm = i, if f[mnm] > f[i], and similarly new_mxm = i, if f[mxm] < f[i]. The second case is, if you don't take the element: then dp(i, k, mnm, mxm) will be equal to dp(i + 1, k, mnm, mxm). You get the solution by calling dp(1, m, 0, 0), where (mnm == 0) or (mxm == 0) means that you have not yet taken any puzzles. The complexity is O(n^4), and it has a low constant.
•  » » 8 months ago, # ^ |   -6 Thanks a lot...bro..