WRTNK-Editorial

PROBLEM LINK:

Practice
Chef Dynasty

Editorialist & Author: Aditi Sahu
Tester : Krish Rustagi

DIFFICULTY:

EASY

PREREQUISITES:

DP, MATHS

PROBLEM:

There are T test cases. In each case, you are given N and K (where N is total length and K is the ominous number) .You have to find total arrangements of tanks except K number of Tanks.

EXPLANATION:

Let’s have a look on the pattern it follows:
If we consider one more arrangement with no tanks then:
for N=2 total possible arrangements are 3(- - , - *, *-)
for N=3 total possible arrangements are 5(- - - , *- -, - * -, - - *, * - *)
for N=4 total possible arrangements are 8( - - - - , * - - - , - * - - , - - * -, - - - *, * - * -, * - - * , - * - *)
for N=5 total possible arrangements are 13
From above we observed that it is a fibonacci series.
So to get total arrangements we will find its fibonacci number and subtract 1 for no tanks.

Fibonacci: A need of precomputation is requried ,first calculate and store in some array so that we can later use it for our purpose.


f =[]*1000000

f[1]=2

f[2]=3

fib():

For i in range(3,1000000):

F[i] = f[i-1]+f[i-2]

To Calculate nCr: An efficient approach will be to reduce the better approach to an efficient one by precomputing the inverse of factorials. Precompute inverse of factorial in O(n) time and then queries can be answered in O(1) time. Inverse of 1 to N natural numbers can be computed in O(n) time using the Modular multiplicative inverse. Using recursive definition of factorial, the following can be written:


n! = n * (n-1) !

taking inverse on both side

inverse( n! ) = inverse( n ) * inverse( (n-1)! )

To find how many arrangements are possible with K tanks:
To find arrangements with k tanks let’s take example where N=4 and K=2

Let’s position the first tank at 1st position now possible position for 2nd tank is at 3rd or at 4th

*-*-

*--*

So total possible position where tanks can occupy there space is =3

And we want only two tanks in total n(n=4) length.

Total arrangement will be=3C2
arrangements with K tanks: (n-k+1)Ck

Answer: Total-(k tanks arrangements)

SOLUTIONS:

Setter's Solution(C++)
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
const ll M = 1e9 + 7;
vector<ll> f(100003);
const int N = 100003;
ll t;
unsigned long long power(unsigned long long x,
                                  int y, int p)
{
    unsigned long long res = 1; 

    x = x % p; 

    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1; 
        x = (x * x) % p;
    }
    return res;
}

unsigned long long modInverse(unsigned long long n,
                                            int p)
{
    return power(n, p - 2, p);
}

unsigned long long nCrModPFermat(unsigned long long n,
                                 int r, int p)
{
    if (n < r)
        return 0;
    if (r == 0)
        return 1;

    unsigned long long fac[n + 1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;

    return (fac[n] * modInverse(fac[r], p) % p
            * modInverse(fac[n - r], p) % p)
           % p;
}
void fib()
{

    f[0] = 0;
    f[1] = 1;

    for(ll i = 2; i <= N; i++)
    {
       f[i] = ((f[i - 1] % M) + (f[i - 2] % M)) % M;
    }
}

ll factorialNumInverse[N + 1];

ll naturalNumInverse[N + 1];

ll fact[N + 1];

void InverseofNumber(ll p)
{
    naturalNumInverse[0] = naturalNumInverse[1] = 1;
    for (int i = 2; i <= N; i++)
        naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p / i) % p;
}

void InverseofFactorial(ll p)
{
    factorialNumInverse[0] = factorialNumInverse[1] = 1;

    for (int i = 2; i <= N; i++)
        factorialNumInverse[i] = (naturalNumInverse[i] * factorialNumInverse[i - 1]) % p;
}

void factorial(ll p)
{
    fact[0] = 1;

    for (int i = 1; i <= N; i++) {
        fact[i] = (fact[i - 1] * i) % p;
    }
}

ll Binomial(ll N, ll R, ll p)
{
    ll ans = ((fact[N] * factorialNumInverse[R])
              % p * factorialNumInverse[N - R])
             % p;
    return ans;
}

