SECPLAYER - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Lavish Gupta
Tester: Danny Mittal
Editorialist: Nishank Suresh

DIFFICULTY:

Medium

PREREQUISITES:

Linearity of expectation and/or observation

PROBLEM:

N players with distinct ratings compete in a tournament, the i-th of whom has rating A_i. Each round, two people are uniformly randomly chosen from those remaining, and the one among them with higher rating wins; with the loser being eliminated.
Find the expected rating of the player who finishes second.

EXPLANATION:

Let’s order the players by decreasing rating, A_1 > A_{2} > \dots > A_{N-1} > A_N.

What’s the probability that the player with rating A_N finishes second?

Answer

This is only possible if A_N is not chosen in any match except the last, because they are guaranteed to lose any match they play.

  • For the first match, there are \binom{N}{2} possible matches, of which \binom{N-1}{2} don’t include A_N.
  • For the second match, \binom{N-1}{2} matches of which \binom{N-2}{2} don’t include A_N.
    \vdots

Multiplying all these together, we see that the probability comes out to be

\frac{\binom{N-1}{2} }{\binom{N}{2}} \frac{\binom{N-2}{2} }{\binom{N-1}{2}} \frac{\binom{N-3}{2} }{\binom{N-2}{2}} \dots \frac{\binom{2}{2} }{\binom{3}{2}}

which cancels out to just give us

\frac{\binom{2}{2}}{\binom{N}{2}} = \frac{1}{\binom{N}{2}}

Now, what about the case when A_N doesn’t finish second?
The expected value then is simply the expected value of the process run on the set \{A_1, A_2, \dots, A_{N-2}, A_{N-1}\}.
This is because if A_N is guaranteed to lose any match they are chosen to play in - and thus A_N plays exactly one match. Thus, without loss of generality, we can assume that A_N is chosen to be in the very first match and immediately loses, leaving us with only the first N-1 elements contributing to the expected value.

This observation allows us to formulate a dynamic programming solution.

Let E_i denote the expected rating of the second player when considering only A_1, A_2, \dots, A_i. Our final answer will be E_N.
As a base case, we define E_2 = A_2 (because there is only one choice of second player).
Now let’s look at how to compute E_i for i\geq 3.
Our earlier arguments tell us that the probability that A_i is the second player is exactly \dfrac{1}{\binom{i}{2}} (given that we’re only considering the first i players), and if A_i is not the second player the expectation is E_{i-1}.
Linearity of expectation then gives us the recurrence

E_i = \frac{1}{\binom{i}{2}}\cdot A_i + \left(1 - \frac{1}{\binom{i}{2}}\right)\cdot E_{i-1}

which is easily computed by simply iterating i from 3 to N.

An alternate “solution”

It is possible to ‘solve’ this problem by other methods as well, for example by writing a brute-force solution for small values of N and guessing the multipliers.

It turns out that the solution is (given that A_i have been sorted in increasing order)

\sum_{i=1}^{N-1} A_i\cdot \frac{2N + 2}{(N-1)(N-i+1)(N-i+2)}

TIME COMPLEXITY:

\mathcal{O}(N\log N) per test.

CODE:

Setter (C++)
#define ll long long
#define dd long double
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mp make_pair
#define mt make_tuple
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
#define tll tuple<ll ,ll , ll> 
#define pll pair<ll ,ll> 
#include<bits/stdc++.h>
/*#include<iomanip>   
#include<cmath>
#include<cstdio>
#include<utility>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<bitset>*/
dd pi = acos(-1) ;
ll z =  1000000007 ;
ll inf = 100000000000000000 ;
ll p1 = 37 ;
ll p2 = 53 ;
ll mod1 =  202976689 ;
ll mod2 =  203034253 ;
ll fact[100] ;
ll gdp(ll a , ll b){return (a - (a%b)) ;}
ll ld(ll a , ll b){if(a < 0) return -1*gdp(abs(a) , b) ; if(a%b == 0) return a ; return (a + (b - a%b)) ;} // least number >=a divisible by b
ll gd(ll a , ll b){if(a < 0) return(-1 * ld(abs(a) , b)) ;    return (a - (a%b)) ;} // greatest number <= a divisible by b
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
ll e_gcd(ll a , ll b , ll &x , ll &y){ if(b > a) return e_gcd(b , a , y , x) ; if(b == 0){x = 1 ; y = 0 ; return a ;}
ll x1 , y1 , g; g = e_gcd(b , a%b , x1 , y1) ; x = y1 ; y = (x1 - ((a/b) * y1)) ; return g ;}
ll power(ll a ,ll b , ll p){if(b == 0) return 1 ; ll c = power(a , b/2 , p) ; if(b%2 == 0) return ((c*c)%p) ; else return ((((c*c)%p)*a)%p) ;}
ll inverse(ll a ,ll n){return power(a , n-2 , n) ;}
ll max(ll a , ll b){if(a > b) return a ; return b ;}
ll min(ll a , ll b){if(a < b) return a ; return b ;}
ll left(ll i){return ((2*i)+1) ;}
ll right(ll i){return ((2*i) + 2) ;}
ll ncr(ll n , ll r){if(n < r|| (n < 0) || (r < 0)) return 0 ; return ((((fact[n] * inverse(fact[r] , z)) % z) * inverse(fact[n-r] , z)) % z);}
void swap(ll&a , ll&b){ll c = a ; a = b ; b = c ; return ;}
//ios_base::sync_with_stdio(0);
//cin.tie(0); cout.tie(0);
using namespace std ;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
//__builtin_popcount(n) -> returns number of set bits in n
ll seed;
mt19937 rnd(seed=chrono::steady_clock::now().time_since_epoch().count()); // include bits
const int N = 1000000 ;


