CODEWITHSUNDEEP
algorithm
Nobody
Nobody

Reputation: 77

Is there any algorithm to improve my code?

SEAWEED

You're given k days and n seaweed.

(1 ≤ n ≤ 1000, 1 ≤ k ≤ 10^17)

At the very first day, you have n seaweed at level 1

The next day, that n seaweed will reproduce, every n seaweed at level i will reproduce n*i seaweed at level 1, these level 1 seaweed will start reproduce after the day end.

Every seaweed at level i will become level i+1.

After k days, return the total number of seaweed (im very sorry, if you dont understand the problem, i'm very bad at translating)

EXAMPLE:

INPUT : 3 3

OUTPUT : 39

EXPLANATION:

DAY 0 : 3 SEAWEED

DAY 1 : 3 Level 1 , 3 Level 2 ...

Total seaweed at day 1 = 6

DAY 2 : 3 + 3 * 2 Level 1 (there are 3 level 1 and 3 level 2, so 3 * 1 + 3 * 2 = 9), 3 Level 2 , 3 Level 3

Total seaweed at day 2 = 15

DAY 3: 9 + 3 * 2 + 3 * 3 = 24 (at day 2 there is 9 level 1, 3 level 2 and 3 level 3) Level 1 , 3 + 3*2 = 9 Level 2 , 3 Level 3 , 3 Level 4

Total seaweed at day 3 = 39

TOTAL OF SEAWEED : 39

Can you help me find any algorithm for this problem? and shorten my problem into one sentence

My code doesn't seem so fast

Here's my code for the problem:

def solver(n,k):
    storage = [n]
    for i in range(k):
        reproduction = 0
        for j in range(len(storage)):
            reproduction += storage[j]*(j+1)
        storage = [reproduction] + storage
    return sum(storage)%(10**9+7)

Some more test case:

INPUT : n = 4, k = 3

OUTPUT : 52

INPUT : n = 5, k = 5

OUTPUT : 445

Upvotes: 1

Views: 92

Answers (2)

Beta
Beta

Reputation: 99144

The first insight is that the function is linear in n. You can imagine each of the n initial seaweed plants as a separate lineage; their descendants do not interfere with each other, so if you double n, you double the answer. So if you solve f(1, k) then you can get f(n, k) simply by multiplying by n. You could -- by some slow calculation -- make a table of values of f(1, k) for many values of k, then compute f(n, k) for any (n, k) that is requested.

The second insight is to work out e.g. f(1, 5) on paper and see the patterns in the numbers. If you are a mathematician at heart, you will recognise some terms from the Fibonacci sequence. (If you are really a mathematician at heart, you will prove the pattern.) Then you can write the formula for f(n, k), and some fast code to calculate it.

Upvotes: 0

MBo
MBo

Reputation: 80232

Solution might be expressed through Fibonacci numbers:

solver(n,k) = n*Fib(2*k+1)

and Fibonacci numbers for extremely high k values (using modulo 10**9+7) might be calculated with matrix exponentiation method here

Upvotes: 2

Related Questions