Solutii - Summer Challenge Trei

(Creat de ditzonec la data de 2006-08-27 categoria Competitii, autor(i) Echipa Info-arena)

ABC

Problema se reduce la 3 cazuri, in functie de cum este C fata de suma termenilor sirului A. Daca aceste numere sunt egale, sirul D cautat este chiar sirul A. In caz contrar, vom rezolva problema pentru C mai mare, celalalt caz fiind analog. Va trebui deci sa marim cateva dintre elementele lui A. O observatie este utila in acest moment: daca A_i<A_j, atunci exista o solutie optima cu D_i<D_j. Pentru a demonstra aceasta afirmatie, observati ca in caz contrar, interschimband valorile D_i si D_j se obtine o solutie pentru care suma termenilor lui D este aceeasi, dar valoarea maxima a sirului din enunt (pe care o vom numi in continuare delta) este mai mica, sau in cel mai rau caz egala.

Sa incercam acum sa obtinem un sir D pentru o valoare fixata a lui delta. Pornim cu sirul D egal cu cel initial, A. Atat timp cat suma termenilor lui D este mai mica decat C vom aplica urmatoarea operatie: vom mari cu o unitate un termen al lui D. Mai trebuie avut grija ca tot timpul sa fie respectata conditia D_i ≤ A_i+delta. Daca nu mai putem aplica nici o operatie (toti termenii au atins valoarea maxima posibila, sau prin marire am obtine o diferenta mai mare decat delta), si inca nu am obtinut C, nu putem gasi nici un sir D pentru acest delta, si in plus am obtinut un sir D cu suma termenilor maxima posibila pentru valoarea curenta a lui delta. Se poate demonstra ca nici nu conteaza ce termen marim, atat timp cat respectam observatia din paragraful anterior. Pentru a obtine insa o complexitate liniara la acest pas, vom mari termenii in ordine descrescatoare (evident dupa o sortare initiala). Bineinteles, nu este nevoie sa aplicam fiecare operatie in parte, ele vor fi aplicate toate in acelasi timp. Pentru cazul analog din paragraful precedent, o operatie va consta din scaderea unui termen cu o unitate, pornind de data aceasta de la cel mai mic.

In plus, daca marim valoarea lui delta la delta+1, putem aplica in continuare operatii asupra lui D, de unde am ramas la pasul precedent, obtinand deci sume mai mari. Se contureaza acum o rezolvare: putem cauta binar valoarea lui delta. Daca am obtinut un sir D care sa respecte conditiile din enunt, putem cauta un delta mai mic, daca nu, trebuie sa marim delta. Complexitatea algoritmului rezultat este O( N log N).

Dupa sortarea sirului A, putem obtine un algoritm liniar rafinand solutia de mai sus. Aceasta afirmatie se bazeaza pe urmatoarea observatie (presupunem sirul A sortat in ordine descrescatoare): daca putem creste A_i cu valoarea d, atunci putem creste cu valoarea d orice A_j, cu j > i. Vom parcurge valorile lui A in ordine crescatoare a indicilor. La pasul i (i ia valori intre 1 si N) ne folosim de valorile D_i-1(convenim ca D₀=B) si S (numarul de unitati cu care mai trebuie marita suma in continuare) si vom creste pe A_i cu valoarea d=min(D_i-1-A_i, ceil(S/(N-i+1))). Bineinteles, la pasul urmator si S va scadea corespunzator.

Oras

Sa presupunem ca avem o solutie pentru N-2 noduri. Acum adaugam la solutie nodurile N-1, si N. Fara a restrange generalitatea putem orienta strada (N-1, N) de la N-1, la N. Acum oricare ar fi un nod X de la 1 la N-2 trebuie sa fie pe un circuit de 3 noduri cu nodurile N-1 si N. Astfel putem fixa ca de la nodurile {1, 2, ..., N-2} sa plece arce inspre nodul N-1, si de la nodul N sa plece arce inspre nodurile {1, 2, ..., N-2}. Daca graful initial cu N - 2 noduri satisfacea conditiile problemei, atunci si graful obtinut este valid. Pentru N = 3 exista o solutie triviala, pentru N = 4 putem demonstra ca nu exista solutie (demonstratia trebuind sa ia in calcul mai multe cazuri), sau putem sa generam exhaustiv toate grafurile turneu cu N = 4 si sa observam ca nici unul nu e valid. Gasirea unei solutii pentru N = 6 este destul de facila (autorului i-a luat 2 minute). Astfel am aratat ca avem solutie pentru toate cazurile din problema, inafara cazului N = 4. Complexitatea acestei solutii este O(N²).

Gold

Solutia triviala este O(N³): se aleg doua puncte si se verifica suma cantitatilor din ambele parti ale dreptei printr-o parcurgere noua a punctelor. O astfel de solutie obtine 30-40 de puncte. Pornind de la aceasta idee se poate rafina ajungand la o complexitate de O(N²logN). Pentru fiecare punct P sortam celelalte N-1 puncte dupa unghiul polar ( unghiul format de punctul curent cu axa Ox, daca consideram originea in punctul P) in O(NlogN). Notam cu S_i suma cantitatilor din primele i mine in ordinea ordonarii dupa unghi. Vom fixa o dreapta de baleiere care sa treaca prin punctul P si prin primul punct in ordinea sortarii. Daca am calculat la un anumit pas toate punctele aflate de o parte a dreptei de baleiere, in momentul in care rotim dreapta de baleiere pana ajunge in dreptul urmatorului punct (in ordinea sortarii) toate aceste puncte raman de aceeasi parte mai putin cel aflat pe dreapta si eventual se vor adauga unele noi. De aceea vom incepe cautarea ultimului punct aflat in sensul + al dreptei
de baleiere de la punctul calculat la pasul anterior( toti indicii vor fi calculati modulo N). Fiecare punct va fi parcurs de cel mult doua ori, deci complexitatea acestui pas este O(N). Astfel vom putea calcula in O(1) sumele de o parte si de alta a dreptei folosindu-ne de vectorul S.