PROBLEM LINK:
Author: Puneet Gupta
Editorialist: Puneet Gupta
DIFFICULTY:
MEDIUM
PREREQUISITES:
DP
PROBLEM:
Given the values of n1, n2, k1, k2 we need to find the number of possible permutations of arranging n1 footmen + n2 horsemen such that there are strictly no more that k1 footmen standing successively one after another, or there are strictly no more than k2 horsemen standing successively one after another.
EXPLANATION:
The problem is solved lazy dynamics. Let z[n1] [n2] [2] be the number of ways to place troops in a legion of Caesar.
Indicate the following parameters, n1 – is the number of footmen, n2 – is the number of horseman, the third parameter indicates what troops put Caesar in the beginning of the line.
If Caesar wants to put the footmen, the state dynamics of the z [n1] [n2] [0] go to the state z [n1] [n2 - i] [0], where 0 <= i <= min (k1, n1) .
If Caesar wants to put the horsemen, the state dynamics of the z [n1] [n2] [1] go to the state z [n1] [n2 - i] [1], where 0 <= i <= min (k2, n2) .
AUTHOR’S SOLUTION:
Author’s solution can be found here.