Soluţii Urmasii lui Moisil 2016

Culegere

Autor: Stefan Negrus

Solutia se rezuma la simularea evenimentelor si a miscarilor lui Snake prin matrice. Trebuie avute in vedere cazurile mai speciale cum ar fi:

● trecerea de la ultima coloana la prima coloana prin deplasare spre Vest
● oprirea simularii atunci cand este mancat un mar ce in mod natural ar fi trebuit sa dispara mai tarziu, au avut loc toate cele E evenimente si dupa disparitia marului nu mai apar alte obiecte
● rotatia sarpelui intr-un patrat 2 × 2 cu 4 schimbatoare
....
.23.
.14.
....

Principala optimizare consta in faptul ca nu este eficient sa parcurgem matricea la fiecare secunda pentru a elimina evenimentele cand acestea sunt programate sa dispara. O solutie ar fi sa citim toate evenimentele si sa tinem trei vectori cu structuri astfel:
1. events - tinem pentru fiecare eveniment valorile x, y, v.
2. start_events - memoram pentru fiecare eveniment secunda st, cand acesta apare, si pozitia evenimentului in vectorul events; acest vector trebuie sortat dupa campul st
3. end_events - memoram pentru fiecare eveniment secunda en, cand acesta dispare, si pozitia evenimentului in vectorul events; acest vector trebuie sortat dupa campul en
Folosind acesti vectori putem procesa toate evenimentele in timp liniar. La fiecare secunda: eliminam toate obiectele care sunt programate sa dispara conform end_events, pozitionam toate obiectele care sunt programate sa apara conform start_events, mutam corpul lui Snake. Complexitate: O(N*logN)

Tromino

Autor: Vlad STOIAN

Se pot face cateva observatii:

  • La fiecare pas, patratul de latura 2K se poate imparti in 4 patrate (cadrane) de latura 2K-1
  • Daca punctele se afla in acelasi cadran, rezolvam aceeasi problema pentru un K-1
  • Daca punctele se afla in cadrane diferite, drumul va trece prin mijlocul patratului

Pornind de la aceste observatii, putem rezolva problema in 2 moduri: recursiv si iterativ.

Varianta recursiva simpla - 60 pct

  • Daca punctele se afla in acelasi cadran, rezolvam recursiv pt K-1
  • Daca punctele se afla in cadrane diferite, calculam recursiv:
    o drumul de la primul punct la mijloc in K-1
    o drumul de la al doilea punct la mijloc in K-1
    o costul de a trece dintr-un cadran in altul (1 atunci cand cadranele sunt alaturate, 2 atunci cand cadranele sunt opuse)

Varianta recursiva optimizata (60 - 100 pct)

Solutia de mai sus poate fi optimizata folosind memoizare pentru a nu calcula de multe ori aceeasi distanta. (~ 60 pct)
O alta optimizare este folosirea formulei explicata mai jos, atunci cand punctele se afla pe diagonala. (~ 100 pct)

Varianta iterativa - 100 pct

Observam ca daca ambele puncte se afla pe diagonala principala (sau secundara), numarul de mutari se poate calcula printr-o formula: |Sr - Fr| + |Sc - Fc|. Astfel, pentru orice K, pentru a calcula distanta de la orice punct, la punctul din dreapta jos, facem urmatorii pasi:

  • Daca punctul se afla in primul cadran, rezolvam pentru K-1
  • Daca se afla in unul dintre celelalte cadrane, incercam sa translatam punctul in primul cadran tinand minte un cost de translatare. Acest cost va reprezenta cati pasi in plus adauga translatarea la drumul curent, si va trebui scazut mai tarziu. Rezolvam pentru K-1

Dupa ce va fi translatat de K ori, punctul va ajunge in (0,0). Deci raspunsul va fi: distanta dintre (0,0) si (2K-1,2K-1) minus suma tuturor costurilor de translatare.

Bilute2

Autor: Cosmin Mihai TUTUNARU.

Fie N numarul de bilute iar S suma tuturor numerelor de pe bilute. Ca sa vedem cum putem grupa bilutele in gramezi, notam cu S1 suma numerelor de pe bilutele din prima gramada si cu N1 numarul de bilute din prima gramada. Analog notam cu N2 si S2 pentru a doua gramada.
Este evident ca:

S1 / N1 = S2 / N2
S1 / N1 = (S-S1)/(N-N1)
S1 * (N-N1)= N1 * (S-S1)
S1 * N - S1 * N1 = S * N1-S1 * N1
S1 * N = S * N1

