Soluţii ONIS 2016, Runda 1

A. Consecutive

Vom privi din alt unghi ce inseamna ca un numar sa fie suma de mai multe numere naturale consecutive.

Avem N = Sum(x ... y) = Sum(1 ... y) - Sum(1 ... x - 1) = y * (y + 1) / 2 - x * (x - 1) / 2 = (y * (y + 1) - x * (x - 1)) / 2. Trecem N in 2 * N. Ecuatia devine 2 * N = y^{2 + y - x}2 + x. Descompunem diferenta de patrate si dam factor comun: $2 * N = (y - x) * (y + x) + (y + x) = (y + x) * (y - x + 1)$. Pentru simplitatea calculelor, vom defini Z = y + x. Atunci, forma finala e egalitatii va fi: 2 * N = Z * (Z - 2 * x + 1). Observam, deci, ca pentru fiecare divizor al lui 2 * N, fie acesta Z, exista maxim o pereche determinata de Z (x, y) astfel incat egalitatea sa fie satisfacuta. Vom parcurge fiecare divizor al lui 2 * N pana la sqrt(N) (inclusiv), adaugand intr-un vector perechile (d, 2 * N / d) pe care le intalnim, cu d divizor al lui 2 * N.

Acum am vrea sa "gasim" in fiecare pereche de mai sus (d, 2 * N / d) unicele x, y (daca acestea exista) astfel incat y + x = 2 * N / d si y - x + 1 = d. Ordinea trebuie sa fie aceasta, intrucat x < y si d < 2 * N / d. Rezolvand sistemul de ecuatii, obtinem posibila pereche solutie y = (d + (2 * N / d) - 1) / 2 si x = d - y. Memoram aceste perechi candidat.

Ramane doar de sortat perechile si de testat pentru fiecare in parte daca este, de fapt, solutie a problemei. Nu toate perechile vor fi solutii, deoarece exista cateva cazuri marginale precum cel in care 2 * N este patrat perfect.

Complexitate timp: O(sqrt(N) + sqrt(N)log(sqrt(N))).
Complexitate spatiu: O(sqrt(N)).

B. Carte2

O prima posibilitate este a incerca pe rand toate cele 6 * 2 configuratii si a vedea daca vreuna dintre ele se potriveste. Alternativ, pentru a reduce din "tractoreala", se pot sorta crescator ambele siruri, incat ramane de incercat o singura configuratie, alegand cele mai mari dimensiuni, de la sfarsitul sirului sortat.

C. Tribut

Vom aborda problema cu ajutorul tehnicii de Flux maxim. Astfel, construim o retea in care fiecare sistem solar i are asociat nodul i, iar fiecare uniune comerciala j nodul N + j. Sursa si destinatia vor fi alese convenabil astfel incat sa nu se suprapuna cu nodurile necesare. Vom trage un arc de la sursa la fiecare sistem solar i printr-o muchie de capacitate solarSystemTribute[i] si de la fiecare planeta la fiecare dintre unionile comerciale din care face parte, cu capacitate suficient de mare. In final, tragem arcuri de la uniunea comerciala i la destinatie, de capacitate unionTribute[i]. Ramane sa rulam algoritmul de flux pe acest graf, iar fluxul maxim rezultant reprezinta solutia problemei.

Complexitate timp: O(N^5) (supraestimata).
Complexitate spatiu: O(N^2).

I. Politie

Observam ca politistii vor merge intai pe toate drumurile optime (dupa enunt) dintre nodurile legate direct sau indirect doar de muchii de categorie 1, dupa aceea doar de muchii de categorie <= 2, de categorie <= 3, etc. Impartim muchiile dupa categorie. Consideram la fiecare pas i, 1 <= i <= D, ca avem nodurile grupate in componente conexe astfel incat intre orice doua noduri din cadrul aceleasi componente conexe se poate ajunge mergand numai pe muchii de categorie strict mai mica decat i. Uitandu-ne la muchiile de categorie i, este posibil ca intre unele perechi de componente conexe sa fi "aparut" una sau mai multe muchii. Politistii vor dori sa faca drumuri de la orice componenta la orice alta folosind muchiile noi (atat cat se poate), avand grija sa aleaga de fiecare data un drum cu periculozitate maxima minima. Ne imaginam un graf, privind componentele deja stabilite ca pe noduri, si ca muchii intre ele doar muchiile originale de categorie i. Astfel, problema se reduce la a gasi un subset de muchii cu cost maxim minim astfel incat, dupa conectarea nodurilor lor aferente, intre orice doua noduri apartinand aceleeasi componente conexe din graful imaginat sa existe un drum - adica, un Arbore partial de cost minim. Sortam, deci, muchiile din categoria curenta crescator dupa periculozitate si aplicam algoritmul lui Kruskal, avand grija sa introducem intr-un vector toate periculozitatile muchiilor selectate. Procedeul se repeta pana am epuizat toate muchiile. La final sortam descrescator vectorul pe care l-am mentinut si afisam primele P elemente distincte.

Alternativ, mai simplu, putem pur si simplu sorta muchiile crescator dupa categorie, si in caz de egalitate crescator dupa periculozitate si, la sfarsit, sa aplicam Kruskal. Practic simulam procedeul de deasupra.

Complexitate timp: O(MlogM + Mlog*N).
Complexitate spatiu: O(N + M).