CDX1602 - Editorial

PROBLEM LINK:

Practice
Contest

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.

1 Like

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

Hi guys,follow this link it’s well explained along with code.

Editorial