Practic, trebuie sa gasim toate valorile S1 si N1 pentru care ecuatia de mai sus este adevarata, iar pentru aceste valori S1 si N1 trebuie sa vedem in cate feluri putem obtine suma S1 din exact N1 bilute.

Solutie 40-60 pct

Fie urmatoarea dinamica DP[K][N][S] = in cate feluri se poate obtine suma S din exact N numere folosind doar primele K bilute. Recurenta este destul de evidenta, avand doua cazuri (cazul in care nu folosim biluta K si cazul in care folosim biluta K):

DP[K][N][S] = DP[K-1][N][S] + DP[K-1][N-1][S-V[k]]
Este evident ca nu are rost sa tinem toata matricea, ci doar ultimele doua linii.

Solutie 80-100 pct
Pentru a obtine cele 100 de puncte putem sa folosim urmatoarele optimizari:
● O mare parte dintre valorile din aceasta dinamica sunt 0 si, practic, trecem prin ele degeaba. Pentru a optimiza acest lucru trebuie sa calculam dinamica inainte (gen Bellman Ford)
● Calculam dinamica doar pana la S/2 si N/2, deoarece atunci cand avem S1 > S/2 sau N1 > N/2, putem folosi S-S1 respectiv N-N1.

Fibocel

Autor: Cosmin Mihai TUTUNARU

In primul rand se observa ca ne intereseaza doar primele 8 numere Fibonacci: 1, 2, 3, 5, 8, 13, 21, 34, 55.

Pentru a putea rezolva eficient aceasta problema, se observa ca daca am avea o functie f(x) care returneaza numarul de numere fibocel strict mai mici decat x, atunci raspunsul la un query ar fi f(B+1) - f(A). Evident partea complicata este implementarea functiei f.

Pentru a numara eficient numerele fibocel, putem sa numaram independent cate numere fibocel avem cu 1 bit, apoi cu 2 biti, … (pe rand pentru fiecare dintre cele 8 numere fibonacci).

Ca sa vedeti cum putem face aceasta numarere, explicam mai jos cum calculam numarul de numere fibocel mai mici decat 113 avand exact 5 biti de 1. Numarul 113 are urmatoarea reprezentare binara: 1110001. Avem urmatoarele cazuri (prin X inseamna ca putem avea orice bit iar prin C(N, K) notam combinari din N luate cate K):

0XXXXXX - C(6,5)
10XXXXX - C(5,4)
110XXXX - C(4,3)

Crescator2

Autor: Vlad Tudose

Solutia 1 (20 de puncte):

 Se foloseste metoda backtracking pentru a genera toate sirurile.

Solutia 2 (40 de puncte):

 Se foloseste metoda programarii dinamice.
Fie Pd[v][s] = numarul de siruri crescatoare, cu numere naturale nenule, care au suma s si nu au valori mai mari decat v.
Pentru a calcula Pd[v][s], putem sa iteram dupa numarul de aparitii ale valorii v la sfarsitul sirului. Obtinem relatia de recurenta:
Pd[v][s] = Pd[v - 1][s] + Pd[v - 1][s - v] + Pd[v - 1][s - 2 * v] + ...
Raspunsul la problema este Pd[S]1 + Pd[S]2 + ... + Pd[S][S].
Pentru a optimiza memoria folosita, observam ca avem nevoie sa retinem doar doua linii din matrice la un moment dat (linie curenta si linia precedenta).
Complexitatea timp: O(s^3). Complexitatea memorie: O(s).

Solutia 3 (60 de puncte):

 Putem optimiza solutia precedenta. Pentru a calcula Pd[v][s] luam in calcul doar doua cazuri: folosim valoarea v sau nu.
Avem Pd[v][s - v] siruri care folosesc valoare v si Pd[v - 1][s] siruri care nu folosesc valoarea v.
Obtinem relatia de recurenta: Pd[v][s] = Pd[v][s - v] + Pd[v - 1][s].
O alta metoda de a deduce relatia de recurenta este sa observam ca Pd[v][s - v] = Pd[v - 1][s - v] + Pd[v - 1][s - 2 * v] + ... in relatia de recurenta
de mai sus. Complexitatea timp: O(s^2).

Solutia 4 (100 de puncte):

 Putem descompune un sir crescator cu suma s in doua parti: un prefix cu valori mai mici sau egale cu sqrt(S) si un sufix cu valori strict mai mari decat sqrt(S).
