USACO oct 2005, divizia GOLD

(Categoria Competitii, autor(i) Florea Tiberiu)

Ca de obicei, USACO debuteaza in luna octombrie cu un concurs prin care oricine se poate califica la o divizie superioara celei in care se afla.

Romania a avut 8 concurenti care s-au calificat (sau recalificat) la divizia GOLD, fiind depasita in acest clasament doar de China (16) si SUA (10). Bineinteles, acest clasament nu este foarte relevant, deoarece multi dintre cei calificati deja au preferat sa nu participe sau sa nu ia concursul foarte in serios.

Elevii romani care au obtinut punctajul necesar pentru (re)calificare sunt:

  • Andrei Teodorescu (andreit1)
  • Vladu Adrian (azotlic1)
  • Andrei Blanaru (blanaru1)
  • Sorin Fagateanu (cyronon1)
  • Ionel Corneliu Gog (gogione1)
  • Tiberiu Florea (greco2)
  • Pasoi Mircea (mircea_1)
  • Vlad Berteanu (vladcyb1)

Proba a constat in 2 probleme de nivel mediu care trebuiau rezolvate in 2 ore.

Skiing

Prima rezolvare care ne vine in minte citind o astfel de problema este transformarea matricii intr-un graf cu R * C noduri si calcularea drumului minim dintre nodurile (1, 1) si (R, C). O observatie destul de evidenta este ca toate muchiile care intra intr-un nod (a, b) vor avea acelasi cost, adica V * 2 H1,1 - Ha,b. Deoarece implementarea obisnuita a algoritmului Dijkstra are complexitatea O (N2 + M) considerand N = numarul de pozitii si M numarul de muchii dintre acestea (N = R * C, M = 4 * R * C - 2 * (R + C)) va trebui implementata varianta in care se foloseste o coada de prioritate pentru nodurile care nu au fost explorate deja: implementand varianta cu heap-uri vom obtine complexitatea O((N + M) * lg N), care se incadreaza in timp.

Pentru cei care nu sunt familiari cu aceasta varianta a algoritmului, ea arata cam asa:

Dsursa <- 0
heap_sz = 1
heapheap_sz <- sursa
pentru i de la 1 la N
daca i != sursa
Di <- oo
heap_sz <- heap_sz + 1
heap[heap_sz] <- i
cat timp heap_sz > 0
x <- extrage_min (heap)
daca x = destinatie
returneaza Dx
altfel
pentru i de la 1 la N
daca Di > Dx + cost (x, i)
descreste_cheie (i, Dx + cost (x,i))

Fiecare nod este extras cel mult o data din heap, si pentru fiecare muchie este apelata cel mult o data functia descreste_cheie. Fiecare dintre aceste operatii se efectueaza in O(lg N), de aici rezultand complexitatea dorita.

De asemenea, putea fi aplicata o alta varianta a algoritmului Dijkstra, care profita mai mult de specificul problemei: In afara de vectorul estimarilor distantelor pana la fiecare nod, se memoreaza si nodul cu estimarea minima de pe fiecare din cele R linii. Astfel, in momentul in care se extrage fiecare nod, cautam minimul in acest vector de dimensiune R, iar apoi reactualizam valoarea liniei pe care se afla nodul curent. Complexitatea acestui algoritm este O(N * R), adica O(R2 * C).

In implementarea oricaruia dintre acesti algoritmi trebuiau avute in vedere eventualele probleme cu precizia calculelor; o idee buna era ca numai costul final sa se inmulteasca cu V.

Flying right

Aceasta problema poate fi rezolvata cu ajutorul unui algoritm greedy, ideea nu este greu de gasit sau demonstrat, insa la implementare pot aparea unele probleme. In primul rand trebuie sa remarcam ca cele doua parti ale problemei se vor rezolva independent una de cealalta, drumurile se vor imparti in 2 multimi (cele de dimineata, si cele de seara), si se va aplica aceeasi rezolvare pentru fiecare din cele doua multimi, raspunsul final fiind suma celor doua rezultate partiale. Rezolvarea urmatoare trateaza calcularea rezultatului optim pentru drumurile de dimineata.

Pentru fiecare din cele N ferme tinem o lista de grupuri care doresc sa plece din orasul respectiv si sortam aceste liste crescator dupa indicele destinatiei fiecarui grup. Parcurgem in ordine cele N ferme, memorand numarul si destinatiile vacilor care se afla la un moment dat in avion, sortate in ordine descrescatoare. In momentul in care am ajuns la ferma i, primul lucru pe care trebuie sa il facem este sa dam jos vacile care au ajuns la destinatie, incrementand corespunzator solutia de pana atunci. Evident, vacile care coboara la ferma respectiva se vor afla pe ultimele pozitii in ordinea descrisa din avion. Urmatorul pas este sa luam in avion din vacile care pleaca de la ferma i pana cand acestea sunt epuizate sau capacitatea avionului este saturata. Daca au mai ramas vaci care nu au avut loc in avion, atata timp cat putem lua o vaca a carei destinatie este mai apropiata decat cea mai departata dintre destinatiile vacilor care se afla deja in avion, consideram ca vaca respectiva din avion nu a fost luata deloc, si ca alocam locul ei noii vaci, care va cobori mai repede.

Este usor de vazut ca algoritmul de mai sus produce o solutie optima, insa implementarea sa nu este foarte lejera. Putem folosi urmatoarea metoda (v este un vector in care retinem destinatiile vacilor care se afla in avion, sortate descrescator):

sol = 0, nr <- 0
pentru i de la 1 la N
cat timp nr > 0 si vnr = i
sol <- sol + 1
nr <- nr - 1
pentru j <- 1, j ≤ C si j ≤ nr vaci ce asteapta sa plece de la ferma i
nr <- nr + 1
vnr + 1 = distanta celei de-a j-a vaci (in ordinea crescatoare a destinatiilor) de la ferma i
sorteaza v
pastreaza primele maxim C pozitii din v

La fiecare pas, vectorul v poate fi sortat folosind qsort (stdlib.h) sau sort (algorithm). Este necesar sa adaugam in v doar primele C vaci de la ferma i, deoarece daca o vaca nu este intre primele C din multimea vacilor de la ferma i, este evident ca nu va fi nici intre primele C din reuniunea acestei multimi cu multimea vacilor aflate deja in avion.

Sa recapitulam pasii algoritmului, alaturi de complexitatea fiecaruia dintre ei:

  • sortarea tuturor grupurilor dupa destinatie: O(K * lg K)
  • parcurgerea grupurilor si inserarea in listele corespunzatoare: O(K)
  • parcurgerea fermelor de la 1 la N, aplicand procedeul descris: O(N * C * lg C)

Asadar, complexitatea totala a algoritmului este de O(K * lg K + N * C * lg C), dand un timp de rulare rezonabil si o implementare fara mari batai de cap.