Solutii Algoritmiada 2015 Runda 3

Scenariu

O prima solutie este sa facem o dinamica: D[ i ][ j ] = in cate moduri putem selecta din primele i pagini j acte. Putem varia numarul de pagini ale actului j. Ca urmare D[ i ][ j ] = Suma(D[ t ][ j - 1] * Combinari(i - t - 1, s[j] - 1)). Avem i - t pagini pentru actul j si s[j] scene din care o scena trebuie fixata la ultima pagina (de aceea avem Combinari(i - t - 1, s[j] - 1)). 

Pentru 100 de puncte observam ca nu conteaza cum pozitionam actele, ci doar cele S = Suma(s[i]) scene (ultima scena fiind la pagina N obligatoriu). Ca urmare raspunsul este Combinari(N - 1, S - 1). Combinarile se pot calcula atat cu invers modular in O(N * log N) cat si cu programare dinamica in O(N * S). Ambele implementari obtin punctaj maxim.

Hashtag

Să analizăm ce complexitate are algoritmul brut care încearcă toate configuraţiile posibile de hashtag şi calculează costul pentru a obţine o anumită configuraţie. Există O(n4) opţiuni pentru a delimita coloanele hashtagului, analog pentru linii. Pentru a calcula costul obţinerii unei configuraţii suntem nevoiţi să parcurgem matricea şi obţinem astfel o complexitate de O(n10). Putem optimiza calcularea costului la O(1) folosind sume parţiale obţinând astfel o complexitate totală de O(n8), care este încă prea mare pentru N = 30. Pare astfel că trebuie să reducem numărul de configuraţii pe care le luăm în considerare.

Analizând problema, putem observa că obstacolul principal pe care-l întâlnim în majoritatea soluţiilor posibile este faptul că liniile şi coloanele hashtagului nu pot fi alese independent unele de altele. Deoarece nu par să există metode uşoare de a rezolva acest conflict, trebuie să ne împăcăm cu ideea că cel puţin liniile sau coloane vor trebui încercate în toate configuraţiile. Totuşi avem motive bune să credem că odată ce sunt fixate liniile, coloanele pot fi alese inteligent pentru a obţine o soluţie optimă (sau invers). Această problemă a dependenţei liniilor faţă de coloane cât şi ideea de a fixa liniile sunt prezente şi în problema Flip.

Să vedem deci cum putem selecta coloanele hashtagului optim, având liniile deja selectate. Această subproblemă cere practic, după ce "eliminăm" liniile fixate care sunt deja pline de 1, doar să transformăm o matrice binară într-o matrice binară formată din cinci fâşii care au alternativ valorile 0 şi 1. Putem rezolva uşor acestă problemă prin programare dinamică având starea dp[i][j] = costul minim de a transforma primele i linii, iar linia cu numărul i să facă parte din fâşia cu numărul j. Avem N * 5 = O(N) stări, iar recurenţa poate fi rezolvată în timp constant dacă precalculăm costul de a transforma fiecare linie într-o linie plină de 1 respectiv de 0.
Astfel, în funcţie de implementare, putem obţine algoritmi de complexitate O(n6) sau O(n5), ambii obţinând punctaj maxim.

Overdrive

O sa cautam binar capacitatea D ceruta. Pentru un D fixat trebuie sa verificam daca putem transporta toate obiectele din 2 drumuri. O sa impartim cele N obiecte in 2 grupe de N / 2 obiecte si (N + 1) / 2. Pentru fiecare grupa o sa precalculam toate cele 2(N / 2) respectiv 2(N + 1) / 2 submultimi posibile. Pentru o submultime consideram ca elementele selectate sunt transportate in primul drum, elementele neselectate la al doilea transport. Astfel, pentru fiecare submultime avem cate o pereche (A,B): A fiind suma greutatilor din primul transport si B suma greutatilor din transportul 2 . Ramane de verificat daca putem selecta o submultime din prima grupa si o submultime din cea de a doua grupa astfel incat atat suma A-urilor cat si suma B-urilor sa fie mai mica sau egala cu D ( D-ul cautat binar). Sortam perechile din prima grupa crescator dupa A si perechile din grupa 2 descrescator dupa A. Verificarea se reduce foarte simplu printr-o baleiere a perechilor. Complexitatea este O(2N / 2 * logVALMAX).

Permsplitcount

Arb4

