Harry Potter and the Vault of Gringotts

Sherlock221b Tough Cubs' Contest, Dece...

Pre-requisite: Inclusion-Exclusion

The total number of passcodes will be:
(Number of passcodes of length N) + (Number of passcodes of length N+1) + ..... + (Number of passcodes of length K)

We will calculate the number of passcodes of each length separately, and add them to get the final answer.

Let's consider passcodes of length M (N ≤ M ≤ K). Let's define a function C(n,r), which denotes the number of ways you can select r items from a collection of n items (You can read about Combination and how to calculate the formula from here). Since we have the restriction of using each of the N digits at least once in the passcode, using the inclusion exclusion principle, the total number of passcodes of length M will be:

(C(N, N) × NM) - (C(N, N-1) × (N-1)M) + (C(N, N-2) × (N-2)M) - ..... (+ or - sign here) (C(N,1) × 1M)

The idea of using inlcusion-exclusion principle here is this - First, we are counting how many passcodes there are where we don't have the restriction of using each of the digits at least once (which is C(N, N) × NM). But clearly we overcounted and to fix this, we are substracting the number of passcodes there are, where at least one of the digits have been left out (which is C(N, N-1) × (N-1)M). But now we oversubstracted, and to fix this we are adding the number of passcodes there are, where at least two of the digits have been left out (which is C(N, N-2) × (N-2)M) and so on.

We will use the following recurrence formula for calculating C(n,r):

C(n,r) = C(n-1,r) + C(n-1,r-1)

See the implementation below for other details.

C++ code:

#include <bits/stdc++.h>

using namespace std;

long long dp[12][12];
long long mod = 1000000007;


long long f(int n, int r)
{
    if(dp[n][r] != -1) return dp[n][r]; //it's already calculated so we are just returing the value

    //otherwise we will calculate the value using the recurrence formula

    if(n == r) return dp[n][r] = 1; //base case
    if(r == 1) return dp[n][r] = n; //base case

    long long ret = f(n-1,r) + f(n-1,r-1);

    return dp[n][r] = ret; //saving the value to dp[n][r] and returning
}


int main()
{
    long long ans,sum,n,k,x,power[12][102];
    ans = 0;

    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> x;
    
    memset(dp,-1,sizeof(dp)); 
    //dp[i][j] will hold the value of C(i,j)
    //we will call the f(n,r) function to calculate dp[i][j]

    for(int i = 1; i <= 10; i++) power[i][0] = 1; //pre-calculating the power

    for(int i = 1; i <= 10; i++) 
    { 
        for(int j = 1; j <= 100; j++) 
            power[i][j] = (power[i][j-1] * i) % mod; //pre-calculating the power 
    }


    for(int i = n; i <= k; i++) //passcodes of length of n to length k
    {
        sum = 0; //sum will hold the total number of passcodes of length i

        int flag = 0; 
        //flag denotes whether we are adding or substracting
        //flag == 0 denotes we are adding
        //flag == 1 denotes we are substracting


        for(int j = n; j >= 1; j--) //inclusion-exclusion
        {  
            if(!flag) sum += (f(n,j) * power[j][i]) % mod; //inclusion
            else sum -= (f(n,j) * power[j][i]) % mod; //exclusion

            sum %= mod; if(sum < 0) sum += mod;
            //Don't forget to mod and make sum postive if it becomes negative
             
            flag = (flag+1) % 2; //changing the state from inclusion to exclusion or vice versa
        }

        ans += sum; //adding the total number of passcodes of length i
        ans %= mod; //Don't forget to mod
    }

    cout << ans << endl;

    return 0;
}

Statistics

43% Solution Ratio
ruhanhabib39Earliest, Dec '16
RobbinFastest, 0.0s
Tarik.amtolyLightest, 131 kB
ruhanhabib39Shortest, 594B
Toph uses cookies. By continuing you agree to our Cookie Policy.