Solutii preONI 2008, Runda 4

...

• Lista de probleme
• Heavy metal
• Koba
• Factoriale
• Lampa
• Garaj
• Carnati
• Stalpi
• Nivele
• Arbori

Heavy metal

O solutie care ar fi obtinut aproximativ 40 de puncte ar fi putut fi urmatoarea: ne construim un vector Best[i], reprezentand timpul total maxim in care vor canta formatii daca fiecare concert se va termina inainte de ora i. Rezultatul cautat se va afla in Best[Tmax], unde Tmax va fi timpul maxim de terminare a unui concert. Relatia de recurenta va fi:

pentru i de la 1 la Tmax
    Best[i] = Best[i-1];
    pentru fiecare concert j cu B[j] = i
        Best[i] = max(Best[i], Best[A[j]] + (B[j] - A[j]))

Solutia ce ar fi obtinut punctajul maxim nu reprezinta nimic altceva decat o rafinare a acestui algoritm. Observam ca valorile A[i] si B[i] sunt foarte mari, iar pentru a rezolva aceasta problema le vom normaliza. Vom sorta intervalele in functie de timpul de terminare si vom calcula Best[i] doar pentru valorile in care exista cel putin un concert care se termina la timpul i.

Koba

Solutia 1 (neoptima)

O solutie neoptima ar fi parcurgerea de la 1 la N si adaugarea fiecarei cifre cerute la suma. Acest lucru se face folosind doar ultimele cifre din numere, pentru a nu implementa pe numere mari, cu formula T_i=(T_i-1+T_i-2*T_i-3) % 10. Complexitatea acestei solutii este O(N).

Solutia 2

Pentru o solutie optima, se observa ca, de la un moment dat, sirul devine periodic. Fie numarul abc care reprezinta 3 cifre a, b si, respectiv, c.
Tinem un vector in care A[abc] va reprezenta pozitia pe care a aparut tripletul a, b, c in sirul pe care l-am construit pana la momentul respectiv. Parcurgand cu un indice i de la 1 la N si adunand in suma S cifrele folosite pana la momentul actual, daca la un moment dat, un triplet a, b, c va aparea pentru a doua oara, facem suma cifrelor (notata cu Sum) de la ultima aparitie a celor 3 cifre pana la momentul actual si memoram in M numarul de cifre din aceasta suma (i-A[abc]+1). In acest moment, stim suma cifrelor pana la pasul i. Acum trebuie aflata suma cifrelor de la i+1 la N. Pentru a afla acesta suma, scadem din N pe i (pentru a afla suma cifrelor de dupa i) si vedem de cate ori intra in "noul" N acea secventa "periodica" si adunam (N/M)*Sum la S. Pana acum am calculat suma cifrelor pana la cel mai mare multiplu al lui M mai mic decat N. De aici mai adaugam la S primele N%M cifre din partea periodica.

Factoriale

Pentru fiecare numar de forma x_i! aflam descompunerea sa in factori primi apoi aflam si descompunerea numarului M adunand exponentii corespunzatori bazelor egale din descompunerile numerelor x_i!. Daca avem M factorizat, putem afla solutia problemei usor. Pentru ca un numar X sa se scrie sub forma A^K, cu A si K naturale, trebuie ca fiecare exponent din factorizarea lui X sa fie multiplu de K. Fie REZ rezultatul minim. La inceput REZ = 1. Pentru fiecare termen de forma p_i^e_i din descompunerea in factori primi a numarului M inmultim REZ cu p_i^{K - e_i%K}, unde a % b reprezinta restul impartirii lui a la b daca a nu este multiplu de b si b altfel.
Deoarece rezultatul poate fi foarte mare, este necesara implementarea operatiilor pe numere mari. Idei privitoare la implementarea operatiilor pe numere mari gasiti aici.

Lampa

Fie x_i sirul de cuvinte obtinute. x₀ si x₁ sunt doua siruri initiale, iar, in rest, avem relatia x_i = x_i-1 + x_i-2, pentru orice i > 1, unde a + b reprezinta concatenarea sirurilor de caractere a si b. Daca ni se da x_N trebuie sa determinam x₀ si x₁. Sa notam x₀ = A si x₁ = B ( A si B sunt siruri de caractere ). Sirul x va avea forma: A, B, AB, BAB, ABBAB, BABABBAB, etc. Se observa ca numarul de siruri A din al N-lea termen este fib_N-2, iar numarul de B este fib_N-1, unde fib este sirul lui Fibonacci (fib₀ = fib₁ = 1 si fib_n = fib_n-1 + fib_n-2 pentru orice n > 1).
Fie M = length(x_N). Avem relatia: M = length(A) * fib_N-2 + length(B) * fib_N-1 (*). Aflam toate solutiile (length(A), length(B)) ale ecuatiei de mai sus. Pentru aceste lungimi A si B sunt unic determinate, in functie de paritatea lui N:

• Daca N este par, A este egal cu primele length(A) caractere din x_N si B este egal cu urmatoarele length(B) caractere.
• Daca N este impar, B este egal cu primele length(B) caractere din x_N si A este egal cu urmatoarele length(A) caractere.

Pentru A si B determinate verificam in complexitate O(M) daca intr-adevar al N-lea termen al sirului pornind de la A si B este sirul dat si, in caz afirmativ afisam perechea (A B).

Acest algoritm este in practica foarte rapid deoarece fib[N] atinge foarte repede valori mari. Pentru testele date, dupa cum reiesea si din tabelul din restrictiile problemei, avem:

Se observa ca pe cele 10 teste folosite la corectare O(M) * O(numar_de_solutii_ecuatie) este relativ mic, deci o astfel de rezolvare garanteaza obtinerea punctajului maxim.

