Числовий граф#199

Числовий граф (Editorial)

Значення гри важко рахувати напряму, зате легко перевіряти порогові питання. Тому застосуємо двійковий пошук за відповіддю: зафіксуємо і з'ясуємо, чи може Василь гарантувати результат не менший за . Що більше , то важче, отже предикат монотонний.

За фіксованого гра стає булевою. Назвемо вершину:

  • виграшною (), якщо ходить Василь і він досягає результату ;

  • програшною для Петрика (), якщо ходить Петрик і Василь усе одно отримує .

Правила переходу прямо випливають з умови — гравець або зупиняє гру, або рухає фішку:

\mathrm{good}[v] \;=\; \bigl(a_v \ge X\bigr) \;\lor\; \exists\, u \in \mathrm{succ}(v):\ \mathrm{bridge}[u],
\mathrm{bridge}[v] \;=\; \bigl(a_v \ge X\bigr) \;\land\; \forall\, u \in \mathrm{succ}(v):\ \mathrm{good}[u].

Перше: Василеві досить зупинитися на достатньо великому числі або штовхнути фішку в позицію, де вже Петрик безсилий. Друге: Петрикові не допомагає зупинка (число завелике), і будь-який його хід веде в позицію, де Василь виграє.

Обчислення — зворотний обхід. Це класична «ретроградна» схема з чергою. Спочатку позначаємо для всіх вершин із a_v \ge X. Для кожної вершини тримаємо лічильник — скільки її наступників ще не виграшні; спочатку це кількість наступників з a_u < X. Коли вершина стає виграшною, зменшуємо лічильники всіх її попередників; щойно в вершини з a_v \ge X лічильник упав до нуля, вона стає , і тоді всі її попередники стають виграшними й потрапляють у чергу. Кожне ребро обробляється один раз, тому перевірка коштує \mathcal{O}(n + m).

Що з нескінченною грою. Вершини, які так і не позначилися, — це саме ті, з яких Петрик може ухилятися вічно. За умовою після 10^{100} ходів гра завершується там, де стоїть фішка, а Петрик, маючи змогу нескінченно уникати «мостів», просто тримається вершин зі значенням, меншим за . Тому непозначена вершина трактується як невиграшна — жодної окремої обробки циклів не потрібно, схема сама дає правильну відповідь.

Відповідь — найбільше , за якого істинне. Загальна складність — \mathcal{O}\bigl((n+m)\log \max a_i\bigr).