### Lance_HAOH's blog

By Lance_HAOH, history, 10 months ago, ,

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).

•
• +12
•

 » 10 months ago, # | ← Rev. 4 →   0 can we swap two same fruits? For example :1Apple 1Orange 1Cherry 2Apple 2Orange 2Cherry and 2Apple 1Orange 1Cherry 1Apple 2Orange 2CherryLike this
•  » » 10 months ago, # ^ |   0 No.
 » 10 months ago, # |   0 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.
•  » » 10 months ago, # ^ |   0 Hmm. How would you count the number of YZ between the Xs? I think that this step itself is non-trivial.
•  » » » 10 months ago, # ^ |   -27 tourist Hey help this guy.
 » 10 months ago, # |   0 I do think that the solution would be (x+y+z)!/{x!y!z!}
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 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.
 » 10 months ago, # | ← Rev. 3 →   +20 Here is the tutorial of this problem, seeing the problem I. tutorialAnd here is an accept code written by me a long time ago... https://ideone.com/0gpXJI
•  » » 10 months ago, # ^ | ← Rev. 3 →   +8 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.