CODEWITHSUNDEEP
algorithmdynamic-programming
myfakeaccount
myfakeaccount

Reputation: 49

Idea of dynamic programming solution

Given natural number N (1 <= N <= 2000), count the number of sets of natural numbers with the sum equal to N, if we know that ratio of any two elements in given set is more than 2 (for any x, y in given set: max(x, y) / min(x, y) >= 2)

I am trying to use given ratio so it would be possible to count the sum using geometry progression formula, but I haven't succeeded yet. Somehow it's necessary to come up with dynamic programming solution, but I have no idea how to come up with a formula

Upvotes: 1

Views: 90

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58251

As Stef suggested in the comments, if you count the number of ways you can make n, using numbers that are at most k, you can calculate this using dynamic programming. For a given n, k, either you use k or you don't: if you do, then you have n-k left, and can use numbers <= k/2, and if you don't, then you still have n, and can use numbers <= k-1. It's very similar to a coin change algorithm, or to a standard algorithm for counting partitions.

With that, here's a program that prints out the values up to n=2000 in the sequence:

N = 2000

A = [[0] * (i+1) for i in range(N+1)]
A[0][0] = 1
for n in range(1, N+1):
    for k in range((n+1)//2, n+1):
        A[n][k] = A[n-k][min(n-k, k//2)] + A[n][k-1]

for i in range(N+1):
    print(i, A[i][i])

It has a couple of optimizations: A[n, k] is the same as A[n, n] for k>n, and A[n, k]=0 when 2k+1 < N (because if you use k, then the largest integer you can get is at most k+k/2+k/4+... <= 2k-1 -- the infinite sum is 2k, but with integer arithmetic you can never achieve this). These two optimizations give a speedup factor of 2 each, compared to computing the whole (n+1)x(n+1) table.

With these two optimizations, and the array-based bottom-up dynamic programming approach, this prints out all the solutions in around 0.5s on my machine.

Upvotes: 2

Related Questions