FMI No Stress 4 - Solutii

• Lista de probleme
• Pariuri
• Beri
• Palin3
• Melodii
• Plicuri
• Camionas
• Frumoasa
• Autobuze
• Dtcsu
• Peluza Sud
• Peluza Nord

Pariuri

Solutia 1: O(N * M + MAXT) - 80 puncte

Avand in vedere ca pentru 80% dintre teste, momentele de timp in care se pariaza erau ≤ 10⁶, puteam retine un vector auxiliar astfel:

• s[i] = suma de bani castigata in total de catre cei N oameni la momentul de timp i

Printr-o simpla parcurgere a perechilor de tipul (timp, bani) din fisierul de intrare, vom actualiza suma de bani astfel:

• s[timp] = s[timp] + bani;

De asemenea, este nevoie sa marcam undeva si momentele de timp in care s-au facut pariuri, pentru a sti exact ce momente de timp sa afisam. Astfel, parcurgand cu un contor i momentele de timp de la 1 la 10⁶, daca i este marcat, vom afisa i si s[i].

Solutia 2: O(N * M) - 100 puncte

Bazandu-ne pe acelasi principiu ca si cel anterior, constatam ca putem retina o tabela de dispersie / tabela hash pentru toate momentele de timp in care s-a pariat. Pentru fiecare moment de timp vom retine in hash valoarea de bani castigata de cei N oameni. In final, vom afisa doar momentele de timp care exista in hash.

Beri

Solutia 1: O(N log N) - 50 puncte

Avand in vedere ca pretul celor N beri scade cu cate un leu pe minut, este evident ca ordinea acestora in functie de pret va ramane neschimbata la orice moment de timp (daca berea i este mai scumpa decat berea j la momentul 0, atunci berea i va fi mai scumpa decat berea j si la orice alt moment de timp). Vom construi vectorul C[i] dupa formula din enunt:

• C[i] = ( C[i-1] * X + Y ) % Z + K

Din formula de mai sus, reiese foarte usor faptul ca C[i] >= K, pentru orice i intre 1 si N. Deci, stim sigur ca dupa K minute, pretul tuturor berilor este inca pozitiv. In continuare, vom sorta crescator numerele si vom retine suma ultimelor K pe care o vom nota cu S, acestea fiind cele mai scumpe beri la toate momentele de timp. Stim ca pretul berilor scade cu cate un leu pe minut, deci Gapdan va plati prima bere integral, pentru cea de-a doua bere va plati cu 1 leu mai putin, pentru cea de-a treia va plati cu 2 lei mai putin, ..., pentru cea de-a K-a bere va plati cu K-1 lei mai putin. In concluzie, raspunsul va fi:

• S - (1 + 2 + ... + K - 1) = S - (K - 1) * K / 2

Solutia 2: O(N) - 100 puncte

Bazandu-ne pe aceeasi idee ca si la solutia anterioara, ne dam seama ca avem nevoie sa stim care sunt cele mai scumpe K beri, dar nu avem nevoie de ele intr-o ordine fixa. De aceea, putem aplica algoritmul de pivotare Quick-Sort pentru gasirea celui de-al (N-K+1)-lea element in ordine crescatoare, problema cunoscuta si sub numele Statistici de ordine.

Palin3

Solutie: O(N³) pe fiecare din cele T teste, unde N este lungimea sirului

Vom rezolva fiecare test in parte, separat. Notam sirul pentru care dorim sa verificam proprietatea cu s, iar lungimea acestuia cu N. Vom considera ca elementele sirului sunt asezate pe pozitiile 0, 1, 2, ..., N-1. Vom folosi notatia i->j pentru secventa caracterelor de pe pozitiile i, i+1, ..., j.

Folosind metoda programarii dinamice, vom construi o matrice auxiliara D, avand urmatoarea semnificatie:

• D[i][j] = 1, daca secventa i->j poate deveni nula prin eliminari succesive de palindroame de lungime 3.
• D[i][j] = 0, daca secventa i->j nu are proprietatea de mai sus.

Vom initializa matricea noastra cu 0 pentru toate valorile lui i si j. Vom actualiza mai intai dinamica pentru secventele palindrom de lungime 3 existente in sirul nostru. Este evident ca o secventa de lungime 3 este de tip palindrom daca primul element al secventei este egal cu ultimul. Deci, o metoda simpla de a actualiza dinamica pentru secventele de lungime 3 este:

for ( int i = 0; i < n - 2; ++i )
    if ( s[i] == s[i + 2] )
        d[i][i + 2] = 1;

In continuare, va trebui sa actualizam dinamica si pentru secventele de lungime mai mare decat 3. Vom face acest lucru bazandu-ne pe urmatoarea afirmatie: O secventa i->j este o secventa ce respecta proprietatea daca se respecta cel putin una din urmatoarele proprietati:

• s[i] = s[j], si exista un k, i ≤ k ≤ j, astfel incat atat secventa i+1->k-1, cat si secventa k+1->j-1 respecta proprietatea din enunt. In acest caz, secventa i->j poate deveni nula, eliminand secventa i+1->k-1, secventa k+1->j-1, pentru ca in continuare sa eliminam si secventa formata din caracterele s[i], s[k], s[j].

• Exista un k, i ≤ k ≤ j, astfel incat atat secventa i->k, cat si secventa k+1->j respecta proprietatea din enunt. In acest caz, secventa i->j devine nula prin eliminarea acestor doua secvente.

Folosindu-ne de observatiile de mai sus, vom parcurge toate lungimile sirurilor pentru care trebuie sa actualizam matricea noastra, iar pentru fiecare lungime, vom seta capatul din stanga, i, capatul din dreapta va fi i + lungime - 1, si vom plimba indicele k intre aceste doua capete.

for ( int len = 4; len <= n; ++len ) // Parcurgem lungimile sirurilor de la 4 la n
    for ( int i = 0; i < n; ++i ) // Setam capatul din stanga
        if ( i + len - 1 < n ) { // Daca capatul din dreapta nu depaseste ultimul element al sirului
            int j = i + len - 1; // Retin capatul din dreapta in variabila j
            if ( s[i] == s[j] ) { // Daca elementele din capete sunt egale
                int k = i + 1; // Setez indicele din mijloc
                while ( k < j && !d[i][j] ) // Cat timp indicele nu depaseste intervalul si nu am gasit nici solutie
                    if ( d[i + 1][k - 1] && d[k + 1][j - 1] ) // Daca cele 2 secvente sunt bune
                        d[i][j] = 1; // Si secventa curenta este buna
            }

            if ( !d[i][j] ) { // Daca nu am setat pana acum secventa curenta ca fiind buna
                int k = i; // Setez indicele din mijloc
                while ( k < j && !d[i][j] ) // Cat timp indicele nu depaseste intervalul si nu am gasit nici solutie
                    if ( d[i][k] && d[k + 1][j] ) // Daca cele 2 secvente sunt bune
                        d[i][j] = 1; // Si secventa curenta este buna
            }
        }

In final, daca d[ 0 ][ n - 1 ] are valoarea 1, vom afisa DA. Altfel, vom afisa NU.

P.S. Cel mai probabil, va trebui sa aveti grija de un mic caz special, dar va descurcati voi!
P.P.S. Este evident ca este necesar sa verificati doar palindroamele de lungime 3, dar acest lucru nu va afecta complexitatea foarte mult.

Melodii

Solutii prezentate de Cristian Lambru •maritim.

Problema se poate reformula matematic in modul urmator:

• Care este numarul de posibilitati de a scrie numarul N ca suma de 1 si 2?

Genul acesta de probleme care cer numarul de posibilitati de a se intampla un eveniment ce este reprezentat in input printr-o singura valoare se rezolva in general prin doua moduri. Problema de fata se poate rezolva prin ambele abordari:

