Solutii preONI 2008, Runda 2

Iata ca s-a terminat si runda a 2-a a concursului preONI 2008. Concurentii au continuat lupta spre marea finala, fiind pusi de aceasta data in fata unui set mai frumos de probleme, credem noi. Speram ca dificultatile tehnice intampinate la evaluarea surselor nu au umbrit prea mult aceasta runda. Prezentam in continuare solutiile problemelor propuse spre rezolvare, precum si rezumatul celor intamplate pe parcursul concursului.

Ne bucura faptul ca la clasele 5-8 au fost rezolvate corect toate cele 3 probleme. Observam ca se profileaza un nucleu de elevi destul de buni si speram ca multi dintre ei sa reprezinte cu succes Romania la olimpiadele internationale peste cativa ani. In fruntea clasamentului gasim la egalitate 3 elevi, fiecare cu 200 de puncte: Andrei Purice, Radu Zernoveanu si Vlad Gavrila. In spatele lor s-au clasat mai multi concurenti cu cate 140 de puncte, dovada a unui set echilibrat de probleme. In clasamentul general stafeta pentru calificarea la runda finala a fost ridicata destul de sus, insa mai sunt 2 runde in care se pot recupera multe puncte.

De aceasta data, cele mai ridicate punctaje s-au inregistrat la clasa a 9-a. Clasamentul este dominat de Victor Ionescu, care a fost foarte aproape de a obtine punctajul maxim. Dupa un inceput mai timid in prima runda, a recuperat si a trecut pe primul loc si la general. Pe urmatoarele pozitii s-au clasat Vlad Tataranu si Ioana Pandele. Problema usoara, Litere, si cea medie, Nunta, au fost rezolvate corect de mai multi concurenti, insa punctajul maxim la cea grea, Operatii, a fost de 90 de puncte. Oricum, rezultatele au fost pe masura asteptarilor, felicitari!

Nu acelasi lucru s-ar putea spune si despre rezultatele de la clasa a 10-a. Problema usoara, Operatii a fost rezolvata corect de doar 4 concurenti, iar cea medie, Rays de unul singur. Punctajul maxim la problema grea, Multiplu a fost de doar 30 de puncte. Primul s-a clasat Alexandru Tudorica, cu doua probleme rezolvate corect, al doilea, cu o zi mai proasta decat de obicei, Bogdan Tataroiu, iar al treilea Istvan Hevele. Speram intr-o imbunatatire a punctajelor la rundele ce urmeaza.

In fruntea clasamentului de la clasele 11-12 gasim nume binecunoscute. Mugurel Andreica a reusit sa se impuna si de aceasta data, cu 210 puncte, fiind urmat la egalitate de Cosmin Gheorghe si de Paul Baltescu. Implementarile atente la problemele Multiplu si Gather ar fi garantat o pozitie fruntasa. Despre problema grea, Hacker nu avem prea multe de spus. Punctajul cel mai mare ii apartine lui Mugurel, 20 de puncte, iar rezolvarea exponentiala potrivita pentru a intra in timp nu a fost gasita de nimeni.

Ii felicitam pe toti cei care au participat la runda a 2-a si le uram succes mai departe!

Litere

Problema cere de fapt sa se calculeze numarul de inversiuni ale sirului. Numim inversiune o pereche (i, j), cu i < j, iar S[i] > S[j]. Pentru a face acest lucru eficient, vom parcurge sirul, iar la fiecare pas vom numara cate litere mai mari decat litera curenta am intalnit pana acum. Putem sa ne mentinem un vector de frecvente ale literelor, complexitatea algoritmului fiind O(N * Sigma), unde Sigma = 26 - marimea alfabetului.

Grozavesti

Observam ca daca avem la dispozitie o matrice NxN putem aduce orice element pe pozitia (1,1) in cel mult doua interschimbari (una pentru linii si una pentru coloane). Daca elementul minim se afla pe pozitia (i,j) interschimbam linia i si coloana j cu linia 1 si coloana 1. Astfel pentru fiecare x de la 1 la N vom plasa pe pozitia (x,x) cel mai mic element din submatricea avand coltul stanga sus (x,x). Acum problema se reduce la aflarea elementului minim din submatricea avand coltul stanga sus (x,x). Se poate implementa direct acest pas iterand prin toate valorile posibile si se obtine un algoritm de complexitate O(N3). Daca in loc sa ne uitam la toata submatricea, verificam doar valorile de pe diagonala principala din submatrice obtinem complexitatea O(N2), dar acest lucru nu era necesar pentru obtinerea punctajului maxim.

