SECPLAYER - Second Player - CodeChef

Question

Witam,
Próbuję rozwiązać https://www.codechef.com/problems/SECPLAYER. Ogółem doszedłem do wniosku, że

E[x_i] = (x_i * prawdopodobieństwo, że x_i zagra tylko jeden mecz) 
             + (x_i * prawdopodobieństwo, że x_i będzie grał tylko z graczami o mniejszym ratingu)

(Zakładam, że gracze są posortowani rosnąco ze wzg. na ich rating)

Dlaczego? Bo jeśli zagra tylko 1 mecz, to znaczy, że reszta się powybijała i x_i stanie do walki z graczem z najlepszym ratingiem (tylko on mógł przetrwać w tej bijatyce), no i skoro będzie się pojedynkować z najlepszym, to na pewno przegra, więc będzie na 2 miejscu. 

Natomiast jest jeszcze przypadek, że zagra więcej niż 1 mecz. Wtedy liczę prawdopodobieństwo, że dojdzie on do 2 miejsca. Żeby to się stało, to ten x_i musi walczyć tylko z graczami o ratingu mniejszym od siebie, a to znaczy, że gracze z ratingiem większym od x_i muszą grać tylko między sobą. Więc zdanie prawdopodobieństwo, że x_i będzie grał tylko z graczami o mniejszym ratingu kryje w sobie tak na prawdę iloczyn dwóch prawdopodobieństw. 

Tylko mam problem, żeby zapisać to matematycznie. 

1. Prawdopodobieństwo, że x_i zagra z graczami tylko o mniejszym ratingu wynosi a = indeks(x_i) / N
2. Prawdopodobieństwo, że gracze z ratingiem większym od x_i będą grali tylko ze sobą, wynosi b = (N - indeks(x_i)) / N

Więc ten 2 przypadek (że zagra więcej niż 1 mecz) można opisać jako x_i * a * b.

Jeszcze trzeba dodać przypadek 1, tylko jak mam zapisać prawdopodobieństwo, że x_i zagra tylko 1 mecz? I czy nie pominąłem czegoś w rozwiązaniu?

Comments

Ja tylko zaznaczę, że to i poprzednie zadanie wyglądają znacznie bardziej jak zadania z matematyki i rachunku prawdopodobieństwa niż z informatyki/programowania, więc zgaduję że jakieś forum do zadań matematycznych pewnie byłoby lepsze do takich pytań.

(inna sprawa, że też nie rozumiem do końca co takie zadania robią na CodeChef)

---

@Szyszka, nie rozumiem, w jakiej formie chcą wyniku. Czyli akapit rozpoczynający się następująco (nie wkleiłem całości, ponieważ tutaj nie formatuje poprawnie wyrażeń matematycznych):

The expected rating of the second player can be represented as a fraction of the form

Dlaczego dla wyniku 5⁄3 wychodzi 666666673?

---

(P/Q) mod m = ((P mod m) * (Q^-1 mod m)) mod m
Pisząc Q^-1 mam na myśli odwrotność modulo. Jeśli m jest liczbą pierwszą, a w tym przypadku jest (1000000007), to odwrotność modulo z Q jest równe Q^(m-2) mod m, czyli w tym przypadku Q^(1000000005) mod 1000000007. Więc jeśli chodzi o 5/3, to mamy (5 * modulo inverse z 3) mod 1000000007, czyli (5 * 333333336) mod 1000000007 = 1666666680 mod 1000000007 = 666666673

---

Tylko że trzeba liczyć niezależne prawdopodobieństwa, a w przypadku jednego meczu oraz meczy ze słabszymi i osobno silniejszych – pokrywają się przypadki. Więc wyrzucając przypadki pokrywające się pozostaje tylko liczba rozegranych meczy poza graczem (tak by rozegrał ostatni mecz) oraz liczba meczy gracza ze słabszymi.

Posklejałem coś takiego, ale dalej nie przechodzi:

#include <stdio.h>
int
qsort_cmp( void *a
, void *b
){  unsigned long a_ = *( unsigned long * )a, b_ = *( unsigned long * )b;
    return a_ - b_;
}
unsigned long
draw( unsigned long n
){  unsigned long res = n % 2 ? 3 : 1;
    for( unsigned long i = n % 2 ? 3 : 2; i != n; i += 2 )
    {   res *= 5;
        res++;
    }
    return res;
}
void
xgcd( long *result
, long a
, long b
){  long aa[2] = { 1, 0 }, bb[2] = { 0, 1 }, q;
    while(1) {
        q = a / b;
        a = a % b;
        aa[0] = aa[0] - q * aa[1];
        bb[0] = bb[0] - q * bb[1];
        if( !a )
        {   result[0] = b;
            result[1] = aa[1];
            result[2] = bb[1];
            return;
        }
        q = b / a;
        b = b % a;
        aa[1] = aa[1] - q * aa[0];
        bb[1] = bb[1] - q * bb[0];
        if( !b )
        {   result[0] = a;
            result[1] = aa[0];
            result[2] = bb[0];
            return;
        }
    }
}
int
main( int argc
, char *argv[]
){  unsigned testcases_n;
    scanf( "%u", &testcases_n );
    for( unsigned testcase_i = 0; testcase_i != testcases_n; testcase_i++ )
    {   unsigned long ratings_n;
        scanf( "%u", &ratings_n );
        unsigned long *ratings = ( unsigned long * )calloc( ratings_n, sizeof( *ratings ));
        for( unsigned long rating_i = 0; rating_i != ratings_n; rating_i++ )
            scanf( "%u", &ratings[ rating_i ] );
        if( ratings_n > 2 )
        {   qsort( ratings, ratings_n, sizeof( *ratings ), qsort_cmp );
            unsigned long expected_rating = 0;
            for( unsigned long rating_i = 0; rating_i != ratings_n - 1; rating_i++ )
                expected_rating += ratings[ rating_i ] * ( draw( ratings_n - 1 ) + rating_i );
            long res[3];
            xgcd( &res[0], draw( ratings_n ), 1000000007 );
            printf( "%ld\n", expected_rating * res[1] % 1000000007 );
        }else
            puts( "1" );
        free(ratings);
    }
    return 0;
}

⁂

Tutaj jest krótkie wyjaśnienie problemu.