Revizia anterioară Revizia următoare
Soluţii Junior Challenge 2012 - runda 2
Sqrt
Soluţie O(K^3) - 60 puncte
Prima observatie este aceea ca daca inmultim numarul nostru X cu 100 si extragem radicalul din el, atunci partea intreaga din acest radical va avea ultima cifra egala cu prima zecimala a numarului sqrt(X). Un exemplu: sqrt(2) = 1.41... iar sqrt(200) = 14.1...... Putem generaliza si zicem ca daca inmultim numarul nostru cu 10^(2*K), atunci partea intraga din radicalul acestui numar va contine ultimile K cifre ca fiind primele K zecimale cautate. Din moment ce precizia nu ne permite sa lucram pe numere reale vom lucra pe numere mari. Practic am redus problema la aflarea radicalului numarului X * (10 la puterea (2 * K)) pe numere mari. O solutie de doar 60 de puncte ar fi sa cautam binar solutia pe numere mari iar la fiecare pas sa facem inmultire pe numere mari. Acest algoritm are complexitate O(K * K) de la inmultirea pe numere mari iar cu O(log2( 10 la puterea (2 * K) )) care este O(2 * K * log2(10)), deci in total cam O(K * K * K) cu constanta aproximativ 6.
Soluţie O(K^2) - 100 puncte
Bazandu-ne pe acelasi principiu dar schimband modul de aflare al radicalului putem scoate o complexitate totala de O(K * K). Daca va aduceti aminte prima lectie despre radicali de la ora de mate atunci ar trebui sa va fie foarte usor sa intelegeti. Sa ne amintim de acel algoritm pe care il foloseam ca sa extragem radicalul pe foaie. Cel mai usor este sa luam un exemplu: sa zicem ca avem sqrt(300). Primul pas era sa grupam cifrele de la dreapta la stanga cate 2 (ultimile 2, urmatoarele 2, si tot asa). In exemplu am avea cele 2 cifre de 0 ca fiind o grupa si prima cifra, cea de 3, ca fiind o alta grupa. Al doilea pas mai amortizat este sa determinam prima cifra a raspunsului care va fi desigur sqrt(3) = 1 (luam partea intraga). Daca prima grupa era sa zicem 36 atunci prima cifra ar fi fost 6. Aceasta cifra va fi prima cifra a catului nostru iar din prima grupa vom scadea aceasta cifra la patrat si vom obtine restul nostru curent. Mai exact dupa cel de al doilea pas catul nostru va deveni 1 iar restul va deveni 3 - 1 * 1 = 2.
De acum vom aplica acelasi algoritm standard: la rest vom adauga inca 2 cifre, care reprezinta defapt urmatoarea grupa care vine la rand. Acum vom incerca sa gasim urmatoarea cifra a catului. Aceasta cifra se determina in felul urmator: se dubleaza catul care sa zicem ca va fi de forma xxxx in final si se cauta cea mai mare cifra y, care respecta proprietatea ca xxxxy * y sa fie mai mic sau egal ca restul. Determinam aceasta cifra y si o adaugam in coada la cat. Din rest desigur vom scadea xxxxy * y si continuam algoritmul. Sa continuam si pe exemplu:
Catul = 1
Restul = 2
Coboram urmatoarea grupa la rest si obtinem:
Restul = 200
Dublul catului este 2 deci vom cauta o cifra y astfel incat 2y * y <= 200. Niste verificari:
25 * 5 = 125 deci 5 este o cifra posibila dar cautam ceva mai mare.
27 * 7 = 189 deci si 7 este o cifra posibila
28 * 8 = 224, nu respecta. Deci urmatoarea cifra a catului este 7
Catul = 17
Rest = 200 - 27 * 7 = 200 - 189 = 11
Daca am mai fi avuta alte cifre am fi continuat sa coboram 2 cifre, dublam catul, cautam noua cifra a catului si actualizam catul si restul.
Complexitatea acestui algoritm este O(K * K) deoarece avem K pasi in care sa determinam cifrele catului iar la fiecare pas avem operatii pe numere mari in O(K) (adunare, scadere, inmultire intre un numar mare si un numar mic). Constanta va fi aproximativ 9 de la cautarea cifrei dar algoritmul in practica se comporta mult mai bine tinand cont ca la inceput catul si restul au putine cifre iar operatiile aproape ca nu se simt.
Hacker3
Soluţie O(N), memorie O(N) - 70 de puncte
Vom porni de la sfarsitul sirului iar la fiecare pas i vom tine o valoare val care va reprezenta timpul minim de a rezolva toate hackurile de la i la N, fara sa conteze ce se intampla cu cele de la 1 la i - 1. Ca sa calculam valoarea val la pasul i avem 2 variante:
- varianta 1: Alegem hackul de tipul A si o sa avem costul a + 2 * val
- varianta 2: Alegem hackul de tipul B si o sa avem costul b + val
La fiecare pas o sa alegem minimul dintre aceste 2 variante iar raspunsul va fi valoarea val de la ultimul pas (pasul 1)
Soluţie O(N * log(N)), memorie O(log(n)) - 100 de puncte
Vom tine o dinamica d[i][j] timpul minim sa rezolvam primele i hackul apeland varianta A de fix j ori.
Recurenta va fi de forma: d[i][j] = minim(d[i - 1][j] + b * (2 la puterea j), d[i - 1][j - 1] + a * (2 la puterea (j - 1)));
Observatia care reduce complexitatea de la O(N * N) la O(N * log(N)) este aceea ca operatia de tipul A nu va fi apelata de mai mult de 50 de ori deoarece raspunsul maxim este N * 2.000.000.000, cazul in care alegem doar operatiile de tipul B
Observatia care reduce memoria de la O(N * log(n)) la O(log(N)) este aceea ca putem tine minte doar ultimile 2 linii de la dinamica.
Bleach
Apeland o strategie greedy obsevam ca optim este ca Ichigo sa se lupte cu cei N inamicii in ordinea crescatoarea a puterii lor. La un pas daca Ichigo are puterea A iar inamicul are puterea B si A >= B atunci puterea lui Ichigo va deveni A + B iar daca A < B atunci puterea initiala a lui Ichigo va creste cu B - A iar puterea lui acum va deveni 2 * B (deoarece acum vor avea putere egala, adica B si va castiga inca pe atat).
Complexitatea acestui greedy este O(N). Singura problema ramasa este cum sortam vectorul.
Soluţie O(N * log(N)), memorie O(N) - 40 de puncte
Sortam vectorul fie cu QuickSort, fie cu MergSort, fie cu sortul din STL.
Soluţie O(N * log(K)), memorie O(K) - 100 de puncte
Observam faptul ca cel mai mic element se afla in primele K + 1 elemente din vector. Putem inlocui sortarea normala cu un HeapSort in felul urmator. La fiecare pas tinem K elemente in heap si actualizam pe pozitia corespunzatoare cel mai mic element din heap. La urmatorul pas mai adaugam un element in heap si continuam algoritmul. Memoria este O(K) deoarece la fiecare pas tinem un heap de maxim K elemente iar complexitatea este O(N * log(K)) deoarece la fiecare pas operatiile se fac pe un array de lungime K. Daca nu tineti un heap si tineti un vector normal avand complexitate N * K obtineti 60 de puncte.
Articol scris de Meditatii Informatica