• Se genereaza (de mana, sau se creeaza un mic programel, eventual cu backtracking) rezultatele pentru date de intrare mici si se incearca gasirea unei relatii de recurenta sau a unei formule in functie de indexul valorii in sir. In acest caz sirul rezultat este urmatorul (fara modulo) - 1 2 3 5 8 13 21 34 55 89 ... Pentru cei care nu cunosc acest sir, acesta se numeste sirul lui Fibonacci si are aplicabilitati in matematica si informatica deopotriva.

• Se incearca gasirea unei recurente folosind metoda programarii dinamice. In acest caz recurenta este in felul urmator: numarul de moduri de a scrie N ca suma de 1 si 2 este numarul de moduri de a scrie N-2 la care se adauga valoarea 2 la final pentru fiecare mod posibil + numarul de moduri de a scrie N-1 la care se adauga valoarea 1 la final. In acest mod se acopera toate solutiile posibile si nu se amesteca intre ele. Matematic vorbind recurenta arata in felul urmator : Best[i] = Best[i-2] + Best[i-1]. Se observa din nou ca aceasta recurenta corespunde sirului lui Fibonacci.

In acest mod am redus problema la a afla rapid care este al N+1-lea termen din sirul lui Fibonacci. Spunem al N+1-lea termen deoarece sirul lui Fibonacci incepe cu valorile 1 1 2, iar sirul nostru incepe cu 1 2 3.

Vom descrie in continuare 5 solutii cu timpi de executie diferiti, dar care rezolva corect problema.

Solutia 1: O(N*2^N) pe fiecare din cele T teste - 10 puncte

Se genereaza cu backtracking fiecare secventa posibila de a scrie valoarea N ca suma de 1 si 2 si se numara aceste secvente.

Solutia 2: O(N) pentru fiecare din cele T teste - 30 puncte

Se calculeaza pentru fiecare din cele T teste al N+1-lea termen Fibonacci.

Solutia 3: O(MaxValue) - 50 puncte

Se preproceseaza sirul lui Fibonacci pana 1 milion si se raspunde in O(1) la fiecare din cele T teste.

Solutia 4: O(log(N)) pe fiecare din cele T teste - 70 puncte

Se foloseste ridicarea la putere in timp logaritmic a matricei ((0,1),(1,1)), asa cum este prezentat in articolul acesta: Al k-lea termen Fibonacci.

Solutia 5: O(R + T) - 100 puncte

Sirul lui Fibonacci este periodic modulo un numar natural. Se calculeaza perioada pentru valoarea R si apoi se genereaza sirul lui Fibonacci pana la acea perioada. Vom nota valoarea perioadei cu PER. Raspunsul pentru un numar N va fi a ((N+1)%PER)-a valoare din sirul lui Fibonacci.

Pentru modul in care putem calcula perioada ne uitam de exemplu la ultima cifra a numerelor din sir (adica modulo 10) si putem observa ca momentul in care incep numerele sa se repete este cand apar valorile 0 si 1 alaturate in sir. Astfel putem genera sirul lui Fibonacci modulo R pana cand gasim valorile 0 si 1 alaturate. Perioada pentru valoarea R nu va depasi niciodata valoarea 4*R, pentru orice R numarul natural.

Plicuri

Solutie: O(N * log N) - 100 puncte

Stim ca un plic i poate fi introdus intr-un plic j daca este adevarata una din urmatoarele conditii:

• L[i] < L[j] si W[i] < W[j]
• L[i] < W[j] si W[i] < L[j]

Cu alte cuvinte, putem spune ca un plic i poate fi introdus intr-un plic j daca este adevarata conditia:

• min(L[i], W[i]) < min(L[j], W[j]) && max(L[i], W[i]) < max(L[j], W[j])

