Домівка > Комбінаторика, Теорія чисел > Розв’язання задачі BearEmptyCoin

Розв’язання задачі BearEmptyCoin

Нещодавно спробував одну з задач першого дивізіону на топкодері. Задача виявилось надто складною для того, щоб я її самостійно розв’язав, навіть зрозуміти код, який вільно доступний, я не зміг. Отже, шукав допомоги в інтернеті. На запит “BearEmptyCoin” Google мені видав кілька посилань власне на topcoder.com і посилання на три блоги, китайською, корейською і японською мовами:) За допомогою Google перекладача, який досить невміло перекладає з цих мов, мені вдалось якось докопатись до істини. Тому, зараз я можу поділитись поясненням розв’язку із вами.

Формулювання

Маємо чесну монету, чисту з обох боків. Цією монетою ми гратимемо в гру. На початку рахунок 0, гра триватиме K раундів. Кожен раунд такий:
1. Вкидаємо монету.
2. Якщо верхній бік порожній, то записуємо на нього число, яке забажаємо.
3. Додаємо до рахунку число записане на верхньому боку монетки.
Для перемоги потрібно, щоб кінцевий рахунок був S.

На вході ми маємо K, S. Нехай P – ймовірність виграшу у разі слідування найоптимальнішій стратегії. Можна показати, що P помножена на 2^K є цілим числом. Повернути це число.

Обмеження

  • K \in [1, 60],
  • X \in [-10^9, 10^9].

Розв’язання

Маючи K раундів кількість можливих аверсів x_i лежить в діапазоні [0, K], кількість реверсів відповідно становить K - x_i. З цього ми можемо записати формулу успіху для певного випадку x_i \times a + (K - x_i) \times b_i = S, де a, b – числа записані нами на аверсі і реверсі, той бік. що випадає першим вважаємо аверсом.

Числа a, b заздалегідь невідомі. Для того, щоб такі числа існували необхідно, щоб d_i = \gcd(x_i, K - x_i) | S, тобто, щоб найбільший спільний дільник x_i і (K - x_i) ділив S. Або, тотожно, \gcd(x_i, K)|S.

Таким чином, маємо K + 1 можливих значень для x_i, які не всі можливі. Ключовим моментом у розв’язанні задачі, є те, що для всіх можливих значень x_i, число написане після першого вкидання може бути однаковим. Для доведення цього запишемо рівняння у вигляді системи:

\left\{\begin{matrix} x_1 a + (K - x_1) b_1 = S \\ \dots \\ x_{K+1} a + (K - x_{K+1}) b_{K+1} = S \end{matrix}\right.

І далі

a e_i d_i = s_i d_i - (k_i - e_i) d_i b_i,
a e_i = s_i - (k_i - e_i) b_i,
a e_i = s_i - f_i b_i,
Оскільки \gcd(e_i, f_i) = 1, то використовуючи розширений алгоритм Евкліда, можна показати, що наступне вірно
a \equiv e_i^{-1} s_i \pmod {f_i}

Чи можемо ми розв’язати цю систему конгруентностей? Так, можемо! Про це нам каже одне з можливих формулювань китайської теореми про залишки. Це формулювання допускає не взаємно прості модулі. Ось воно:

Нехай n_1,...,n_k \in \mathbb{N} і нехай a_1,...,a_k \in \mathbb{Z}.Тоді існує x \in \mathbb{Z}, яке задовольняє системі такій рівнянь:
x\equiv a_1 \pmod {n_1}
x\equiv a_2 \pmod {n_2}
\ldots
x\equiv a_k \pmod{n_k}
тоді і тільки тоді, коли a_i \equiv  a_j \pmod{\gcd(n_i,n_j)} для всіх i,j=1,...,k.

Якщо числа n_i, для i=1,...,k взаємно прості, це класична версія теореми.

Нам треба довести, що e_i^{-1} s_i \equiv e_j^{-1} s_j \pmod{\gcd(f_i, f_j)}.
Позначимо d = \gcd(f_i, f_j).
e_i^{-1}e_i \equiv 1 \pmod{f_i} \Rightarrow e_i^{-1} e_i \equiv 1\pmod d,
домножимо обидва боки на a:
s_i e_i^{-1} \equiv a \pmod d, тобто цей добуток не залежить від i за модулем d.

Отже, ми бачимо, що ми можемо знайти єдине a, що задовольняє усім можливим варіантам перебігу гри. Це значення ми записуємо на першому порожньому боку монетки. Далі, коли випадає другий порожній бік, ми вибираємо b_i, яке найбільше нас влаштовує, але ані конкретне значення a, ані конкретне значення b_i нам шукати не потрібно.

Алгоритм
int gcd(int x, int y){
    return x ? gcd(y % x, x) : y;
} 

long long win_probability(int K, int S){
    int i, j; 

    if(S < 0) S = -S;

    // Окремо обробляємо найпростіший випадок
    if(S % K == 0) return (1ll << K);

    // Знаходимо, які можливі значення можуть приймати x_i
    for(i = 1; i <= K; i++) can[i] = (S % gcd(K, i) == 0);

    // Формуємо трикутник Паскаля
    for (i = 0; i < K+1; ++i) {
        for (j = 0; j < i + 1; ++j) {
            if(j == 0 || j == i) C[i][j] = 1;
            else C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }

    ll ans = 0;
    if(can[K]) ans += 2; 

    // Для кожної можливої неперервної послідовності аверсів,
    // що починається від першого вкидання
    for(i = 1; i < K; ++i){
        long long best = 0;
        // Скільки ми ще можемо мати реверсів
        for(j = 0; j <= K - i - 1; ++j)
            // За допомогою трикутника Паскаля визначаємо вагу кожного випадку
            if(can[1 + j]) best = max(best, 2 * C[K - i - 1][j]);
        ans += best;
    } 

    return ans;
}

Посилання

Advertisements
  1. Коментарів ще немає.
  1. No trackbacks yet.

Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: