S-a consumat si al patrulea act al bataliei si odata cu el si etapa on-line a concursului preONI. S-a tras linia si s-au desemnat "fericitii calificati in runda finala":http://infoarena.devnet.ro/clasament/preoni2006.php (atentie! verificarea inca nu a fost facuta, dar cu asta ne vom ocupa in urmatoarea perioada).

Aruncandu-ne ochii pe clasamentele Rundei 4, constatam ca participantii au tras tare pe ultima suta de metri vrand sa ne contrazica previziunile sumbre dupa Runda 3. Desi nivelul de dificultate al problemelor a fost un pic mai scazut fata de runda precedenta, concurentii s-au dovedit mult mai conectati la concurs - suspectam ca apropierea olimpiadelor ar fi cauza. Asadar am avut punctaje aproape maxime (275, 255) obtinute in viteza maxima de primii doi clasati la clasa a 9-a - $Bogdan Tataroiu$ si $Sima Mihai Cotizo$, un punctaj maxim la clasa a 12-a realizat de $Costea Andrei$ care a reusit, dupa un start mai putin reusit in rundele precedente, sa treaca la pas pe langa ceilalti info-atleti, unii dintre ei deja nume mari. De data aceasta, concurentii de la clasa a 10-a nu s-au lasat mai prejos fata de celelalte grupe de varsta si, avand un set clar mai usor decat precedentul, au adunat in ritm de maraton punctaje frumoase care au atins si depasit limita (legal admisa) de 200. Felicitari pentru aceasta realizare lui $Vlad Dumitriu$ si $Bogdan Stoica$. In concluzie, am asistat la un concurs bine organizat (felicitari comisiei!) si la un sprint de sanatate din partea concurentilor (felicitari mai ales lor!) care ne-au convins inca o data ca tinerii nostri sunt pregatiti sa fuga mancand pamantul pentru gloria si renumele olimpiadelor nationale si internationale.

Aruncandu-ne ochii pe clasamentele Rundei 4, constatam ca participantii au tras tare pe ultima suta de metri vrand sa ne contrazica previziunile sumbre dupa Runda 3. Desi nivelul de dificultate al problemelor a fost un pic mai scazut fata de runda precedenta, concurentii s-au dovedit mult mai conectati la concurs - suspectam ca apropierea olimpiadelor ar fi cauza. Asadar am avut punctaje aproape maxime $(275, 255)$ obtinute in viteza maxima de primii doi clasati la clasa a 9-a - $Bogdan Tataroiu$ si $Sima Mihai Cotizo$, un punctaj maxim la clasa a 12-a realizat de $Costea Andrei$ care a reusit, dupa un start mai putin reusit in rundele precedente, sa treaca la pas pe langa ceilalti info-atleti, unii dintre ei deja nume mari. De data aceasta, concurentii de la clasa a 10-a nu s-au lasat mai prejos fata de celelalte grupe de varsta si, avand un set clar mai usor decat precedentul, au adunat in ritm de maraton punctaje frumoase care au atins si depasit limita (legal admisa) de $200$. Felicitari pentru aceasta realizare lui $Vlad Dumitriu$ si $Bogdan Stoica$. In concluzie, am asistat la un concurs bine organizat (felicitari comisiei!) si la un sprint de sanatate din partea concurentilor (felicitari mai ales lor!) care ne-au convins inca o data ca tinerii nostri sunt pregatiti sa fuga mancand pamantul pentru gloria si renumele olimpiadelor nationale si internationale.

Una peste alta, s-a incheiat o etapa frumoasa a concursului in care am pus mult suflet. Normal, pot fi doar 30 de participanti fericiti de rezultate. Ii felicitam pe cei calificati si abia asteptam sa-i vedem in finala. Ii felicitam si pe ceilalti care nu au putut sa-si tina suflul pana in final, pierzand locurile calificabile. Noi le uram cat mai multe succese, sa mai alerge vreo cateva sute de probleme (incepand cu cele din Arhiva noastra) si sa ne intalnim cu ei mult mai pregatiti la startul urmatorului preONI.

Al doilea pas este sa observam ca daca aflam pentru fiecare $T{~i~}$, $B{~i~}$ astfel incat $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$ atunci $B$ (numarul cautat in problema) este maximul dintre $B{~i~}$. Implicatia imediata e ca putem sa ne ocupam de fiecare numar prim in parte fara sa tinem cont de celelalte.

Al treilea pas consta in determinarea $B{~i~}$-urilor cu ajutorul cautarii binare. Pentru o valoare candidata $X$ (din cautarea binara) trebuie sa calculam puterea lui $T{~i~}$ in descompunerea lui $X!$. Acest lucru se afla simplu ca fiind $[X/T{~i~}] + [X/T{~i~}^2^] + ... (unde prin @[x]@ intelegem partea intreaga a lui $x$). Cautarea binara se poate optimiza observand ca $B{~i~}$ este intotdeauna divizibil cu $T{~i~}$, ba mai mult nu va fi mai mare decat $(R{~i~} * Q) * T{~i~}$ (observatie necesara obtinerii punctajului maxim). In concluzie, vom cauta binar o valoare intreaga $K$ in intervalul $[1, R{~i~} * Q]$ astfel incat $B{~i~} = K * T{~i~}$ sa aiba propietata ca $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$. Va puteti intreba de ce putem cauta binar. Este simplu: daca o valoare $X$ are propietatea ca $X!$ se divide la $Y$ (unde lui $X$ si $Y$ le putem da semnificatiile dorite de noi) atunci, evident, si $(X + 1)!$ se divide la $Y$.

Al treilea pas consta in determinarea $B{~i~}$-urilor cu ajutorul cautarii binare. Pentru o valoare candidata $X$ (din cautarea binara) trebuie sa calculam puterea lui $T{~i~}$ in descompunerea lui $X!$. Acest lucru se afla simplu ca fiind $[X/T{~i~}] + [X/T{~i~}^2^] + ...$ (unde prin $[x]$ intelegem partea intreaga a lui $x$). Cautarea binara se poate optimiza observand ca $B{~i~}$ este intotdeauna divizibil cu $T{~i~}$, ba mai mult nu va fi mai mare decat $(R{~i~} * Q) * T{~i~}$ (observatie necesara obtinerii punctajului maxim). In concluzie, vom cauta binar o valoare intreaga $K$ in intervalul $[1, R{~i~} * Q]$ astfel incat $B{~i~} = K * T{~i~}$ sa aiba propietata ca $B{~i~}!$ se divide la $T{~i~}^Ri * Q^$. Va puteti intreba de ce putem cauta binar. Este simplu: daca o valoare $X$ are propietatea ca $X!$ se divide la $Y$ (unde lui $X$ si $Y$ le putem da semnificatiile dorite de noi) atunci, evident, si $(X + 1)!$ se divide la $Y$.

Solutia finala va avea complexitatea $O(√P * log Q * log Q)$. Exista o serie de solutii intermediare care permiteau obtinerea de punctaje suficient de mari si de aceea problema a fost considerata medie desi rezolvarea completa este destul de dificila.