Astfel, ca sa ne fie mai usor sa "comparam" doua plicuri in functie de dimensiunile acestora, vom retine pentru fiecare plic i, dimensiunea mai mica a sa in L[i], iar cealalta dimensiune in W[i]. Acum putem spune ca un plic i poate fi introdus intr-un plic j daca:

• L[i] < L[j] && W[i] < W[j]

Problema ne cere sa aflam lungimea maxima K a unui subsir de plicuri, astfel incat primul plic sa incapa in al doilea, al doilea in al treilea, ..., al K-1-lea in al K-lea. Intuitiv, aceasta cerinta ne duce cu gandul la un algoritm de tipul subsir crescator maximal. Pentru a aplica insa acest algoritm in cazul de fata, trebuie sa avem plicurile intr-o ordine convenabila. Vom sorta plicurile crescator dupa dimensiunea L a acestora, iar in caz de egalitate, descrescator dupa dimensiunea W. Astfel, pentru oricare doua plicuri i si j, cu i < j, vom avea doua cazuri:

• L[i] < L[j], deci este suficient sa comparam dimensiunea W ca sa ne dam seama daca plicul i poate fi introdus in plicul j.
• L[i] = L[j], deci W[i] > W[j], datorita conditiei de sortare in caz de egalitate. Deci este suficient sa comparam doar dimensiunea W a plicurilor pentru ne da seama ca plicurile nu pot fi introduse unul in celalalt.

Asadar, avand plicurile sortate dupa acest criteriu, pentru oricare doua plicuri i si j, este suficient sa comparam W[i] si W[j] pentru a ne da seama daca plicurile pot fi introduse unul in celalalt. In concluzie, putem aplica algoritmul de determinare a subsirului crescator maximal pe vectorul dimensiunii W a plicurilor, afisand lungimea determinata. Acest algoritm este explicat in detaliu la acest link: Scmax.

Camionas

Solutii prezentate de Teodor Plop •Teodor94.

Solutia 1: O(M * log N) - 100 puncte

Basmul poate fi privit ca un graf orientat cu N noduri si M muchii, in care fiecare muchie are o rezistenta si se garanteaza ca exista cel putin un drum intre nodul 1 si nodul N.
Rezistenta unei muchii trebuie marita doar daca aceasta este mai mica strict decat greutatea camionasului. Deci, raspunsul problemei este numarul minim de muchii cu rezistenta strict mai mica decat G prin care este nevoit camionasul sa treaca, mergand din nodul 1 si oprindu-se in nodul N. Astfel, putem atribui costuri muchiilor astfel:

• O muchie i are costul 1, daca rezistenta ei este mai mica strict decat greutatea camionasului (g _i < G).
• O muchie i are costul 0, daca rezistenta ei este mai mare decat greutatea camionasului (g _i >= G).

In concluzie, problema se reduce la gasirea drumului de cost minim intre nodul 1 si nodul N. O solutie este un algoritm de tip Dijkstra.

Solutia 2: O(M + N) - 100 puncte

Bazandu-ne pe aceeasi observatie ca si la solutia anterioara, putem identifica componentele conexe din graful initial, folosind doar muchiile ce au cost 0. Astfel, putem crea un nou graf, avand ca noduri componentele conexe identificate. Apoi, vom trage muchiile ce au cost 1 pentru a uni aceste componente conexe intre ele. Deci, problema se reduce acum la gasirea unui drum de lungime minima intre componenta conexa in care se afla nodul 1 si cea in care se afla nodul N. Aceasta lungime minima se gaseste foarte usor cu o parcurgere in latime.

Frumoasa

Solutii prezentate de Dragos-Alin Rotaru •mathboy.

Solutie 1: O(N) - 40 puncte

In mod evident, atunci cand P >= 26 raspunsul va fi 0, deoarece avem doar 26 de caractere la dispozitie si aranjand literele in cel mai rau caz abc...z, nu mai avem o a 27-a litera pentru a o adauga la sfarsit. Prin urmare, vom considera doar cazul in care P < 26:

