Iekavu uzdevums: kāpēc es vienmēr izpildīju treniņuzdevumus līdz galam

2002. gada Latvijas informātikas olimpiādē es biju vienīgais dalībnieks, kas ieguva 100 punktus divos uzdevumos. Progmeistars man par to piešķīra savu speciālbalvu, ko pasniedz par risinājumu kvalitāti, nevis par kopējo punktu summu.

Aiz viena no šiem uzdevumiem slēpās treniņš. Nodarbībā bijām risinājuši uzdevumu par „operāciju ar iekavām”, un olimpiādē gadījās gandrīz tāds pats (par to sīkāk tālāk). Es vienmēr izpildīju treniņuzdevumus līdz galam un biju vienīgais, kas to atrisināja uz maksimālo punktu skaitu. Spēcīgākais skolēns mūsu grupā zaudēja testus laika dēļ: izvadē viņš bija izmantojis +, nevis bitu OR.

Uzdevums saucās „Operācija @” — finālkārtas pirmās dienas trešais uzdevums, 2002. gada 25. marts. Uz cipariem no 0 līdz n (n ≤ 9) ar tabulu ir definēta operācija @. Piemēram, ja n = 2:

 @ | 0 1 2
---+------
 0 | 1 1 0
 1 | 2 1 0
 2 | 1 2 2

Operācija nav komutatīva: 0@1 = 1, bet 1@0 = 2. Tā nav arī asociatīva: (0@1)@2 = 0, bet 0@(1@2) = 1. Tātad tas, kur liek iekavas, maina rezultātu.

Dota virkne līdz 250 cipariem x1x2…xk, un katram t no 0 līdz n jāatbild VAR vai NEVAR: vai iekavas izteiksmē x1@x2@…@xk var salikt tā, lai iznāktu t. Divas sekundes uz testu. Piemēra virknei 11110 atbilde ir VAR, NEVAR, VAR: (1@(1@1))@(1@0) = 0 un (((1@1)@1)@1)@0 = 2, bet 1 iegūt nevar nekādi.

Risinājums ir dinamiskā programmēšana pa nogriežņiem: katram virknes nogrieznim glabā vērtību kopu, ko tas var dot, un garāka nogriežņa kopu būvē no visiem veidiem, kā to sagriezt divos īsākos. Desmit ciparu kopa ir desmit biti, un kopas apvieno ar OR.

Vēlāk tajā pašā gadā sekoja bronza Baltijas olimpiādē Viļņā un zelts Starptautiskajā olimpiādē Korejā, bet par olimpiādēm — Latvijas valdības un Rīgas domes apbalvojumi (tās „Zelta pildspalva”).

Ko es no tā paņēmu: treniņuzdevums, ko izpildi līdz galam, kādu dienu parādīsies eksāmenā.