h1. USACO oct 2005, divizia GOLD

(Creat de ==user(user="greco" type="tiny")== la data de _2005-11-21_ categoria _Competitii_, autor(i) _Florea Tiberiu_)

(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.

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

p(pre). D{~sursa~} <- 0

==code(cpp) |
D{~sursa~} <- 0

heap_sz = 1
heap{~heap_sz~} <- sursa
pentru $i$ de la $1$ la $N$

        pentru i de la 1 la N
            daca D{~i~} > D{~x~} + cost (x, i)
                descreste_cheie (i, D{~x~} + 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.

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):

p(pre). sol = 0, nr <- 0

==code(cpp) |
sol = 0, nr <- 0

pentru i de la 1 la N
    cat timp nr > 0 si v{~nr~} = i
        sol <- sol + 1

        v{~nr + 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.