PROBLEM LINK:
Author: ???
Tester: Kevin Atienza, Jingbo Shang
Editorialist: Kevin Atienza
PREREQUISITES:
Sorting, combinatorics
PROBLEM:
The strength of an array a = (a_1,\ldots,a_n) is the sum of |i-j| for all 1 \le i \le j \le n such that a_i = a_j.
How many arrangements of a are there such that the strength is the maximum possible among all rearrangements? (modulo 10^9 + 7)
QUICK EXPLANATION:
Let v be a value of a which appears k times. Replace the i th occurrence of v with 2i-k-1. Do this for all distinct values v.
Let c_w be the number of times w appears in this new array. The answer is then
EXPLANATION:
The first observation is that the actual values of a themselves don’t matter a lot. The positions of a particular value doesn’t matter either, because we’re going to rearrange a anyway. For a given value v of a, all that matters really is the number of times v appears in a, because all rearrangements of a will contain that many appearances of v.
Let’s fix a value v, and say it appears k times in a. Obviously, the best way to place these v s in the rearrangement is to place (roughly) half in one end and the remaining ones in the other. For example, if the value 5 appears 6 times, then placing it in the following manner maximizes its contribution to the strength: (5,5,5,?,?,?,?,?,5,5,5).
However, when there are other values involved, things are trickier. It’s tempting to say that the best way would be to place the most frequent values outside the array, but actually we can’t be greedy like this. It’s true that the more times a number appears, the higher its contribution to the strength is, but when combined with other values, it’s not always optimal to place them in the outer edges of the array. For example, if a = (4,4,4,4,5,5,5,5,5,5), then our method will yield (5,5,5,4,4,4,4,5,5,5), but this is not the best; the rearrangement (5,4,5,4,5,5,4,5,4,5) yields a higher strength.
To find the optimal arrangement, we need to dig a little deeper. Again let’s look at a particular value v which appears k times. Suppose p_1 < p_2 < \ldots < p_k are the positions of the v s. Then the contribution of the v s to the strength is:
We now notice the following: the contribution of each position p_i is equal to itself weighted by (2i-k-1). For other values than v, a similar situation happens, though the weights may be different. Thus, we can say the following:
The contribution of the i th occurrence of v is its position weighted by (2i-k-1), where k is the number of times v appears.
Let’s consider the weight array of a, i.e. the sequence of weights of all numbers. For example, for the array
the weight array is
(For example, check that the four instances of 1 have weights -3, -1, 1 and 3.)
Now, assuming we can rearrange this array any way we want, what is the rearrangement of this weight array that maximizes the strength? Clearly we can be greedy with this and the best way is simply to sort the array, yielding: (-3,-2,-1,-1,0,0,1,1,2,3). Thus, we just found a very fast way of computing the maximum strength!
There’s a slight issue with this though. Clearly this is the best we can do, but note that we assumed we can rearrange the array any way we want, but this is not true. For example, we can’t place the second occurrence of a value before its first occurrence. But since the weight of the i th occurrence is strictly less than the $(i+1)$th occurrence of a given value, any arrangement placing these occurrences out of order will never yield the maximum strength, so we’re fine 
The remaining part is to count how many arrangements yield this maximum. But this isn’t too hard. First, count the number of times each weight appears. Now we can’t reorder the weight array because we have to keep them sorted, but same-weight entries can be arranged amongst themselves. For any weight w appearing c_w times, there are c_w! ways to arrange these values, so we determine that the number of arrangements is simply
(Notice that all weights are > -n and < n)
The running time is O(n \log n), dominated by sorting / counting frequencies of the $a_i$s. All other parts of the algorithm can be done in O(n).
Don’t forget to reduce modulo 10^9 + 7!
Time Complexity:
O(n \log n)
AUTHOR’S AND TESTER’S SOLUTIONS:
[setter][333]
[tester][444]
[editorialist][555]
[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[555]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.