void solve()
{
    ll n ;
    cin >> n ;
    ll arr[n] ;
    fo(i , n)
        cin >> arr[i] ;
    sort(arr , arr + n);
    reverse(arr , arr + n) ;

    ll ans[n] ;
    ans[0] = arr[0] ;
    ans[1] = arr[1] ;
    for(int i = 2 ; i < n ; i++)
    {
        ll val = (i * (i+1))/2 ;
        val %= z ;
        val = inverse(val , z) ;
        ans[i] = (1-val)*(ans[i-1]) + (val * arr[i]) ;
        ans[i] = ((ans[i]%z) + z)%z ;
    }

    cout << ans[n-1] << '\n' ;
    return ;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif
 
    ll t = 1;
    cin >> t ;
    fo(i , t)
        solve() ;
    
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
 
    return 0;
}
Tester (Kotlin)
import java.io.BufferedInputStream

const val MOD = 1000000007L

const val BILLION = 1000000000

fun main(omkar: Array<String>) {
    val jin = FastScanner()
    var nSum = 0
    repeat(jin.nextInt(500)) {
        val n = jin.nextInt(500000)
        nSum += n
        if (nSum > 500000) {
            throw IllegalArgumentException("limit on sum n exceeded")
        }
        val ratings = Array(n) { jin.nextInt(BILLION, it == n - 1).toLong() }
        ratings.sort()
        if (ratings.toSet().size != n) {
            throw IllegalArgumentException("ratings aren't distinct")
        }
        var answer = 0L
        var coefficient = (((n.toLong() * (n - 1).toLong()) / 2L) % MOD) pow -1
        for (k in 1 until n) {
            //println("k = $k, coefficient = $coefficient")
            answer += coefficient * ratings[k - 1]
            answer %= MOD
            coefficient *= (n + 2 - k).toLong()
            coefficient %= MOD
            coefficient *= (n - k).toLong() pow -1
            coefficient %= MOD
        }
        println(answer)
    }
    jin.assureInputDone()
}

const val MOD_TOTIENT = MOD.toInt() - 1

infix fun Long.pow(power: Int): Long {
    var e = power
    e %= MOD_TOTIENT
    if (e < 0) {
        e += MOD_TOTIENT
    }
    if (e == 0 && this == 0L) {
        return this
    }
    var b = this % MOD
    var res = 1L
    while (e > 0) {
        if (e and 1 != 0) {
            res *= b
            res %= MOD
        }
        b *= b
        b %= MOD
        e = e shr 1
    }
    return res
}

class FastScanner {
    private val BS = 1 shl 16
    private val NC = 0.toChar()
    private val buf = ByteArray(BS)
    private var bId = 0
    private var size = 0
    private var c = NC
    private var `in`: BufferedInputStream? = null

    constructor() {
        `in` = BufferedInputStream(System.`in`, BS)
    }

    private val char: Char
        private get() {
            while (bId == size) {
                size = try {
                    `in`!!.read(buf)
                } catch (e: Exception) {
                    return NC
                }
                if (size == -1) return NC
                bId = 0
            }
            return buf[bId++].toChar()
        }

    fun assureInputDone() {
        if (char != NC) {
            throw IllegalArgumentException("excessive input")
        }
    }

    fun nextInt(endsLine: Boolean): Int {
        var neg = false
        c = char
        if (c !in '0'..'9' && c != '-' && c != ' ' && c != '\n') {
            throw IllegalArgumentException("found character other than digit, negative sign, space, and newline")
        }
        if (c == '-') {
            neg = true
            c = char
        }
        var res = 0
        while (c in '0'..'9') {
            res = (res shl 3) + (res shl 1) + (c - '0')
            c = char
        }
        if (endsLine) {
            if (c != '\n') {
                throw IllegalArgumentException("found character other than newline")
            }
        } else {
            if (c != ' ') {
                throw IllegalArgumentException("found character other than space")
            }
        }
        return if (neg) -res else res
    }

    fun nextInt(from: Int, to: Int, endsLine: Boolean = true): Int {
        val res = nextInt(endsLine)
        if (res !in from..to) {
            throw IllegalArgumentException("$res not in range $from..$to")
        }
        return res
    }

    fun nextInt(to: Int, endsLine: Boolean = true) = nextInt(1, to, endsLine)
}
Editorialist (Python)
mod = int(10**9 + 7)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    for i in range(n-1):
        mul = 2 * (n+1)
        mul *= pow((n-1)*(n-i)*(n-i+1), mod-2, mod)
        ans += mul*a[i]
        ans %= mod
    print(ans)