Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-03-29 14:46:24.
Revizia anterioară   Revizia următoare  

Soluţii ONIS 2015, Runda 2

Secv10

Se calculeaza o dinamica d[i] = de cate ori se potriveste sirul st in primele i+|st|-1 litere din S folosing KMP sau hash-uri.
Pentru o pozitie i din S unde incepe o potrivire a sirului dr se adauga la solutie d[min(i + |dr| - |st| + 1, i)].
Complexitatea este O(N) pe test.

Cupa Berii

Formal problema ne da M intervale intre O si N si ne intreaba cate intervale [L,R] exista, astefel incat exista un interval x,y din cele date initial astfel incate L = x si y <= R daca x < y sau L <= x si y = R daca x > y(deci standul de bere se afla pe intervalul de intoarcere).
Pentru fiecare pozitie i vom calcula Rt[i] cel mai mic interval care incepe aici si se termina in dreapta, analog vom calcula St[i] pentru intervalele aflate la intoarcere.

O solutie in N^2 consta in a verifica pentru fiecare pereche L,R daca se indeplineste conditia mentionata mai sus.

Pentru a obtine o solutie NlogN vom folosi arb de intervale sau arbori indexati binari.
Intai adaugam toate intervalele [X,Dr[x]], [X,Dr[x]+1]...,[X,N] pentru orice interval X Y cu X < Y(practic posiblitatiile de a bea nr maxim de beri fix la plecare. O(N)
Apoi vom aduaga toate intervalele X,Z pentru care Z<Dr[x] si ST[z] >= X.
Vom sorta intervalele de intoarcere dupa capatul din Stanga.
Vom face arb[x] = 1 pentru toate pozitile x unde incepe un interval x y cu x > y.(n * log n pe operatie)
Apoi vom parcurge toate pozitile de la stanga la dreapta si vom face urmatoare 2 operatii:
add_total += sum(i, dr[i]-1) (unde dr[i] va fi N+1 daca nu exista nici un interval x y cu x < y care sa inceapa din x
Arb[x] = 0 pentru toate pozitiile x care au st[x] = 1.

Fiecare element e introdus si eliminat o singura data in arbore, de asemenea avem n queriouri. Complexitatea totala este N log N + M(citirea)
Daca a gasit cineva o solutie O(N) este rugat sa anunte comisia :)

Tic Tac

O observaţie care ne duce către rezolvarea problemei este aceea că în cazul unui ceas analogic în care indicatorul orei se miscă continuu, ne putem da seama de timpul exact (atât ora cât şi minutul) doar uitându-ne la poziţia indicatorului orei.

De exemplu, dacă acesta este situat fix deasupra unui marcaj al unei ore (să spunem ora H), atunci ora exactă va fi H:00. În schimb, dacă indicatorul este situat la jumătatea distanţei dintre ora H şi ora H + 1, atunci ora exactă va fi H:30.

Având în vedere că indicatorul orei ne poate spune exact ce oră este, mai rămâne doar să verificăm dacă indicatorul minutelor ne arată numărul bun de minute. Mai precis, rămâne să verificam dacă următoarea condiţie se respectă:

  • h - ([h / 30] * 30) = m / 12.

Nk

Comoditate

Sir7

Una din cele mai importante observatii este ca sirul final o sa arate cam asa:
x x ... x x m y y ... y y
unde x e elementul minim, y e maxim si m e un numar intre x si y. Nu are rost sa existe mai mult de 3 valori diferite in sir, demonstratia este urmatoarea
Presupunem ca exista valorile a < b < c < d, cu suma patratelor a2 + b2 + c2 + d2 = S. Daca luam sirul a <= b - 1 < c + 1 <= d vom avea suma
a2 + b2 - 2b + 1 + c2 + 2c + 1 + d2 > S deoarece 2c > 2b din restrictia a < b < c < d => al doilea sir are suma patratelor mai mare, desi suma elementelor a ramas aceeasi. Se poate extinde aceasta demonstratie pentru a arata ca in sir sunt maxim 3 valori diferite.
Se poate cauta binar diferenta dintre elementul maxim si cel minim. Pentru a verifca daca exista un sir care respecta proprietatile cu diferenta fixata se fixeaxa de cate ori apare elementul minim si se calculeaza care este acesta.
Fie x elementul minim si i de cate ori apare. Acum au ramas 2 cazuri:
1) Exista un element m in sir intre x si y -> suma patratelor elementelor = i * x2 + m2 + (n - i - 1) * (x + dif)2^ .
2) In sir sunt doar elemente x sau y -> suma patratelor elementelor = i * x2 + (n - i) * (x + dif)2^
Daca in cel putin un caz suma este mai mare ca Smin inseamna ca exista un sir in care diferenta dintre elementul maxim si cel minim este dif.
Complexitatea totala este O(N * log(Smax)) pe test.

Tempest

Zapezi2

Mafia

Probabilitatea sa se aleaga M numere astfel incat X sa apara cel putin o data se poate calcula ca 1 - probabilitatea ca X sa nu apara printre cele M numere.
Probabilitatea ca X sa nu apara este C(S - vx, M) / C(S, M) , unde S = v1 + v2 ... + vn iar C(n, k) = combinari de N luate cate K, care se simplifica in
(S - vx - M + 1) * (s - vx - M + 2) * ... * (S - M) / ((S - vx + 1) * (S - vx + 2) * ... * S). Aceasta formula se poate calcula in O(N + vx) pe test.

Desenand Stele

Folosind razele initiale, construim un max-heap care reţine valorile unghiurilor. Apoi la fiecare pas, extragem unghiul maxim, calculam unghiul-jumatate, stergem din heap unghiul maxim, si adaugam in heap de doua ori unghiul jumatate. La final, unghiul maxim va fi solutia. Complexitatea spatiu asteptata este O(R + P), deoarece structura de date heap poate fi implementata ca un vector care ocupa O(R + P) spatiu. Complexitatea timp asteptata este O(R + P log(R + P)), unde operatia de constructie a structurii de date heap (heapify) cu cele R unghiuri initiale are complexitatea , iar o operatie de partitionare din cele P are complexitatea O(log(R + P)). Problema poate fi rezolvata si folosind direct structuri de date din biblioteca STL care pastreaza aceleasi complexitati timp si spatiu.