Sortam muchiile dupa cost. Pentru fiecare muchie (a,b) consideram lantul de la a la b din arborele nostru initial. Observam ca muchia noastra (a,b) poate inlocui orice muchie de pe acest lant. Putem updata tot lantul cu costul muchiei: acest lucru poate sa fie realizat cu diferite structuri de date (Heavy Path, Arbori de Intervale) dar nu ar trebui sa intre in timp. Daca ne folosim de faptul ca am sortat muchiile dupa cost observam ca o muchie odata ce a fost updatata nu mai este nevoie si a doua oara (deoarece vrem sa o inlocuim doar cu cea mai mica muchie). Pornim din nodul a si mergem in sus in arbore pana cand ajungem intr-un stramos de-al lui b (sa verificam daca un nod este stramosul altui nod se poate foarte simplu cu o parcurgere euler). Pe parcurs updatam toate muchiile prin care tercem. Analog, facem acelasi lucru si din nodul b. Ca sa nu trecem printr-o muchie de mai multe ori tinem paduri de multimi disjuncte pe aceste muchii. Astfel, in loc sa mergem muchie cu muchie la fiecare pas mergem doar in muchia cea mai de sus din padurea ei. Complexitatea este O(M log N + N * log* N).

Diametru

Problema aceasta avea un format mai special, era oarecum output-only (practic se dorea numai output-ul unei surse, fara niciun input) dar avea punctaje partiale.

Pe scurt ce cerea ea e sa gaseasca un test astfel incat algoritmul din enunt sa aiba nevoie de un K cat mai mare pentru a ajunge la rezultatul corect. Evaluarea sa facea astfel: se simula algoritmul acela fara un K predefinit si atunci cand se intalnea diametrul grafului se oprea iar aceea era iteratia folosita pentru a puncta testul.

  • Pentru 30 de puncte se puteau gasi destul de multe solutii dar una foarte simpla este urmatoarea:
    Cream un ciclu de lungime 8 cu nodurile numerotate in ordinea urmatoare (1 2 7 3 4 5 8 6). De nodul 7 legam inca un nod numeratot cu 9. Astfel daca incepem din nodul 1 vom merge asa: 1 -> 4 -> 2 -> 5 -> 1 -> 3 -> 6 -> 4 -> 7 -> 8 -> 9
  • Pentru 50 de puncte era nevoie de un graf astfel incat sa se treaca prin toate nodurile lui macar o data (se cereau 450 de iteratii cand numarul de noduri putea fi maxim 500). Aici o solutie era un graf complet cu 500 de noduri fara muchia 499 - 500. Astfel iteratiile erau
    1 -> 2 -> 3 -> 1 -> 4 -> 2 -> 5 -> 1 -> 6 -> 2 -> 7 - > 1 -> ... -> 2k -> 2 -> 2k + 1 -> 1 -> ... -> 498 -> 2 -> 499 -> 500.
  • Pentru 75 de puncte deja numarul crestea mult peste numarul de noduri si era comparativ cu numarul de muchii (10000)
    Aici observatia ce trebuia facuta e ca se puteau folosi construciti anterioare pe care le puteam generaliza. Mai exact se putea folosi constructia de la 30 de puncte.
    Acea constructie face 10 iteratii pentru ca nodul curent se muta de pe o parte a ciclului pe alta ( nodurile 6 1 2 si 3 4 5). Daca se mai adaugau inca 3 noduri care sa formeze un lant si sa uneasca nodurile 7 si 8 (dupa o renumerotare convenabila asfel incat nodurile 7, 8 si 9 sa fie N-2 N-1 si N din graful nou obtinut unde N e numarul de noduri din graful nou) se observa ca numarul de iteratii crestea chiar repede. De aici o solutie se putea forma.
    • Se construia un graf in care nodurile N - 2 si N erau interconectate printr-o muchie.
    • Se construiau cat mai multe lanturi de lungime 4 intre nodurile N - 1 si N - 2 folosind 3 noduri noi de fiecare data.
      O astfel de construtie genera in jur de 11000 de iteratii si garanta 75 de puncte.
  • Pentru 100 de puncte mai trebuia rafinata un pic ideea de la 75 de puncte. Defapt daca in loc de lanturi de lungime 4 erau folosite lanturi de lungime 3 numarul de lanturi crestea si deci si numarul de iteratii. Astfel se obtineau 100 de puncte. De mentionat ca daca se incerca cu lanturi de marime 2 numarul de iteratii era in jur de N si se obtineau doar *50% de puncte.

Metrou3

Pentru a putea rezolva mai usor problema putem sa facem o transformare foarte simpla a enuntului: In loc de N statii date cu distantele dintre ele putem sa avem un graf ciclud e lungime T ( egal cu suma distantelor consecutive dintre statii) si care are in anumite noduri statii.

