Lance_HAOH's blog

By Lance_HAOH, history, 4 weeks ago, In English,

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?

 
 
 
 
  • Vote: I like it  
  • +12
  • Vote: I do not like it  

»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

can we swap two same fruits? For example :

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

Like this

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
4 weeks ago, # |
Rev. 3   Vote: I like it +20 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    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.