humbIefool's blog

[Solved]Pls help me with this formula
By humbIefool, history, 3 years ago, In English

Hello codeforces, I want your help in following permutation and combination problem.

We are given an arr of numbers and we want to find the no of ways to put all occurences of second max(arr) to left of the max(arr) and ofcourse all the numbers are different(for eg. 4 4, we can arrange these in two ways). I couldn't solve yesterday's C just because of this, so I wanna learn this now. Thanks and have a good day :)

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

There's a purely combinatorial way to do this.

As mentioned in the other comment, if there is more than one maximal element, then the answer is $$$n!$$$.

If there is only one maximal element, and $$$x$$$ second-max elements, then the answer is $$$\frac{n!}{x+1}$$$. We can show this using probabilities; if we permute the array randomly, you are effectively permuting the order of max and second-max. As there are $$$x+1$$$ such numbers, there's a $$$\frac{1}{x+1}$$$ probability that the max ends up after all the second-max numbers.

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Suppose there are M second max values. Also, let's denote the max value as F and second max value as S. Obviously, the number of ways to create a permutation of length N is factorial(N). When you fix one permutation, the order of S and F will be one of the following. [F S S ... S] [S F S ... S] [S S F ... S] ... [S S S ... F] so, the ways to put F in front of some S will be factorial(N) * M / (M + 1)

→ Reply