Garaj

Observam ca daca in timpul T putem termina transportul, atunci transportul poate fi terminat si la momentele de timp mai mari decat T. Deci putem cauta binar timpul maxim in care circula un camion. Pentru un timp T fixat, vom vedea care este numarul maxim de sticle care pot fi duse la adapost, daca acest numar este mai mare sau egal decat M, timpul fixat este unul valid si vom incerca sa gasim un timp mai mic, altfel vom incerca un timp mai mare. Dupa ce am minimizat timpul maxim in care circula un camion, vom sorta camioanele descrescator dupa numarul de sticle pe care il pot transporta in acest timp si vom alege pe rand cate un camion incepand cu primul pana cand numarul de sticle pe care il pot transporta toate camioanele alese va fi mai mare sau egal cu M.

Carnati

Prima observatie pe care o facem este faptul ca pretul fixat de Gigel va fi unul dintre preturile clientilor sai. Odata ce avem fixat un pret X putem sa construim o dinamica A_i profitul maxim daca magazinul este deschis in momentul in care trece clinetul i (clientii vor fi sortati crescator dupa timpul la care trec). Relatia de recurenta se observa usor A_i= max(A_i-1-(T_i-T_i-1)*C+G,G-C), unde G este X pentru X ≤ P_i sau 0 in caz contrar. De fapt, avand fixat X si construind vectorul H_2*i=G-C, H_2*i+1=-(T_i-T_i-1)*C problema se reduce la determinarea subsecventei de suma maxima.

Complexitatea de rezolvare pentru X fixat este O(N), deci in final algoritumul va fi O(N²)

Stalpi

Vom sorta stalpii dupa coordonata X si vom calcula best[n] = costul minim pentru a acoperi primii n stalpi (dupa sortare). De asemenea vom sorta stalpii dupa valoarea X+D si aceasta va fi ordinea in care ii vom procesa. Cand procesam stalpul i (din ordinea sortata dupa X+D) vom afla R, cel mai din dreapta stalp pentru care X_R ≤ X_i+D_i si L, cel mai din dreapta stalp pentru care X_L < X_i-S_i. Atunci o valoare posibila pentru best[ R ] ar fi min(best[L], best[L+1]...best[N])+cost[i]. Daca best[ R ] si-a imbunatatit vechea valoare (initial vectorul best va fi initializat cu infinit) atunci pentru 1≤j≤R best[j]=min(best[j],best[ R ]). Pentru a implementa eficient operatiile descrise se poate folosi un arbore de intervale, sau mai simpu de implementat, un arbore indexat binar.

Nivele

Pentru a determina daca un sir de numere poate reprezenta nivelele frunzelor dintr-un arbore binar vom incerca sa determinam daca putem construi arborele eliminand frunze din arbore. Daca exista doua frunze aflate pe pozitii adiacente in vector si care au aceasi valoarea, le putem elimina din arbore, lasand in loc o frunza pe nivelul L-1. Daca la final in vector o singura frunza pe nivelul 1 atunci putem raspunde cu DA. Putem implementa eficient acest algoritm folosind o stiva. Se parcurg frunzele de la stanga la dreapta si la fiecare pas se verifica nivelul frunzei curentei cu nivelul frunzei din varful stivei:

• daca sunt diferite se insereaza nivelul curent in stiva
• daca sunt egale se scoate frunza din varful stivei, iar nivelul frunzei curente scade cu 1

La final, se verifica daca in stiva a ramas o singura frunza cu nivelul 1.

Arbori

Problema se rezolva prin programare dinamica. Se construieste o matrice A[i][j][k] numarul de arbori cu urmatoarele proprietati:

• au i noduri
• gradul radacinii este j (mod M)
• ultimul fiu al radacinii este un subarbore cu k noduri
• fiecare nod intern din arbore (mai putin radacina) are gradul K (mod M)

Raspunsul se va gasi in A[N][K][N]. Arborii fiind neetichetat, ordinea fiilor nu conteaza, asadar putem considera ca fiecare nod are fiii in ordine crescatoare a numarului de noduri din subarbore.

Pentru a calcula A[i][j][k] vom itera o variabila x dupa numarul de fii ai radacinii cu fix k noduri in subarbore. Astfel, pentru fiecare x intre 0 si i/k vom aduna la A[i][j][k] valoarea A[i-x*k][(j-x) mod M][k-1] * Nr(k, x) unde Nr(k, x) este numarul de moduri in care se pot aranja x subarbori cu k noduri fiecare. Stim ca pentru subarborii de k noduri avem A[k][(K-1) mod M][N] posibilitati (K-1 deoarece ii legam de o radacina). Dintre toate aceste posiblitati trebuie sa alegem x, tinand cont de faptul ca ordinea nu conteaza. Numarul pe care il cautam va fi Nr(k, x) = Comb(A[k][(K-1) mod M][N]+x-1, x), deoarece Comb(n+k-1, k) reprezinta numarul de moduri in care n obiecte identice pot fi distribuite in k cutii distincte.
Complexitatea spatiu a rezolvarii este O(N²*M), iar complexitatea timp este O(N²*M*lg N), deoarece N/1+N/2+N/3...N/N = N*lg N (cand iteram x iteram doar pana la i/x). Desigur, am presupus ca putem calcula combinarile in O(1). Acest lucru chiar este posibil, presupunand ca avem valoarea combinarii pentru x, putem determina valorea pentru x+1 in O(1). Datorita limitelor mici, se putea obtine punctaj maxim si calculand combinarile in O(x), obtinand astfel o solutie O(N³*M). Rezolvarea se mai poate optimiza folosind tehnica de memoizare.