want_2b_expert's blog

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

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.

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

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

The tutorial itself is a dp approach, isn't it?

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

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?

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

    I already solved it but I am practicing DP and trying to solve this one using dp

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

If you want to practice DP, I suggest finding other problems where the desired approach involves DP, instead of overcomplicating a simple greedy problem.

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

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.