Madara__Uchiha__'s blog

Help needed in this problem
By Madara__Uchiha__, history, 4 years ago, In English

Problem:- https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/the-chocolate-boy-738c799b/

My sub:- https://pastebin.com/E1hqm56H

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

It's pretty much Knapsack DP.

I will mention the dynamics:

$$$dp_{i,j,0}\ =maximum \ amount \ paid\ for\ first\ i\ elements\ with\ sweetness\ <=j\ and\ operation\ is not\ used.$$$

$$$dp_{i,j,1}\ =maximum \ amount \ paid\ for\ first\ i\ elements\ with\ sweetness\ <=j\ and\ operation\ is\ used.$$$

$$$Transitions\ are\ similar\ to\ Knapsack\ DP.$$$

Your answer will be $$$max(dp[n][m][0]\ ,\ dp[n][m][1])$$$

My solution: https://ideone.com/NgqsT4

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

    Brother please can you clear my doubt I use 3 dp states dp[n][m][flag] The code passed the test cases but when I was using 2 dp states dp[n][m] and was updating the value for flag . Then it was failing on few cases why is so???

    This is my previous code:- https://pastebin.com/E1hqm56H

    This is new code:- https://pastebin.com/xEqn2Uq8

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

      The problem is with the statement 

      if(dp[n][m]!=-1)

   return dp[n][m];

      , since we don't know if flag was true or false, in the returned state,so it may lead to overcount.

      → Reply