tirupati's blog

CodeForces 247 div2C
By tirupati, history, 9 years ago, In English

This is my first blog post here and also this is the first dp problem I was able to solve by myself. So, I thought I should celebrate it by publishing a blog entry. Here it goes..., We have to find the sum of the numbers(range[1...k]) such that their sum forms n. Also it's given that there must be at least one entry with value >=d. So this is equivalent to...

Required Number of Paths = (total number of paths which sum to n using range[1...k]) - (total number of paths which sum to n using range[1...d-1])

Each of the two subproblems on the R.H.S can be individually solved using dp. You can see the solution here

PS: Feel free to suggest improvements or show up bugs :D Thank You..,

Update 1: From Michael Kirsche's explanation I have improved my implementation which can be found here. Thank You mkirsche

Tags dp
  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DP can be a really hard concept to wrap your head around, so first of all congrats on solving it. :) Also, I do have one suggestion for improvement on this problem for making it run faster. In your DP, the first dimension seems to be the depth in the tree, but this is not actually important. You can create a one-dimensional such that dp[i] is the number of paths with sum of i, regardless of depth. Then, dp[0] is 1, and each of the other values can be computed according to the following loop, trying all possible edges to be the last edge on the path: for(j = 1; j<= min(i, k); j++) dp[i] += dp[i-j]; Then the runtime is O(n*k) instead of O(n*n*k). Not necessary for the given bounds of 100 for n and k, but if the bounds were as high as 5000 your approach would be too slow.

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

do you know there's pure math solution for this problem? "Total number of paths which sum to n using range[1...k]" equals to n-th Fibonacci K-step number. Can you prove it?

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

    I am sincerely unaware of that. Can you give me references, also can you explain what is an "nth Fibonacci K-step number" or some references related to that too..,

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

      Fibonacci 2-step number: Fi = Fi - 1 + Fi - 2
      Fibonacci 3-step number: Fi = Fi - 1 + Fi - 2 + Fi - 3
      Fibonacci N-step number: Fi = Fi - 1 + Fi - 2 + ... + Fi - n

      someone's code: 6684479

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

        This is a simple DP.
        Lets say dp[N] = "Total number of paths which sum to n using range[1...k]".
        So if we can pich [1...k] each step => dp[N] = dp[N-1] + dp[N- 2] + dp[N-...] + dp[N-k].
        So this is actually (as you call it) — Fibonacci k-step number.

        Also consider Fi = i-th Fibonacci k-step number

        Fi = Fi-1 + Fi-2 ... + Fi-k and Fi+1 = Fi + Fi-1 + ... + Fi-k+1

        Lets subtract Fi+1 by Fi

        => Fi+1 - Fi = Fi - Fi-k => Fi+1 = (2 * Fi) - (Fi-k) for every "i" and "k".

        So for every N-th Fibonacci K-step number: Fi = 2 * Fi - Fi-k-1

        → Reply