M72BTS- Editorial

dynamic-programming
easy-medium
maths

#1

PROBLEM LINK:

Practice
Contest

Author: nmalviya1929
Editorialist: nmalviya1929

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

DP

PROBLEM:

Find the number of ways to divide n days into groups such that each group have at least k days.

QUICK EXPLANATION:

Let dp* represent answer for i days. Then dp[n]=\sum_{i=0}^{n-k} dp*.

EXPLANATION:

Let dp* represent answer for i days.
If we’re solving for n days, in the last group we can keep days from k to n.If we select k days in last group then number of ways is dp[n-k] , if we select k+1 , then number of ways is dp[n-k-1] ans so on. Therefore dp[n]=\sum_{i=0}^{n-k} dp*.

dp[0]=1;
	for( i=1 to n) {
		dp*=0;
		for (j= i-k to 0) {
			dp*+=dp[j];
			dp*%=MOD;
		}
	}

However, time complexity for this solution is O(n^2).
We can store cumulative sum of dp to reduce the complexity.
cum*=\sum_{j=0}^{i} dp[j]

dp[0]=1;
	cum[0]=1;
	for (i=1 to n) {
		dp*=0;
		if(i-k is greater than equal to 0)
			dp*+=(cum[i-k]);
			dp*%=MOD;
		}
		cum*=(cum[i-1]+dp*)%MOD;
	}

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.