Numarul de siruri crescatoare cu suma s este dat de numarul de moduri de a construi un prefix * numarul de moduri de a construi un sufix.
Pentru a numara prefixele, calculam Pd[v][s] exact ca mai sus dar doar pentru v <= sqrt(S).
Pentru a numara sufixele, observam intai ca lungimea sufixului este cel mult sqrt(S). O alta observatie este ca daca avem un sufix de lungime k si suma s, putem scadea
sqrt(s) din fiecare element si sa obtinem un sir crescator de lungime k si suma s - sqrt(s) * k (exista o bijectie intre cele doua multimi de siruri).
Deci putem calcula Pd2[k][s] = numarul de siruri crescatoare de lungime k, cu numere naturale nenule si suma s.
Pentru a calcula Pd2[k][s] observam ca daca scadem 1 din fiecare valoare a unui sir crescator de lungime k si suma s obtinem un sir crescator cu suma s - k dar care poate sa aiba pe prima pozitie valoarea 0.
Numarul de astfel de siruri care incep cu valoarea 0 este Pd2[k - 1][s - k] iar numarul de siruri care incep cu valoarea 1 este Pd2[k][s - k].
Obtinem relatia de recurenta Pd2[k][s] = Pd2[k][s - k] + Pd2[k - 1][s - k].
Se pot combina rezultatele din matricile Pd si Pd2 pentru a obtine raspunsul la problema.
Complexitatea timp: O(S*sqrt(S)). Complexitatea memorie: O(S).

Diez

Autor: Ştefan NEGRUŞ.

Solutia care implementeaza simularea operatiilor din enunt va trece aproximativ 4-5 teste. Aceasta solutie are complexitatea la inserare si interogare O(lungimea sirului).

O solutie optimizata presupune sa aflam raspunsul la interogari in mod offline.

Tinem toate operatiile in memorie si construim sirul final, dupa ce au loc toate inserarile. Pentru a face asta pornim cu un sir de caractere cu lungimea N + numarul de inserari si initial doar cu caractere ‘#’. Parcurgem operatiile de la sfarsit catre inceput si, pentru fiecare operatie de inserare, cautam al pos-lea caracter ‘#’ in acest sir si punem caracterul corespunzator inserarii pe acea pozitie. Dupa ce procesam inserarile, in sirul nostru de caractere vom avea ‘#’ pe pozitiile unde ar trebui sa fie caracterele din sirul initial, in aceeasi ordine. Printr-o singura parcurgere putem completa aceste pozitii. Sirul obtinut este corect deoarece la fiecare inserare, in modul descris mai sus, caracterul este asezat pe pozitia pe care trebuie sa fie in sirul final. Pentru a gasi al pos-lea ‘#’ in sir putem folosi un arbore indexat binar care sa ne spuna cate caractere ‘#’ sunt in sir pana la o pozitie data. Peste acest arbore trebuie sa facem o cautare binara pentru a gasi pozitia dorita, aceasta fiind relativa.

Acum putem raspunde la interogari in aceeasi maniera. Parcurgem operatiile de la sfarsit catre inceput iar operatiile de inserare vor fi echivalente cu eliminarea caracterelor de pe pozitia respectiva. Pentru a elimina un caracter putem folosi aceeasi optimizare cu arbore indexat binar si cautare binara pe care am folosit-o si la inserari. Pentru a raspunde la interogari putem folosi un arbore de intervale in care in fiecare nod memoram pentru intervalul corespunzator urmatoarele elemente: hash1 - valoare hash doar a caracterelor diferite de ‘#’, hash2 - valoare hash doar a caracterelor diferite de ‘#’, dar diferita de hash1 si cnt - numarul de caractere diferite de ‘#’ din interval. Un aspect important este ca, pentru fiecare interogare, trebuie sa gasim pozitiile corespunzatoare in sirul nostru, acest lucru poate fi rezolvat folosind arborele si cautarea pe care le utilizam la eliminari.

Pentru aceasta solutie, pentru valorile hash1 si hash2 putem reprezenta secventele intr-o baza mai mare decat 26 si memoram rezultatele modulo doua valori mari. Un exemplu concret:

BASE 73
MOD1 1000000007
MOD2 1000000033

Pentru doua teste, daca se mentine o singura valoare hash cu MOD = 264 vor exista coliziuni si astfel raspunsul final va fi gresit.

Pentru a calcula valoarea hash1 intr-un nod vom folosi:
(valoarea hash1 din fiul stang * BASEcnt din fiul drept + hash1 din fiul drept) % MOD1

Ramane doar sa afisam raspunsurile pentru interogari in ordinea initiala.

Complexitate: O(N*log2(N))