Pe prima pozitie putem pune 26 de litere, pe a 2-a pozitie putem pune orice litera in afara de cea de pe prima pozitie, in total 25; Momentan putem avea 26 * 25 de siruri de lungime 2; Pe a 3-a pozitie putem pune orice litera, excluzandu-le pe cele de pe primele 2, deci (26 - 2) = 24; etc. Observam rationamentul: pe a i-a pozitie putem pune (26 - i + 1) litere, 1 <= i <= min(P, N).

Fie SOL = (P + 1) * (P + 2) * ... * 26

Avand SOL posibilitati de a obtine sirul format din P litere, atunci cand o adaugam pe a (P + 1)-a ne vom asigura doar de faptul ca litera pe care o punem la final sa nu se afle din ultimele P, deci solutia noastra se va actualiza : SOL = SOL * (26 - P); Continuam acest procedeu pana cand completam toate cele N pozitii.

Solutie 2: O(logN) - 100 puncte

Ne vom baza pe acelasi rationament ca si in solutia anterioara. Dupa ce completam primele P pozitii, observam ca inmultim solutia noastra cu (26 - P) de fiecare data. Dupa completarea celor N pozitii, solutia noastra a fost inmultita cu (26 - P) de (N - P) ori. In concluzie, putem calcula (26 - P) ^ (N - P) in timp logaritmic, reducand complexitatea la O(log(N)).

Autobuze

Solutii prezentate de Teodor Plop •Teodor94.

Solutia 1: O(N²) - 50 puncte

Vom considera ca cele N numere sunt nodurile unui graf neorientat, iar fiecare nod i o sa aiba valoarea a[i]. Initial, graful are N noduri si 0 muchii. Pentru fiecare nod i de la 1 la N, vom parcurge toate celelalte N noduri, iar cand gasim un nod j care are proprietatea ca a[i] divide a[j] sau viceversa, vom trage o muchie intre aceste doua noduri i si j. In momentul acesta, problema se reduce la gasirea numarului de componente conexe existente in acest graf. Acest lucru se poate face liniar cu o parcurgere in adancime / latime.

Solutia 2.1: O(N * sqrt( MAX_VAL )) - 70 puncte Teodor Plop •Teodor94

Pe acelasi principiu ca cel al rezolvarii anterioare, putem adauga valoarea tuturor nodurilor intr-o tabela de dispersie / hash, retinand pentru fiecare valoare a[i] adaugata, numarul de ordine al nodului careia ii apartine, si anume i. In continuare vom parcurge valorile tuturor celor N noduri si le vom cauta divizorii in hash. Daca gasim un divizor in hash, vom trage muchie intre nodul curent si nodul din hash care are valoarea divizorului gasit. In acest moment, problema se reduce din nou la gasirea numarului de componente conexe ale grafului.

Solutia 2.2: O(M * log(log M)) + O(N * NR_MAX_DIV) - 100 puncte Teodor Plop •Teodor94

Vom pregenera numerele prime pana la sqrt(MAX_VAL) folosind Ciurul lui Eratosthenes. Vom descompune in factori primi toate valorile celor N noduri. In continuare, vom genera toti divizorii unui numar cu un algoritm de tip backtraking, folosindu-ne de factorii sai primi si exponentii acestora. Astfel, ajungem din nou la ideea solutiei anterioare, continuand rezolvarea in acelasi fel.

Complexitatea preprocesarii numerelor prime este O(M * log(log M)), unde M este sqrt(MAX_VAL), iar complexitatea efectiva a problemei este O(N * NR_MAX_DIV), unde NR_MAX_DIV este numarul maxim de divizori al unui numar.

Solutia 3.1: 80 puncte Duta Vlad •Vman

