„Labākais algoritms pasaulē”: binārā meklēšana un IOI zelts

Mans treneris Sergey Melnik — patiešām labs skolotājs — nemitīgi uzstāja uz vienu algoritmu. Atcerieties šo, viņš mums teica, tas ir labākais no visiem: tas atrod atbildi precīzi, vienmēr strādā un ir ātrs. Tā bija binārā meklēšana — variants, kas atrod pašu kreisāko pozīciju:

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

Es to ne tikai iemācījos no galvas — es tajā iemīlējos un parūpējos, lai precīzi saprastu, kāpēc tas strādā un kur ir tā robežas. Tieši tur lielākā daļa cilvēku binārajā meklēšanā kļūdās: par vienu garām, bezgalīgs cikls, ne tā puse no meklējamā.

Starptautiskajā informātikas olimpiādē 2002. gadā uzdevums Two Rods prasīja tieši to. Režģī ir paslēpti divi stieņi — viens horizontāls, otrs vertikāls —, un tos var atrast, tikai jautājot, vai taisnstūrī ir kāda to daļa. Risinājums ir binārā meklēšana vairākas reizes pēc kārtas: vienā virzienā un otrā, pa rindām un pēc tam pa kolonnām. Par to es saņēmu tīrus 100 punktus.

Jonginā, Korejā, 2002: trīs no četriem Latvijas komandas dalībniekiem — Alexander Belov, Sergey Kozlovich un es (pa labi).

Olimpiādē varēja pasūtīt savu programmu izdrukas, lai sēdētu un domātu ar papīru un pildspalvu. Es pasūtīju šī risinājuma izdruku, uzrakstīju uz tās „Paldies, Sergey Melnik, par šo algoritmu, ko mēs mācījāmies”, atvedu to mājās uz Rīgu un uzdāvināju viņam.

Divdesmit gadus vēlāk es to joprojām publicēju ar vienu parakstu: best algorithm ever.

Atpakaļ Rīgā: pieņemšana Latvijas olimpiāžu medaļniekiem pēc IOI 2002.

2002: Rīgas mēra Gundara Bojāra apsveikums.