Solutii Algoritmiada 2011, Runda Finala

Avioane

Soluţia I O(NlogN):

În primul rând, se observă că mereu este optim să stabilim costul unui bilet (şi cel de business cât şi cel de economy) egal cu unul din cele n preţuri pe care sunt dispuse clienţii să îl plătească.
Sortăm în ordine crescătoare cele n preţuri ”candidate”. Dacă fixăm preţul biletului business pe elementul cu indicele i , să notăm cu D i indicele preţului optim pentru biletul de economy astfel încât să se obţină suma maximă. Evident, D i < i. De asemenea, se poate observa că vectorul D va fi sortat, deci că oricare ar fi i < j, D i ≤ D j (observaţie uşor de demonstrat).
Vom defini o funcţie solve(i, j) care să calculeze D i, D i+1 .. D j, presupunând D i-1 şi D j+1 cunoscute. Vom calcula D (i+j)/2 iterând prin elementele D i, D i + 1, ... D j şi alegând indicele pentru care se obţine suma maximă. Apoi apelăm recursiv solve(i, (i + j) / 2 - 1) şi solve((i + j) / 2 + 1, j). Complexitatea finală va fi O(N log N), pe fiecare din cele log N nivele ale recursivităţii parcugându-se maxim odată fiecare element al şirului.

Soluţia II O(N):

Definim vectorul D la fel ca în soluţia precedentă şi sortăm vectorul v din input.
Calculăm de la stânga la dreapta valorile din D. La momentul i, dacă j ar fi D i, suma ce se obţine (partea ce depinde de j) este v j * (i - j) = v j * i - v j * j. La momentul i + 1, suma obţinută pentru j devine v j * (i + 1) - v j * j. Observăm că pentru fiecare j, cu trecerea de la i la i + 1, sumele obţinute cresc liniar. Putem considera fiecare indice j ca o semidreaptă, cu a = v j şi b = - v j * j, cerinţa problemei devenind la fiecare moment i pe axa Ox ( i de la 1 la n ) să vedem semidreapta care în momentul respectiv se află cel mai sus. Menţinem un deque cu indicii semidreptelor ce încă sunt candidaţi. Ordinea în care intră elementele în deque va fi crescător după pantă. Când avem momentul i de timp, eliminăm elemente de la începutul deque-ului cât timp acestea au devenit invalide (elementul următor l-a depăşit pe primul). Apoi înainte să îl inserăm pe i la sfârşit, trebuie scoase din deque elementele ce sunt depăşite de i înainte ca ele să depăşească elementul dinaintea lor (comparăm timpii la care i îl depăşeşte pe ultimul, respectiv când ultimul îl depăşeşte pe penultimul). Răspunsul pentru i se află la începutul deque-ului (elementul cu valoarea maximă la momentul i).

Fabrica

Să notăm cu timpA i momentul in care maşina A termină cea de a i - a bere. Prima bere se va termina la momentul t, cel mai mic timp al vreunui procesor de tip A. Când se termină prima bere, procesorul respectiv începe imediat să lucreze la următoarea bere. În general, când un procesor i termină o bere la momentul T, următoarea bere pe care o va termina va fi la T + Nr A [ i ]. Astfel, putem ştii pentru fiecare procesor de tip A care va fi următorul moment la care acesta va termina o bere. La fiecare pas, următoarea bere procesată va fi la minimul acestor momente. Menţinând un heap, se pot calcula momentele la care se termină primele N beri în O(N * log Nr A).

Putem calcula în mod similar timpii necesari celei de a doua maşini să sigileze dozele, făcând abstracţie de prima maşină. Să notăm cu timpB i timpul necesar maşinii B pentru a procesa primele i doze.

Acum, să presupunem că alegem o ordine de procesare a dozelor pentru a doua maşină, fie aceasta p 1, p 2 ... p~n~ : cea de a i - a sticlă va fi procesată a p i - a de către a doua maşină. Timpul după care se termină de procesat sticla i va fi timpA i + timpB pi . Deci pentru această ordine, timpul după care se termină de procesat toate dozele este maximul timpilor după care este gata fiecare doză în parte.

Dacă avem două poziţii i şi j, pentru care i < j şi p i < p j , timpA j + timpB pj va fi mai mare sau egal şi faţă de timpA i + timpB pj cât şi faţă de timpA j + timpB pi (din modul de definire, vectorii timpA şi timpB vor fi ordonaţi crescător), deci dacă am interschimba p i cu p j am obţine o soluţie cel puţin la fel de bună. Deci ordinea optimă va fi N, N-1 ... 1.
Astfel, răspunsul la problemă va fi max(timpA 1 + timpB N , timpA 2 + timpB N-1 ... timpA N + timpB 1).

Perb

Un sir S de lungime N are perioada d daca si numai daca S[i] = S[i mod d] si d divide N. Pentru fiecare rest intre 0 si d - 1 ne vom uita la toate pozitiile ce dau acest rest la impartirea cu d si le vom face egale. Pentru a face un numar minim de operatii, vom schimba toate caracterele in cel cu numar maxim de aparitii.

