Solutii .com 2009, Runda 1

Tabara2

Solutia optima este de complexitate O(M logN + M log*S).

  • Pentru a face update-ul de tipul 1 in complexitate O(log*S) ne vom folosi de multimi disjuncte. Astfel, cand trebuie sa unim nodurile i si j, unim multimea lui i cu multimea lui j. In fiecare radacina a unei multimi disjuncte vom tine si valoarea maxima din multimea respectiva.
  • La update-ul de tipul 2 vom uni nodul i cu radacina multimii in care se afla nodul j. Ca si la update-ul de tipul 1, vom tine in radacina (in cazul nostru, nodul i) valoarea maxima din multimea nou formata. Tot aici vom updata valoarea maxima din nodul i intr-un arbore de intervale tinut pe nodurile 1 - N. Complexitatea pentru aceste operatii va fi O(log*S + logN).
  • Fiecare query va fi rezolvat in O(logN) cu ajutorul arborelui de intervale.

Floare

Vom construi sirul Di, cu semnificatia a cata dintre jucatoare (considerand ca jucatoarea 1 muta prima) va castiga jocul pentru o floare cu i petale. Observam ca dintr-o stare cu i petale putem ajunge in oricare dintre starile i-1, i-2, ... i-K, luand 1, 2... K din petalele florii. Fata 1 va alege starea din care poate sa castige cat mai multi trandafiri, adica A[M - D[j]] sa fie maxim, i-K ≤ j ≤ i-1.
Pentru 30 de puncte recurenta se rezolva direct, iar pentru 100 de puncte se foloseste un deque.

Galerie

Solutia 1 : Serban Andrei Stan

Pentru un query (X,Y) ne intereseaza numarul de cartite care vor traversa galeria curenta, mai exact numarul de intervale (P,Q) astfel incat P≤X si Y≤Q. Costul final se va imbunatati cu L_galerie * Nr_cartite. Cum un interval (A,B),A≥B, este echivalent cu un interval (A,B),A≤B, vom interschimba in primul caz pe A cu B.

Pentru a raspunde in mod eficient la fiecare intrebare o sa folosim un AIB. Initial, pentru fiecare vizita (P,Q),vom insera in AIB la pozitia P numarul de cartite care pleaca din P spre Q.
Vom parcurge query-urile in ordine dupa capatul din dreapta, si la fiecare pas vom elimina din aib pozitiile reprezentand vizite cu Q≤Y-1. Numarul de cartite care vor traversa intervalul (X,Y) va fi egal cu suma valorilor ce se afla in AIB pe pozitii ≤P.

Complexitatea finala va fi O(MlogM + TlogT + (M+T)logN).

Solutia 2 : Teodor Anton Pripoae

Vom calcula pentru fiecare intrebare a organizatorilor, cate drumuri ale cartitelor contin acel interval (sa zicem Nr). Costul imbunatatirii va fi Nr * ( lungime_interval - cost_interval ). Pe exemplul din enunt unde merg 2 cartite intre camerele 1 si 4, vor exista 2 drumuri care contin intervalul [1, 3] : Drumul facut de prima cartita, respectiv a doua cartita din camera 1 pana in camera 4.

Acum, trebuie sa vedem cum putem raspunde eficient la intrebarea: Cate drumuri contin un interval cautat de organizatori. Vom retine intervalele ca puncte in plan (atat drumurile cat si intrebarile), coordonata x va fi capatul din stanga, iar coordonata y capatul din dreapta. Pentru ca un interval sa fie cuprins de altul, trebuie ca primul punct sa fie in stanga si deasupra celul de-al doilea. Vom sorta crescator toate cele M + T puncte dupa coordonata x si in caz de egalitate descrescator dupa coordonata y. Acum, pt fiecare punct (interval) cautat, raspunsul va fi numarul de puncte cu aflate inaintea lui in vector care au coordonata y mai mare decat a lui.

Vom proceda ca la subsir descrescator maximal. Vom tine un aib (Arbore indexat binar). La pasul i, vom vedea daca punctul curent( P ) este din cele M, caz in care vom updata pe pozitia corespunzatoare coordonatei P.y in aib numarul de cartite care trec pe acel interval, sau in caz ca este din cele T vom vedea cu ajutorul aib-ului cate drumuri a caror coordonate R.y sunt mai mari decat coordonata P.y a lui: scadem din suma totala, suma pozitiilor pana la P.y - 1.

Solutia are complexitate o((M + T) (log (M + T) + log N)) ca timp si o(N) ca memorie.

Trilant

Pentru doua noduri P,Q din graf, vom defini d(P,Q) ca fiind drumul de cost minim de la P la Q. Pe noi ne intereseaza sa gasim un nod X astfel incat suma d(A,X)+d(B,X)+d(C,X) sa fie minima. Pentru a realiza acest lucru trebuie sa calculam pentru orice nod K din graf d(A,K),d(B,K) si d(C,K). Putem face acest lucru folsind Algoritmul lui Dijsktra. Nodul solutie va fi acel nod X cu proprietatea ca suma d(A,X)+d(B,X)+d(C,X) sa fie minima.

Presupunem ca am ales nodul X cu proprietatea de mai sus. Daca drumurile (X,A) si (X,B) nu ar fi disjuncte, atunci stim sigur ca exista un nod K pe lantul de la X la A, astfel incat drumurile (K,A) si (K,B) sunt disjuncte. Inseamna ca pe drumul de la K la X, vom numara muchiile care apar de doua ori, rezulta ca X nu ar avea proprietatea ca suma d(A,X)+d(B,X)+d(C,X) sa fie minima. Analog daca (X,A) si (X,C) sau (X,B) si (X,C) nu ar fi disjuncte.

Complexitatea solutiei este O(MlogN).