# CDX1602 - Editorial

Author: Puneet Gupta
Editorialist: Puneet Gupta

MEDIUM

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.

Is it okay to completely copy both the problem and editorial from other sites like Codeforces and take full credit for it?

http://codeforces.com/problemset/problem/118/D

http://codeforces.com/blog/entry/2822

3 Likes