Dusman

Desi la o prima vedere limitele ar putea parea prea mari, problema se rezolva folosind tehnica backtracking. Pur si simplu se genereaza in ordine lexicografica primele K permutari indeplinind conditiile din enunt.

Urmatorul cod reprezinta o implementare simplista si intuitiva a problemei:

void dusman ( int l ) {
    if ( K < 0 ) {
       return ;
    }

    if ( l > N ) {
       if ( --K == 0 ) afis () ;
       return ;
    }

    for ( int i = 1; i <= N; ++i ) {
       if ( X[i] == 0 && A[ sol[l - 1] ][ i ] == 0 ) { // A[x][y] == 1 daca intre x si y exista o relatie de dusmanie
          sol[ l ] = i; 
          X[ i ] = true;
          dusman (l + 1) ;
          X[ i ] = false;
       }
}

Algoritmul merge repede si furnizeaza solutie repede datorita restrictiei ca fiecare vecin are cel mult 3 dusmani.

Ca o optimizare la acest algoritm ca de altfel la majoritatea problemelor care implica generarea permtarilor se pot folosi dancing links, dar acest lucru nu era necesar pentru obtinerea punctajului maxim.

Nunta

Fie FN numarul de moduri de a aseza la masa N perechi. Se observa imediat ca F1 = 1 si F2 = 2. Pentru a calcula FN este necesar sa stim valorile elementelor FN-1 si FN-2. Astfel, pentru o asezare oarecare a primelor N-2 cupluri, putem aseza cea de-a N-a si a (N-1)-a pereche ca in imagine:

In acest caz, avem FN-2 variante de asezare.
Perechea a N-a poate fi asezata si in modul urmator:

In acest caz, avem FN-1 variante de asezare. Numarand astfel putem sti ca nu vom numara aceeasi asezare de mai multe ori. Obtinem relatia de recurenta: FN = FN-1 + FN-2. Rezolvarea problemei se bazeaza deci pe afisarea celui de-al (N+1)-lea numar din sirul lui Fibonacci. Deoarece rezultatul nu se incadreaza in nici un tip de date conventional, trebuie implementata adunarea pe numere mari. De exemplu, al 1000-lea numar Fibonacci are 209 cifre. Operatiile cu numere mari sunt tratate in acest articol. Din considerente de memorie se vor retine la fiecare pas doar ultimele doua numere Fibonacci.

Operatii

Problema admite multe rezolvari si a fost propusa pentru o departajare a concurentilor. Un prim algoritm ar fi selectarea la fiecare pas a secventei de lungime maxima ce contine numai elemente nenule si decrementarea cu o unitate a tuturor elementelor secventei. Procedeul se repeta cat timp exista o secventa cu elemente nenule (cat timp vectorul nu este nul). Deoarece la fiecare pas s-a selectat secventa de lungime maxima, numarul final de operatii va fi minim posibil. Aceasta solutie obtine 20-40 de puncte, in functie de prezenta optimizarilor.
Problema se poate rezolva in complexitate liniara si exista mai multe rezolvari diferite ce au aceasta complexitate. Una din rezolvari este urmatoarea: fie MAX maximul elementelor din vectorul v. Retinem MAX liste, in a i-a lista avand memorate pozitiile din vector pe care apare numarul i. Pornim de la vectorul nul si inseram pe rand numerele 1, 2, ... MAX. Calculam la fiecare pas i numarul de intervale in care impart primele i numere vectorul v, rezultatul final fiind suma numerelor de intervale de la fiecare pas.
De exemplu, pentru vectorul v = (0 1 4 2 4 1 3) se procedeaza in felul urmator: plecam de la vectorul nul cu 7 elemente. Introducem valoarea 0 pe pozitia 1 si s-a format un "interval" cu pozitii care nu au fost inca completate ( pozitiile 2-7 ). Introducem numarul 1 pe pozitiile 2 si 6 si se formeaza 2 intervale: pozitiile 3-4-5 si 7. Introducem elementul 2 pe pozitia 4 si se formeaza 3 intervale, cate un interval pe pozitiile 3, 5 si 7, etc. In final se aduna numarul de intervale de la fiecare pas si se afiseaza rezultatul obtinut. Procedand in acest fel, vom sti sigur ca numarul de operatii folosite este minim: daca la pasul i avem un anumit numar de intervale, aplicam operatia specificata in problema o data pentru fiecare interval.
Ca sa aflam in O(1) la fiecare pas cate intervale avem, tinem un vector caracteristic uz, unde uzi este 1 daca si numai daca numarul de pe pozitia i a fost inserat (marcat). Fie nr_interval numarul curent de intervale. Distingem 4 cazuri:

  • marcam pozitia i, si pozitiile i-1 si i+1 sunt nemarcate => nr_interval creste cu o unitate
  • marcam pozitia i, pozitia i-1 nemarcata si i+1 marcata => nr_interval nu se modifica
  • marcam pozitia i, pozitia i+1 nemarcata si i-1 marcata => nr_interval nu se modifica
  • marcam pozitia i si pozitiile i-1 si i+1 sunt marcate => nr_interval scade cu o unitate

Aceasta solutie este foarte simplu de implementat si obtine 100 de puncte.

O solutie alternativa si cu o implementare mult mai concisa a fost oferita de Bitis Gabriel. Aceasta se bazeaza pe urmatoarea observatie: capetele stangi ale secventelor ce vor fi selectate pentru incrementare vor fi doar acele pozitii cu valoare strict mai mare decat pozitia precedenta. Evident, celelalte pozitii vor fi acoperite de secvente care pornesc mai in stanga. De exemplu, pentru vectorul de mai sus, se vor selecta doar secvente ce incep cu valorile 1, 4, 4, 3. Pentru a afla numarul minim de operatii, vom tine un contor pe care il vom creste de fiecare data cand v[i]>v[i-1] cu valoarea v[i]-v[i-1], pentru fiecare i cuprins intre 1 si N. Conventional v[0]=0. Solutia poate fi optimizata (desi nu este necesar pentru 100 de puncte) pentru a nu retine tot vectorul, ci numai ultimii 2 termeni. Complexitatea obtinuta este O(N).

Multiplu

O rezolvare triviala ar fi generarea (prin metoda backtracking) in ordine crescatoare a tuturor numerelor formate doar din cifre de 0 si 1 si verificarea proprietatii de divizibilitate. In momentul in care am intalnit un numar care este multiplu si pentru A si pentru B afisam rezultatul si oprim executia programului.
Solutia optima are complexitatea O(A*B). Fie M cel mai mic multiplu comun pentru numerele A si B. Trebuie sa determinam cel mai mic numar natural format doar cu cifre de 0 si 1 si care este multiplu pentru M. Vom avea o coada in care vom introduce cele mai mici numere formate cu 0 si 1 care dau un anumit rest la impartirea cu M. Initial, in coada se va afla doar numarul 1. La un moment dat, daca ne aflam pe pozitia i in coada si pe aceasta pozitie se afla numarul X, tratam urmatoarele cazuri:

  • adaugam cifra 0 la sfarsitul lui X. Daca nu exista nici un numar in coada care sa aiba restul (X*10) % M, atunci introducem X*10 in coada.
  • adaugam cifra 1 la sfarsitul lui X. Daca nu exista nici un numar in coada care sa aiba restul (X*10+1) % M, atunci introducem X*10+1 in coada.

In momentul in care introducem in coada un numar care are restul 0 la impartirea cu M, il afisam si oprim executia programului. Se observa ca in coada vor fi introduse cel mult M numere, deoarece exista M resturi posibile la impartirea cu M. Cum M este cel mult A*B, complexitatea acestui algoritm este O(A*B).
Din motive de eficienta, in coada nu vor fi introduse numerele propriu-zis, ci doar resturile acestora la impartirea cu M. Pentru reconstituirea solutiei este necesara retinerea a doi vectori suplimentari up si cif, unde upi indica ultima pozitie de la care s-a plecat pentru a ajunge la pozitia i, iar cifi este ultima cifra (0 sau 1) a numarului de pe pozitia i in coada.

Rays

Pentru fiecare din cele 2 semiplane determinate de axa Oy rezolvam problema si adunam in final rezultatele. Sa presupunem ca vrem sa aflam numarul minim de raze ce trebuiesc proiectate astfel incat sa distrugem toate segmentele verticale cu y > 0. Sortam dupa unghi capetele segmentelor verticale date. Astfel, fiecare segment va avea de fapt asociat un interval "de unghiuri". Daca anumite intervale "de unghiuri" se intersecteaza, atunci poate fi dusa o raza care sa elimine toate segmentele aferente acestor intervale.
Problema se reduce la a determina numarul minim de puncte pentru un set de intervale dat astfel incat fiecare interval sa contina cel putin unul din punctele determinate. Aceasta problema se poate rezolva optim in O(N log N) folosind metoda greedy. Fiecare interval determina doua tipuri de evenimente: "de intrare" (capatul din stanga, mai mic) si "de iesire" (capatul din dreapta, mai mare). Sortam evenimentele pentru toate cele N intervale si realizam o baleiere. In momentul in care ajungem la un punct de intrare, introducem intr-o coada intervalul asociat evenimentului. Atunci cand se intalneste un eveniment de iesire, se aduna 1 la solutie si se goleste coada, fara a mai considera vreodata evenimentele ce apartin unor intervale deja eliminate.

Gather

Vom calcula o matrice A[i][j] - distanta minima ca sa ajungem in celula i urmariti de detinutii care corespund cifrelor de 1 in reprezentarea binara a lui j. De fapt ne vor interesa doar valorile pentru celulele in care se afla detinuti, de aceea vom calcula doar aceste valori.

Pentru calcularea acestor valori vom construi un graf format din noduri de tipul (i,j) unde i este o celula in care se afla un detinut, iar j este un numar intre 0 si 2K. Vom avea muchie de la (i,j) la (t,j+2t) daca t nu apare in reprezentarea binara a lui j si exista un drum de la celula celula i la celula t astfel incat capacitatea minima a muchiilor de pe acest drum sa fie mai mare sau egala decat numarul de biti de 1 din descompunerea lui j(adica numarul de detinuti care il urmaresc pe Gigel). Costurile asociate acestei muchii va fi exact suma costurilor de pe drumul minim de la i la t care respecta conditia respectiva.

Pentru a calcula toate costurile muchiilor noului graf se aplica de k2 ori algoritmul lui Dijkstra. Vom calcula pentru fiecare i de la 1 la k si pentru fiecare j de la 1 la k drumurile minime de la nodul in care se afla detinutul i la toate nodurile folosind doar muchii ce au capcitate mai mare sau egala cu j.

Odata construit noul graf se poate aplica Dijkstra pe el pentru a calcula matricea A, sau se poate folosi programare dinamica datorita aciclicitatii grafului.

Complexitatea finala va fi O( K2*N2 + 2K*K2).

Hacker

Pasul 1

In prima faza vom incerca sa rezolvam problema atunci cand sirul dat este format numai din ? (fie Nr[N] numarul lor pentru o lungime N). Pentru asta avem nevoie de urmatoarea observatie:

  • Fie un sir de lungime N in care exista un prefix egal cu un sufix; fie lungimea acestui prefix/sufix L. Daca 2L > N (prefixul si sufixul se intersecteaza) atunci exista si un prefix egal cu un sufix, de lungime L' < L pentru care 2L' ≤ N (nu se intersecteaza).

Aceasta observatie este destul de evidenta. Lasam demonstratia ei pe seama cititorilor. Vom numi in continuare un sir in care nu exista nici un prefix egal cu un sufix ca fiind bun.

  • Daca avem un sir care nu este bun de lungime impara (N=2k+1), putem elimina elementul din mijloc (de pe pozitia k+1) si obtinem un sir de lungime N-1 care in continuare nu va fi bun (datorita observatiei de mai sus). Treaba este valabila si invers. Putem lua orice sir bun de lungime N-1, inseram orice valoare intre 0 si K-1 in mijloc si va fi in continuare bun. Astfel, Nr[N] = K*Nr[N-1]
  • Putem aplica in mare parte acelasi rationament si pentur sirurile de lungime para (N=2k). Inseram orice valoare pe pozitia k intr-un sir bun de lungime N-1 pentru a obtine siruri de lungime N. Se observa ca in acest caz pot aparea si siruri care nu sunt bune, si anume cele in care exista un prefix de lungime k = N/2 egal cu un sufix. Este evident ca numarul lor este Nr[N/2]. Putem trage concluzia ca Nr[N] = K*Nr[N-1] - Nr[N/2].

Pasul 2

Vom incerca acum sa rezolvam problema initiala plecand de la ce-am descoperit mai sus. Vom nota cu count(S) numarul de siruri bune care se potrivesc cu S (S este un sir de cifre si ?).

  • Consideram un sir S de lungime N = 2k+1. Putem elimina caracterul din mijloc, reducand problema la una de dimensiune mai mica. Daca caracterul eliminat a fost ? vom inmulti rezultatul cu K.
daca S[N/2+1] = '?':
  count(S) = K*count(S[1..N/2]+S[N/2+2..N])
altfel:
  count(S) = count(S[1..N/2]+S[N/2+2..N])
  • Consideram acum un sir S de lungime N = 2k. Ca si pentru cazul de lungime impara putem elimina caracterul din mijloc ca sa reducem la o problema de dimensiune mai mica. Desigur, in acest caz pot aparea si siruri care nu sunt bune, si anume cele in care exista un prefix de lungime k = N/2 egal cu un sufix. Putem determina numarul acestor siruri daca gasim un alt sir de lungime N/2 care sa se potriveasca cu ambele jumtati ale lui S. Vom nota cu intersect(A, B) un sir care se potriveste si cu A si cu B. De exemplu, intersect(?0?1, ??11) = ?011 sau intersect(?0, ?1) = sir vid. Astfel, va trebui sa scadem valorea lui count() pentru intersectia celor doua jumatati ale lui S, reprezentand numarul sirurilor care nu sunt bune.
daca S[N/2+1] = '?':
  count(S) = K*count(S[1..N/2-1]+S[N/2+1..N]) - count(intersect(S[1..N/2], S[N/2+1..N]))
altfel:
  count(S) = count(S[1..N/2-1]+S[N/2+1..N]) - count(intersect(S[1..N/2], S[N/2+1..N]))
intersect(a, b):
  rez = ""
  pentru i = 1, |a|:
    daca a[i] = '?':
      rez += b[i]
    altfel:
      daca b[i] != '?' si b[i] != a[i] returneaza "" // nu exista intersectie
      rez += a[i]
  returneaza rez

Rezolvarea prezentata mai sus se traduce imediat intr-o functie recursiva. Sa vedem cum ar functiona pe un exemplu:
count(0?1?1) = count(0??1)
count(0??1) = K*count(0?1) - count(01) deoarece intersect(0?, ?1) = 01
count(0?1) = K*count(01)
count(01) = 1

Pasul 3

Desi avem acum o modalitate de a rezolva problema este clar ca o implementare directa a functiei recursive duce la o complexitate exponentiala, care ar parea cam mare pentru N = 200. Sa vedem exact cate apeluri se fac pentru count() in cel mai rau caz. Fie C(N) numarul de apeluri recursive pentru un sir de lungime N, in cel mai rau caz.

  • C(2*k+1) = C(2*k)+1
  • C(2*k) = C(2*k-1)+C(k)+1

O scurta evaluarea a acestei functii ne va arata ca pentru N = 200 valoarea C(N) este in jur de 500.000. Cum pentru fiecare apel C(N) se fac O(N) operatii (datorita manipularii sirurilor) putem estima ca algoritmul va face in jur de 100 de milioane de operatii. Asadar, putem spera ca s-ar incadra in timp, si intr-adevar solutia oficiala este implementarea directa a functiei recursive prezentate mai sus. Se poate aplica memoizare pentru a mai optimiza solutia, dar nu era necesar. Chiar si memoizand, rezolvarea este tot exponentiala. Daca aveti cumva o solutie in timp polinomial pentru aceasta problema nu ezitati sa o scrieti pe forum, deoarece nici noi nu stim nici una.