Count the ways to complete N jobs in sequence

Count the total number of ways to complete N jobs (1 to N), each job having Ui units (1 <= i <= N) such that all jobs are completed sequentially (i.e J_i < J_i+1) and each unit is completed in one time slot. Since the ways can be very large, output the answer modulo p = 10⁹ + 7.

Examples :

Input : N = 2, U = [2, 2]
Output : 3
Explanation :
Possible ways are [ 'J1 J1 J2 J2' , 'J1 J2 J1 J2', 'J2 J1 J1 J2' ].
Note the way 'J1 J2 J2 J1' is invalid because J2 is completed
(all 2 units done) before J1
which violates the condition that Ji is completed before Ji+1.

Input : N = 3 , U = [2, 2, 3]
Output : 45

Approach :

We are going to use Dynamic Programming and Combinatorics to solve this problem.

Key Observations :

• Consider the second testcase. U = [2 , 2, 3]. So total we have 7 slots _ _ _ _ _ _ _ to fill in total.
• Now consider only Job 1. We have only 1 way to complete J1 i.e, J1 J1 .
• Now consider Job 2. The most basic arrangement can be J1 J1 J2 J2. Now observe that for J2 to be completed at the end, the last slot HAS to occupied by J2. So we fix the last slot ans we get (J1 J1) J2 J2.
• Now the J2 remaining have 3 places to go in -> _ J1 _ J1 _ J2. So ans = prev_ans * 3 C 1 = 1 * 3 = 3 ways
• Now J3 comes in. The most basic arrangement is (J1 J1 J2 J2) J3 J3 J3. The last slot has to be J3. 
• Now observe that the remaining two J3s have 7-1 = 6 places to go in _(J1_J1_J2_J2) _ _ J3. So ans = prev_ans * 6 C 2 = 3 * 15 = 45

 Hence we can formulate a DP approach.

1 . Optimal Substructure :

  We can see that answer to the 3rd job can be obtained from the previous 2 jobs.

2 . Overlapping SubProblems :

We can see that dp[i] depends on the answer dp[i-1].

Basic Recurrence :

dp[i] = dp[i - 1] * ((total slots till i) - 1) C (slots at ith position - 1)

Modulo Optimisation :

Since we need the answer modulo p = 1e9 + 7. We need to use Compute nCr % p | Set 3 (Using Fermat Little Theorem)

We also assume basic knowledge of Binary Exponentiation.

dp[i] = (dp[i - 1] * ((total slots till i) - 1) C (slots at ith position - 1))  % p

Implementation :

// C++ program to count total number of ways to complete N jobs,
// each job having Ui units such that all jobs are completed Sequentially.
#include <bits/stdc++.h>
using namespace std;

#define int long long int
const int p = 1e9 + 7;   // modulo p
const int lim = 1e6 + 7; // maximum value of n
int fac[lim];

// preprocess n! mod p
void preprocess() {
  fac[0] = 1;
  for (int i = 1; i < lim; i++) {
    fac[i] = (fac[i - 1] * i) % p;
  }
}

// Standard Fast Binary Exponentiation
int power(int a, int b, int m) {
  a = a % m;
  int ans = 1;
  while (b) {
    if (b & 1)
      ans = (ans * a) % m;
    a = (a * a) % m;
    b /= 2;
  }

  return ans;
}

// Calculate a^-1 mod p = a^(p - 2) mod m using Fermat's little theorem
int inverse(int a, int p) { return power(a, p - 2, p); }

// Function to calculate ncr modulo p
// using Fermat's theorem and multiplicative modulo inverse
int ncrmod(int n, int r, int p) {
  return (fac[n] % p * inverse(fac[r], p) % p * inverse(fac[n - r], p) % p) % p;
}

void solve(int n, const vector<int> &arr) {
  preprocess(); // preprocess factorials in O(lim) time
  vector<int> dp(n);

  dp[0] = 1;          // base case of only Job 1
  int slots = arr[0]; // slots till current job
  for (int i = 1; i < n; i++) {
    slots += arr[i]; // add slots of this job

    // dp formula
    dp[i] = (dp[i - 1] % p * ncrmod(slots - 1, arr[i] - 1, p)) % p;
  }

  cout << "The total no of ways are: " << dp[n - 1] << endl;
}

signed main() {

  int N = 3;
  vector<int> arr = {2, 2, 3};
  solve(N, arr);

  return 0;
}

Time Complexity : O(N log P)

Explanation : For each of the N jobs, we have to caclulate the binomial coefficient which is basically modular exponentiation and takes O(log P) for every time it is invoked. Hence total time O(N * log P) = O(N log P)