Adaugam toate numerele intr-un hash, retinand pentru fiecare numar pozitia pe care se afla in vector. Vom considera din nou cele N numere ca fiind nodurile grafului. Parcurgem cele N noduri, iar pentru fiecare valoare, ii vom cauta multiplii in hash folosind un algoritm asemanator cu Ciurul lui Eratosthenes, si vom trage muchie intre nodul curent si nodul gasit in hash. Astfel, ajungem din nou la determinarea numarului de componente conexe ale grafului.

Solutia 3.2: 100 puncte Duta Vlad •Vman

Vom optimiza solutia precedenta. Pentru fiecare nod i din cele N, avem doua optiuni:

• Ii putem cauta multiplii incepand cu 2 * a[i], pana la MAX_VAL, mergand din a[i] in a[i].
• Ii putem cauta multiplii printre valorile celor N noduri.

Astfel, pentru nodurile i pentru care MAX_VAL / a[i] < N, le vom cauta multiplii folosind prima optiune, iar pentru nodurile i pentru care MAX_VAL / a[i] >= N, vom folosi cea de-a doua optiune.

Solutia 4: 100 puncte Heidelbacher Andrei •a_h1926

Putem considera ca fiecare din cele N numere face parte din cate o multime. Astfel, vom avea initial N multimi, fiecare continand cate un element. In continuare vom folosi un algoritm de tipul paduri de multimi disjuncte pentru a uni multimile care au elemente in comun.

Dtcsu

Solutie prezentata de Duta Vlad •Vman.

Solutie: 100 puncte

Datorita limitei de memorie foarte stransa nu putem decat sa incercam sa impartim fiecare numar pe rand la 2, 3, 5, 7, 11 pana cand nu se mai poate, iar daca rezultatul este 1 atunci numaram solutia. Totusi, daca efectuam aceste calcule pentru fiecare numar din input timpul de executie va fi depasit. Ne trebuie asadar o metoda de respingere rapida a numerelor despre care stim sigur ca nu pot fi de forma ceruta, ramanand sa verificam doar numerele care nu au fost respinse, dar pot fi "false positives".

Pornind de la ideea de Bloom Filter, vom construi o tabela de dispersie (hash) in care vom introduce toate cele 276997 numere din fisierul de intrare, urmand ca pentru restul sa verificam daca functia de hash corespunzatoare returneaza true (posibil candidat) sau false (cu siguranta respins). Totodata avem nevoie de o functie (sau mai multe) de hash care sa asigure o rata de respingere de aproximativ 30-40%. Dat insa faptul ca toate cele 276997 valori sunt cunoscute (chiar daca nu sunt date explicit in enunt, ele pot fi generate foarte usor prin backtracking), putem incerca o multime mai mare de functii de hash, iar apoi vom alege acele functii care au rata de respingere cea mai buna.
Aceasta tehnica are aplicatii in baze de date, filtrarea rapida a rezultatelor, url blacklisting, etc.

Pro Tip: Pentru cei care folosesc STL e important de stiut ca atat containerul set cat si map sunt implementati prin arbori rosu-negru si complexitatea per operatie tinde la log(size). Tabelele de hash sunt implementate in librariile unordered_set, respectiv unordered_map. Totusi, in cazul de fata un bitset ar putea fi o solutie mult mai buna dat fiind ca ne este suficient sa setam un bit per intrare, astfel dimensiunea tabelei crescand considerabil.

P.S. E greu sa gasesti un hash bun!

Peluza Sud

Problema are numeroase soluţii care se încadrează în timp. Evident, o secvenţă care constituie un răspuns valid pentru testul maxim este răspuns corect şi pentru orice alt test. Vrem deci să găsim o secvenţă continuă de 30 de numere compuse între 10¹⁴ şi 10¹⁵. O soluţie ar putea fi, spre exemplu, un multiplu comun al primelor 31 de numere naturale, situat în intervalul dorit, dar se pot obţine 100 de puncte şi folosind un algoritm randomizat. Toate aceste soluţii pot fi folosite şi pentru a precalcula răspunsul.

Peluza Nord