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 1*e*9 + 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* ≤ 2*e*5

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?

can we swap two same fruits? For example :

1Apple 1Orange 1Cherry 2Apple 2Orange 2Cherry and 2Apple 1Orange 1Cherry 1Apple 2Orange 2Cherry

Like this

No.

You can lock one of the fruits. For example if you lock the apples, arrangement would be like ...X...X...X...X... and between those X's YZY..Z or YZY..Y or ZYZ..Z or ZYZ..Y. And you have to find how many ways you can put those ...YZYZYZ... between those X's.

Hmm. How would you count the number of YZ between the Xs? I think that this step itself is non-trivial.

tourist Hey help this guy.

I do think that the solution would be (x+y+z)!/{x!y!z!}

Are you sure? Maybe you want to check your solution against the sample test cases provided in the problem link? It is quite obvious that your solution does not consider the restrictions on adjacent similar fruits.

Here is the tutorial of this problem, seeing the problem I.

tutorial

And here is an accept code written by me a long time ago...

https://ideone.com/0gpXJI

Hi. I have read the tutorial before. However, the important formula on page 37 is not explained. Did you manage to derive it on your own? If you did, how did you manage to derive it?

Please advise.