Educational Codeforces Round 117 — Editorial

Here is a slightly different approach for problem G which I think is easier. (Sorry if my explanation is not good.) It would seem that many other people have this approach too.

First, let's ask ourselves, given an array, how can we find the total sum of distances between all pairs of equal elements? For each element, we will need to add to the answer the sum of absolute values between each pair of indexes where it exists. This is a very well known problem, and can be easily understood by looking at an example.

Let's say an element exists at the indices [1,4,5,6,8][1,4,5,6,8]. Then, we will need to add (4−1)+(5−1)+(6−1)+(8−1)+(5−4)+(6−4)+(8−4)+(6−5)+(8−5)+(8−6)(4−1)+(5−1)+(6−1)+(8−1)+(5−4)+(6−4)+(8−4)+(6−5)+(8−5)+(8−6) to the answer. Overall, 1 has been subtracted 4 times, 4 has been subtracted twice, 5 does not contribute towards the sum, 6 is added twice, and 8 is added 4 times. So we will add to the sum (−4)∗1+(−2)∗4+(0)∗5+(2)∗6+(4)∗8(−4)∗1+(−2)∗4+(0)∗5+(2)∗6+(4)∗8. In general, for a sorted array [p1,p2,…,px][p1,p2,…,px], we will add to the answer p1∗(1−x)+p2∗(3−x)+p3∗(5−x)+...+px∗(x−1)p1∗(1−x)+p2∗(3−x)+p3∗(5−x)+...+px∗(x−1). We can think of this as assigning multiplying each index by a coefficient and finding the total sum of indexes, such that the coefficients assigned to indexes with the same element are a [1−x,3−x,…,x−1][1−x,3−x,…,x−1] in ascending order.

We can now move on to maximising the answer. We will generate a coefficient array. For each cici, we will add the elements [1−ci,3−ci,…,ci−1][1−ci,3−ci,…,ci−1] to the coefficient array. Then, we want to obtain a permutation of this coefficient array [p1,p2,…,pn][p1,p2,…,pn] such that ∑ni=1ipi∑i=1nipi is maximised. By the rearrangement theorem, this sum is maximised when pp is sorted, and it is easy to see that such a permutation is possible.

For more clarity, consider the case where c=[3,3,2]c=[3,3,2]. We will generate the coefficient array [−2,0,2]+[−2,0,2]+[−1,1]=[−2,−2,−1,0,0,1,2,2][−2,0,2]+[−2,0,2]+[−1,1]=[−2,−2,−1,0,0,1,2,2]. Then the maximum answer will be (−2)∗0+(−2)∗1+(−1)∗2+(0)∗3+(0)∗4+(1)∗5+(2)∗6+(2)∗7=27(−2)∗0+(−2)∗1+(−1)∗2+(0)∗3+(0)∗4+(1)∗5+(2)∗6+(2)∗7=27, and this is achievable for example by choosing a=[1,2,3,1,2,3,1,2]a=[1,2,3,1,2,3,1,2].

Now, how do we do this fast? Instead of actually generating the coefficient array, we will simply create a frequency map storing how many times each element exists in the coefficient array. We can create this map quickly using a difference array (or you can visualise this as a sweepline). We will then iterate through this map in ascending order. For each element ee which occurs numnum times in the coefficient array, we will assign ee as the coefficient of the numnum lowest indexes which we haven't assigned yet, and increment our answer by (e∗e∗ sum of chosen indexes). Remember that of the distinct elements in aa, exactly numnum of these elements will have contributed ee to the coefficient array, so these indexes will correspond to some permutation of these numnum elements in aa. We will therefore multiply the number of possible arrays by num!num!, as this is the number of permutation of these numnum elements in aa.

See https://codeforces.com/contest/1612/submission/136599117 for implementation details. If an array is used instead of a map, the overall complexity of this algorithm is O(m+max(ci))O(m+max(ci)).