Pentru a raspunde eficient la intrebari, vom precalcula pentru fiecare subsecventa S[i..j] raspunsul, sa il numim C[i][j]. Acum vom fixa lungimea perioadei, d si capatul din stanga, i, si ne vom deplasa la dreapta cu un indice j. In acest timp numaram de cate ori apare fiecare litera in functie de restul indicii ei la impartirea cu d. De fiecare data cand intalnim un j astfel incat lungimea subsecventei S[i..j] se divide cu d calculam numarul de litere ce trebuie modificate cu metoda de mai sus si modificam C[i][j] in caz ca obtinem un raspuns mai bun.

Complexitate O(N ^ 3).

Guvern

Primul pas este sa determinam pentru fiecare nod x, nodul y care trebuie obligatoriu selectat daca nodul x este selectat. Acest lucru putem determina foarte usor pornind cu un dfs din radacina. La fiecare pas tinem intr-un set lista nodurilor stramos si cu un lower_bound determinam usor care este nodul cu valoarea cea mai mica, mai mare decat o valoare data. Notam acest nod y determinat in functie de x cu obligat[x]. Daca un nod x nu are un astfel de nod y, notam ca obligat [x] = 0. Pentru fiecare nod y o sa tinem o lista cu toate nodurile x astfel incat obligat[x] = y.

Pasul 2 consta in realizarea unei dinamici pe arbore care spune d[i] = numarul maxim de noduri pe care le putem selecta din subarborele lui i daca i ar fi selectat. In primul rand d[i] = 1 (il numaram mai intai pe nodul i). Observam ca nodurile din subarborele lui i sunt de 4 tipuri:

1) Toate nodurile j astfel incat grad[j] > grad[i]. Este clar ca daca am selectat nodul i, aceste noduri nu pot fi selectate.
2) Toate nodurile j astfel incat grad[j] < grad[i] si obligat[j] arata catre un nod care este stramos a lui j. Nici aceste noduri nu pot fi selectate deoarece daca le-am selecta ar trebui sa selectam si toate nodurile obligat[j], noduri care au gradul mai mic ca i (altfel obligat[j] ar fi fost i) si sunt stramosi a lui i (contradictie cu proprietatea 1).
3) Toate nodurile j astfel incat grad[j] < grad[i] si obligat[j] = i. Putem selecta toate aceste noduri cu conditia ca unul sa nu fie stramosul altuia. Mai exact, fie 2 noduri j si k astfel incat obligat[j] = obligat[k] = i si j este stramosul lui k. Automat deducem ca grad[j] < grad[k] < grad[i], deci j si k nu pot fi simultan selectate. Daca grad[k] ar fi fost mai mic decat grad[j], atunci obligat[k] ar fi fost j si nu i.
Pentru a determina ce noduri selectam si ce noduri nu, o sa asociem fiecarui nod un interval (intervalul determinat din parcurgerea Euler). Astfel, daca un interval contine complet alt interval inseamna ca primul nod este stramosul celui de al doilea. Costul intervalului lui j este d[j] (cate noduri selectam din subarborele respectiv). Obtinand aceste intervale am redus recurenta la problema spectacolelor, scopul nostru fiind sa selectam un set de intervale cu suma costurilor cat mai mare (practic sa selectam cat mai multe noduri).
4) Toate nodurile j astfel incat grad[j] < grad[i] si obligat[j] = k, k aflandu-se la randul lui in subarborele lui i. Aceste noduri pot fi ignorate deoarece k ori este un nod de tipul 1 si 2 si nu poate fii selectat deci nici j nu poate, ori este de tipul 3 deci j este deja luat in considerare in d[k]

Consideram si nodul 0 ca fiind parintele nodului 1 si pornim dinamica de acolo (trebuie sa facem asta deoarece exista noduri x care au obligat[x] = 0).

Nummst

Vom nota cu GCD cel mai mare divizor comun şi cu LCM cel mai mic multiplu comun.

GCD-ul maxim posibil al numerelor afişate va fi D = cel mai mare divizor al lui N diferit de el însuşi. Astfel o soluţie simplă care afişează N / D numere de valoare D va obţine 20 de puncte.

În continuare vom încerca să maximizăm valoarea LCM-ului. Pentru a simplifica problema, observăm că putem să-l împărţim pe N prin D: să numim această valoare N'. În continuare dorim să aflăm LCM-ul maxim posibil al unui şir de cel puţin 2 numere cu suma numerelor egală cu N'.

Pentru a face problema mai tractabilă vom face câteva observaţii, pe care vă invităm să le demonstraţi ca exerciţiu:

1. N' ≤ sqrt(N).
2. Există întotdeauna o soluţie optimă în care niciunul din numerele din şir nu are mai mult de un factor prim.
3. Există întotdeauna o soluţie optimă în care nu există două elemente strict mai mari decât 1 egale între ele.

Folosindu-ne de N'-ul relativ mic şi observaţia că factorii primi pot fi adăugaţi incremental pentru a îmbunătăţi soluţia, putem dezvolta o soluţie ce se bazează pe programare dinamică dp[IDX][SUM] = LCM-ul maxim pe care il putem obtine dintr-un sir de numere in care toti factorii primi constituenti sunt printre primele IDX numere prime, iar suma tuturor numerelor este SUM. Recurenţa este asemănătoare unui knapsack, cu atenţie la modul în care se compară două LCM-uri (acestea pot fi mult prea mari într-o implementare naivă).

Complexitatea algoritmului este O(N' * nrPrimeMaiMici(N')). Înlocuindu-l pe N' cu bound-ul observat mai sus şi aproximând numărul de numere prime prin teorema numerelor prime, obţinem complexitatea O(N / log N).