int mod(ll num, ll modValue)
{
    return ( modValue- ( (0-num) % modValue) );
}
void solve()
{
    ll n, k;
    cin >> n >> k;
    ll ans;
    ans = (f[n+2] - 1) % M;
    ll x = n - k + 1;
    ll sub = Binomial(x, k, M);
    ans = (ans - sub);
    if(ans < 0)
    {
        ans = mod(ans, M);
    }
    cout<< ans << "\n";
}
int main()
{
    fast
    fib();
    InverseofNumber(M);
    InverseofFactorial(M);
    factorial(M);

   cin >> t;
   while(t--)
   {
       solve();
   }
}
Tester’s Solution(Python)
N = 1000000
 
factorialNumInverse = [None] * (N + 1)
 
naturalNumInverse = [None] * (N + 1)
 
fact = [None] * (N + 1)
 
def InverseofNumber(p):
    naturalNumInverse[0] = naturalNumInverse[1] = 1
    for i in range(2, N + 1, 1):
        naturalNumInverse[i] = (naturalNumInverse[p % i] *
                                   (p - int(p / i)) % p)
 
def InverseofFactorial(p):
    factorialNumInverse[0] = factorialNumInverse[1] = 1
 
    for i in range(2, N + 1, 1):
        factorialNumInverse[i] = (naturalNumInverse[i] *
                                  factorialNumInverse[i - 1]) % p
 
def factorial(p):
    fact[0] = 1
 
    for i in range(1, N + 1):
        fact[i] = (fact[i - 1] * i) % p
 
def Binomial(N, R, p):
    ans = ((fact[N] * factorialNumInverse[R])% p *
                      factorialNumInverse[N - R])% p
    return ans
 
p = 1000000007
fib = [0, 1]
for i in range(2, 1000000):
	fib.append((fib[i - 1] % p + fib[i - 2] % p) % p)
InverseofNumber(p)
InverseofFactorial(p)
factorial(p)
 
for _ in range(int(input())):
 
	n, k = map(int, input().split())
	ans = fib[n + 2] - 1
	sub = Binomial(n - k + 1, k, p)
	ans -= sub
	if(ans < 0):
		ans = (p - (-ans) % p) % p
	print(ans)
5 Likes

It would be great if you could expand the explanation a bit and talk about how to mathematically derive that the given sequence is a fibonacci series rather than looking into the pattern and also a little bit more context on the arrangement with k tanks.

Thanks for your concern

2 Likes

How to derive the given sequence?
No need to think in terms of Fibonacci. But usually, there are 2 ways to handle a sequence. First way is to make a combinatorial argument and get a closed form solution. The 2nd way is to write a recurrence relation. If you spend a little time looking at the problem, you might be able to come up with a recurrence relation (by trying to express the number of configurations for a problem of size n in terms of smaller problems).

For a problem of size n, either the first element is a tank or it is not a tank

  1. If it is a tank, then 2nd one can not be a tank. And from the 3rd element onwards it’s a problem of size (n-2).
  2. If it’s not a tank, then the remaining is a problem of size (n-1).

So We can write T(n) = T(n-1) + T(n-2).

How you express it is not important. For example, if you don’t want to count the empty sets, then you will come up with T(n) = T(n-1) + T(n-2) + 1. (of course Both these expressions have different meanings and must be handled appropriately)

In either case, once you have a recurrence relation, you can easily compute f(n) for all N in range (1,Y) n O(Y).

How many arrangements contain k tanks?

There are many ways to look at this problem. One standard way (might be new if you have never seen it) is using the stars and bars technique (Stars and bars - Competitive Programming Algorithms). It might not be intuitive and someone may have a better way, but I am explaining how I solved it.
For K tanks, the base case (the simplest case) contains 2K-1 slots. In this case, every odd element is a tank and there is only 1 way to fill K tanks in 2K-1 slots. For any N>2K-1, we can build on top of this configuration. There are N- (2K-1) = Z=N-2K+1 more slots remaining which we can insert anywhere between the tanks. There are R=K+1 different areas for slot insertion in between the tanks (K-1 between and 2 on the corners). Now using stars and bars, we can insert this in {Z+R-1} \choose{R-1} ways. Simplify this into {N-K+1} \choose {K} .

Another way to look at this is the number of integer solutions of X_{1} + X_{2} + ... + X_{K+1} = N where X_{1} and X_{K+1} are non negative and others are positive.
Can subtract K-1 from right side and get the equation with all variables non negative, and then use formula for solutions to integer equation.

6 Likes