Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-02-22 13:10:40.
Revizia anterioară Revizia următoare

Soluţii ONIS 2015, Runda 1

Por Costel şi Azerah

Solutia cea mai la indemana la problema aceasta se bazeaza pe metoda programarii dinamice:
Calculam:

dp[i][0] = numarul de submultimi cu suma numerelor para cu primele i numere din sir
dp[i][1] = numarul de submultimi cu suma numerelor impara cu primele i numere din sir

Cazul de baza:

dp[0][0] = 1 (submultimea vida)
dp[0][1] = 0

Relatia de recurenta:

Daca numarul v[i] este par:
- dp[i][0] = 2 * dp[i-1][1]
- dp[i][1] = 2 * dp[i-1][1]
Daca numarul v[i] este impar:
- dp[i][0] = dp[i-1][0] + dp[i-1][1]
- dp[i][1] = dp[i-1][0] + dp[i-1][1]

Complexitate: $O(N)$

Insa, la o inspectie mai amanuntita a dinamicii sau dupa un rationament combinatoric descoperim ca:

Daca exista numai numere pare in sir, raspunsul este 2ⁿ
Altfel este 2^n-1

Acum, daca ignoram citirea sirului, complexitatea este $O(log N)$

Por Costel şi Algoritmul

Stim ca aloritmul va lua cel putin doua iteratii pentru ca se garanteaza ca exista cel putin o muchie care iese din nodul 1. Pentru ca algoritmul lui Por Costel sa se termine in doua iteratii, trebuie ca doar la prima iteratie sa se produca relaxari ale muchiilor (modificari ale vectorului d). Cand se intra in iteratia a doua trebuie ca in vectorul d sa existe deja valorile drumurilor minime pentru a nu se produce nicio modificare, variabila ok sa ramana cu valoarea 1 si sa nu se mai intre in while a treia oara.

Pentru a rezolva problema sunt necesare niste cunostiinte generale despre problema drumurilor minime intr-un graf, de exemplu, faptul ca reuniunea drumurilor minime din nodul x catre toate celelalte noduri formeaza un arbore (arborele partial al drumurilor minime din x). Observam ca daca muchiile din acest arbore sunt parcurse in ordinea unei parcurgeri din nodul x (DFS sau BFS sau orice fel de parcurgere), drumurile minime se vor propaga complet. Deci solutia este o astfel de ordonare a N-1 muchii care formeaza un arbore partial de drumuri minime din nodul 1 iar restul de @M-N+1 muchii pot fi interclasate cu acestea in orice fel.

Pentru a construi un arbore partial de drumuri minime din nodul 1, trebuie sa aplicam un algoritm de drum minim. O solutie este chiar Bellman-Ford dar acesta are complexitate O(N*M) chiar si daca il codezi mai bine ca Por Costel. Pentru ca muchiile din graf au cost pozitiv, drumurile minime se pot calcula folosind algoritmul lui Dijkstra

Complexitatea: $O(M*logN)$

Testul pe care pica Bellman-Ford:

Muchiile 1 -> 2, 2 -> 3, 3 -> 4... N-1 - > N, toate de cost 1
Muchiile 1 -> 3, 1 -> 5, 1 -> 7....1 ->N-1/N, toate de cost 10

Este nevoie de un shuffle foarte norocos al muchiilor din nodul 1 pentru ca algoritmul sa mearga bine.

Por Costel şi Bujor

Constatarea cheie aici este ca daca inmultim matricele B si P obtinem matricea I cu semnificatia: I[i][j] = total expected winnings pentru Bujor in casino-ul i, in ziua j.
Observam ca matricele I care satisfac cerinta finala sunt matricele permutare, printe care se numara si matricea identitate I_n. Deci matricea P poate fi inversa matricei B. Matricea B este garantat inversabila deoarece se garanteaza ca exista solutie la problema (Ecuatia matriceala B*P = I cu det(I) nenul are solutie doar daca det(B) este si el nenul)

Inversa matricei se poate calcula in $O(N^3)$ cu o variatie a algoritmului lui Gauss care se cheama eliminare Gauss-Jordan. Prin inmultiri de linii cu constante, si scadere de linii din alte linii, putem aduce matricea B la matricea I_n. Atunci operatiile pe care le-am efectuat sunt echivalente cu inmultirea cu matricea B^-1. Daca retinem aceste operatii si le aplicam pe matricea I_n, vom obtine matricea B^-1. Mai multe explicatii/informatii se gasesc si aici

Por Costel şi Comisia de Cenzură

Problema aceasta poate fi impartita in doua subprobleme:

Aflarea pozitiilor dintr-un text pe care apar cuvintele dintr-un dictionar
Dandu-se un numar de intervale pe axa Ox, si costuri pe fiecare pozitie de pe axa Ox sa se gaseasca o acoperire a intervalelor (fiecare interval sa aibe cel putin un punct care il acopera) de cost minim.

Subproblema 1

Aceasta problema admite mai multe solutii, insa cea de complexitate optima se foloseste de un automat Aho-Corasick. Va rugam sa-l studiati inainte de a citi mai departe. Vom numi nod terminal un nod din Aho-Corasick in care se termina un cuvant din dictionar. Fiecare nod din automat va avea un vector dinamic mathces, o lista cu indici ai prefixelor din text pentru care cuvantul determinat de acest nod (mai precis de drumul de la radacina la acest nod) este sufix. Atunci cand 'trecem textul prin automat' incarcam fiecare indice i din text (care reprezinta prefixul care se termina la pozitia i) in vectorul matches al nodului la care am ajuns la momentul respectiv. Acesta va fi cel mai lung prefix al unui cuvant din dictionar care este sufix al unui prefix al sirului. Pentru a afla toate prefixele din dictionar care sunt sufixe ale acestui prefix i, este suficient sa copiem continutul vectorului matces al nodului curent in vectorii matches ai nodurilor in care ajungem urmarind pointerul de nepotrivire fail. Putem scoate pozitiile de potrivire ale cuvintelor din vectorii matches ale nodurilor terminale.

Atentie ! Aici se poate cadea intr-o capcana. Problema garanteaza ca numarul de aparitii ale cuvintelor din dictionar in text nu depaseste 10⁴, dar problema nu garanteaza pentru numarul de aparitii ale prefixelor cuvintelor din dictionar.

Daca avem textul T: aaaaaaa
si un cuvant un dictionar C: aaaaaaa
numarul de aparitii ale lui C in T este 1 dar numarul de aparitii ale unui prefix al lui C in T este $O(L^2^)$ unde L este lungimea lui C. Urmarind procedeul de mai sus putem da peste o explozie in vectorii matches, dimensiunea lor find de ordinul $O(Nr.aparitii.cuvinte*L^2^)$ . Pentru a remedia acest lucru, vom mentine in fiecare nod o valoare booleana care ne spune daca urmarind pointerul fail mai putem ajunge la un nod terminal. Daca aceasta valoare este false, nu mai copiem continutul vectorului matches al nodului curent mai departe.

Pana acum avem complexitate $O(N + Nr.cuvinte*L + Nr.aparitii.cuvinte*L)$ .

Subproblema 2

Por Costel şi Cifrul

Por Costel şi Invazia Extraterestră

Por Costel şi Livada

Por Costel şi Meciul

Por Costel şi Perechile

Por Costel şi Pinball

Por Costel şi Semipalindroamele