Bosscoder's blog

What actually is the difference in both forms of recursion
By Bosscoder, history, 10 months ago, In English

It is not limited to this problem , I have encountered this issue since the first week i started with basic recursion and thought why not do this So in this first submission , i am calculating total value in knapsack like problem and at the end when there is nothing more left , i return the total answer . It gives tle as expected https://www.codechef.com/viewsolution/1010917404 However in the second submission when i try to memoize it , I get a wrong answer https://www.codechef.com/viewsolution/1010917299 At the end when i return 0 in the invalid case and add the value at each layer instead , i get correct answer https://www.codechef.com/viewsolution/1010939008

Why is first submission fine when i don't memoize it .

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

during your dp, you go over 3 variables: w, ptr, and point. however, you only memoize over w and ptr.

in your third submission you don't use point at all, so the memoization is correct.

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    i don't think point is a valid state ? using 3d dp array while storing point also as a state with w /ptr will help in first memoization ? I mean it is actually the maximum point i am storing in i and j of dp array

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

      consider two calls to solve: identical w and ptr, but distinct point. those two calls should produce different result, but they have the same w and ptr, so the memoization can't distinguish them, and would produce the same result.

      here's something your first memoization code fails at:

      n = 2. time = {6,5}. total = {10,1}.

      first w: 9

      call solve(w = 9, ptr = 0, point = 0):
    call solve(w = 9, ptr = 1, point = 0):
        call solve(w = 9, ptr = 2, point = 0) -> returns 0
        call solve(w = 3, ptr = 2, point = 10) -> returns 10
        so we return 10. dp[9][1] = 10.
    call solve(w = 3, ptr = 1, point = 10):
        call solve(w = 3, ptr = 2, point = 10) -> returns 10
        so we return 10. dp[3][1] = 10.
    so we return 10. dp[9][0] = 10.

      second w: 3

      call solve(w = 3, ptr = 0, point = 0):
    call solve(w = 3, ptr = 1, point = 0):
        we have dp[3][1] = 10, so we return 10.
    so we return 10. dp[3][0] = 10.

      ...which is wrong. without the memoization we would've returned 0.

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

        Woah , that clears up a lot . Thanks cheese

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

        but how will call to w=3 and ptr=0 come ?

        → Reply