Pentru 10 puncte cu o complexitate O(T * N2) se putea simula foarte usor ce scria in enunt:

Se itera timpul in [0, T) statiia de plecare in [0, N) si statie de destinatie in [0, N)
* Daca statia de plecare era egala cu destinatia se aduna 0 la raspuns
* Altfel se calcula timeA, timpul pentru a ajunge din sursa in destinatie luand metroul A (cel care merge 0 -> 1 -> 2 -> ... -> N - 1 -> 0), respectiv timeB pentru metroul celalalt si se aduna minimul dintre ele.

Pentru 30 de puncte cu o complexitate de O(N2) se rafina ideea de 10 pe observatia ca intre o sursa si o destinatie fixata intervalul de timp [0, T)

poate fi impartit in maxim 3 bucati [0, A) [A, B) si [B, T) cu proprietatea ca in fiecare di aceste intervale de timp mereu se va lua acelasi metrou si deci nu era decat o formula asemanatoare cu o suma telescopica.

Pentru 100 de puncte vom trata mai intai un caz simplificat al problemei, mai exact atunci cand T este par.

In acest caz cele 2 trenuri se intalneau de fix 2 ori in puncte intregi pe ciclu in puncte la distanta maxima unul de altul. (sa le zicem X s Y)

Mai era nevoie si de o observatie simpla intervalul de timp [0, T] este echivalent cu orice interval [A, A + T). Astfel putem aduna pentru fiecare pozitii pe care le pot lua trenurile (care sunt exact T) getTime(start, finish) start si finish din [0, N).

Problma originala se poate imparti in 2 identice: cat face suma de getTime pentru toate sursele si destinatile posibile cand cele doua metrouri se intalnesc in X si se indreapta spre Y si viceversa).

Acum sa analizam un caz simplu cand trenurile sunt in punctele U V pe ciclu. Putem imparti ciclu in 2 zone, zona in care se indreapta trenurile (sa-i zicem zona rosie) si zona din care vin (zona albastra). Cele 2 puncte in care se afla trenurile vor face parte din zona rosie.

Vor exista 4 cazuri:

  • sursa si destinatia sunt in zona rosie. Aici conteaza doar ordinea (U sursa destinatie V sau U destinatie sursa V). Pentru prima ordine getTime este distanta pe zona rosie dintre destinatie si U, iar pentru al doilea distanta pe zona rosie dintre destinatie si V.
  • sursa si destinatia sunt in zone albastre. Acelasi rationament ca mai sus. Pentru ordinea (U zona rosie V sursa destinatie U) getTime va fi lungimea zonei rosii + distanta pe zona albastra dintre V si destinatie si analog lungimea zonei rosii + distanta pe zona albastra dintre U si destinatie
  • sursa e in zona rosie si destinatia in zona albastra. Aici nu conteaza unde este sursa, doar unde este destinatia, costul va fi egal cu T - minimum(distanta pe zona albastra de la U la destinatie, distanta pe zona albastra de la V la destinatie)
  • sursa e in zona albastra si destinatia in zona rosie. Aici iarasi nu conteaza unde este sursa, intrucat va trebui sa parcurgem in intregime tot ciclul si apoi inca un pic sa ajugem la destinatie. Costul va fi egal cu T + minimul(distanta pe zona rosie de la U la destinatie, distanta pe zona rosie de la V la destinatie).

Aici exista inca un caz special cand U si V sunt acelasi nod si exista o statie in U dar acesta ramane spre rezolvare cititorului.

Totusi nu putem calcula de fiecare data pentru toate perechile (U, V) intrucat complexitatea ar fi O(N * T) care este mult prea mare.
Totusi o idee ce ar fi trebuit sa vina destul de repede de la acest punct este ca putem calcula pentru perechea (U', V') de la timpul t + 1 stiind suma pentru perechea (U, V) de la timpul t. Astfel:

  • Daca nu exista nicio statie in punctele U si V atunci suma de la (U', V') este suma de la (U, V) - N * (N - 1). Asta reiese din observatia ca daca la momentul curent oriunde ne-am afla nu e niciun tren oricum trebuie sa asteptam. Daca asteptam o secunda ne va lua pentru fiecare din cele N * (N - 1) perechi de (sursa, destinatie) cu sursa != destinatie
  • Daca exista statii nu trebuie decat sa transformam toate perechile de (sursa, destinatie) care contin statia asta dintr-unul din cele 4 cazuri de mai sus in altul. Aici nu erau decat niste sume partiale (de mentionat ca nu sunt 16 cazuri posibile ci numai 3).

Astfel complexitatea ajungea la O(N)