«Лучший алгоритм на свете»: бинарный поиск и золото IOI

Мой тренер Сергей Мельник — очень хороший учитель — прямо настаивал на одном алгоритме. Запомните его, говорил он, он лучше всех: находит точно, работает чётко и быстро. Это был бинарный поиск — вариант, который находит самую левую позицию:

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

Я его не просто выучил — я его полюбил: разобрался, почему он работает и где у него границы. Именно на этом большинство и ошибается в бинарном поиске: плюс-минус единица, бесконечный цикл, не та сторона от искомого.

На Международной олимпиаде по информатике 2002 года ровно этого требовала задача Two Rods («Две палочки»). На сетке спрятаны две палочки — горизонтальная и вертикальная, — и найти их можно, только спрашивая, задевает ли их заданный прямоугольник. Решение — бинарный поиск несколько раз подряд: в одну сторону и в другую, по строкам и по столбцам. Я чётко взял за неё 100 баллов.

Йонъин, Корея, 2002: трое из четырёх участников команды Латвии — Александр Белов, Сергей Козлович и я (справа).

На олимпиаде можно было заказывать распечатки своих программ, чтобы сидеть и думать с бумажкой и ручкой. Я распечатал это решение, написал на нём «Спасибо Сергею Мельнику за этот алгоритм, который мы учили», привёз в Ригу и подарил ему.

Двадцать лет спустя я выложил его с одной подписью: best algorithm ever.

Снова в Риге: приём латвийских призёров международных олимпиад после IOI 2002.

2002 год: поздравление мэра Риги Гундарса Боярса.