Значення гри важко рахувати напряму, зате легко перевіряти порогові питання. Тому застосуємо двійковий пошук за відповіддю: зафіксуємо і з'ясуємо, чи може Василь гарантувати результат не менший за . Що більше , то важче, отже предикат монотонний.
За фіксованого гра стає булевою. Назвемо вершину:
виграшною (), якщо ходить Василь і він досягає результату ;
програшною для Петрика (), якщо ходить Петрик і Василь усе одно отримує .
Правила переходу прямо випливають з умови — гравець або зупиняє гру, або рухає фішку:
Перше: Василеві досить зупинитися на достатньо великому числі або штовхнути фішку в позицію, де вже Петрик безсилий. Друге: Петрикові не допомагає зупинка (число завелике), і будь-який його хід веде в позицію, де Василь виграє.
Обчислення — зворотний обхід. Це класична «ретроградна» схема з чергою. Спочатку позначаємо для всіх вершин із 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).