How to solve this Combinatorics problem?

Правка en3, от Lance_HAOH, 2018-01-23 09:21:16

Hi. I am trying to solve this problem.

For convenience, I have summarised the problem statement below:

Problem Statement

We are tasked to arrange X Apples, Y Cherries and Z mangoes on a line, Compute the number of valid arrangements (modulo 1e9 + 7). All X + Y + Z fruits must be used in a single arrangement.

A valid arrangement is defined as an arrangement in which no two fruits of a similar kind are adjacent (no wraparound).

Constraints: 1 ≤ X, Y, Z ≤ 2e5

Time limit: 2s


Example

Example of a valid arrangement for X = 2, Y = 2, Z = 2 is:

Apple Orange Cherry Apple Orange Cherry

Example of a invalid arrangement for X = 2, Y = 2, Z = 2 is:

Apple Apple Orange Cherry Orange Cherry


My analysis

If the constraints were smaller, an obvious dynamic programming solution would suffice. However, the large constraints here seem to point towards a combinatorics solution (which I cannot figure out).


Could someone please advise me on how to solve this problem?

Теги #combinatorics, #dynamic-programming, #kattis

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Lance_HAOH 2018-01-23 09:21:16 2 Tiny change: 'le 2e5 $\nTime lim' -> 'le 2e5 $\n\nTime lim'
en2 Английский Lance_HAOH 2018-01-23 09:19:48 46
en1 Английский Lance_HAOH 2018-01-23 09:18:20 1208 Initial revision (published)