Please provide few hints to solve K FIBONACCHI problem? (link of the problem in description )

general
1

problem link:- https://www.codechef.com/problems/KFIB

please give some hint to solve this problem

2

there will be exactly k 1’s in the solution. so first, create a list list_ = [1]*k
Then, append sum(list_[i:]) in list_ for i in range(n - k)

1 Like
3

Here’s my trial code and submission link

n,k=map(int,input().split())
l=[1]*k
for i in range(n-k):
    l.append(sum(l[i:])%1000000007)
print(l[-1])
1 Like
4

The Problem in Short:
Given 2 integers N and K, we need to find the Nth term modulo 109+7 for the series:

T(N, K) = 1 if N <= K and T(N, K) = T(N-1, K) + T(N-2, K) + T(N-3, K) … + T(N-K, K) if N > K

Some Observations

  1. K does not change in the relation given in the question, implying it to be a static parameter.
  2. If the given N<=K, we can simply return 1 as the answer.
  3. If the given N>K, the first K terms of the series would be 1.

We can make an array where series[i] will store the ith term of the series.
So with all these basic observations, we can loop from K+1 till N(both inclusive).
For each i from K+1 till N, the ith term can be found out by adding all the terms from i-1 to i-K (as specified in the question).
Then perform mod operations as specified in the question.
The answer would be series[N]

For complete implementation, this is the link to my code.
Submission Link

1 Like
5

quite well explained. I used a similar approach. The difference in the language gives a difference of 132 lines of code :flushed:

6

and also 17 times slower.

1 Like
7

Not really 132 lines. I’ve used C++ and my code has a template with some functions, some #define type definitions, and a lot more.
The core logic is written in the main function and is not that big…

8

If the given N>K, the first K terms of the series would be 1.
can you explain this
for example if i take (10,2)
then (10,2)=(9,2)+(8,2)
how can (9,2) and (8,2) equals 1

9

You have interpreted the statement in the wrong way.
(10,2) is the 10th term of the series.
(1,2) will be the 1st term
(2,2) will be the 2nd term
In both (1,2) and (2,2) we have N<=K

I hope your doubt was cleared :grinning: