Pagina principala | Inscriere | Autentificare | Probleme | Clasament pe runde | Clasament | Anunturi | Echipa | Regulament | Linkuri


Vizualizare solutie

Titlul problemei: leaves
Numarul problemei: 2
Runda: Runda 5 - pregatire
Solutie: Solutia este O(N*K).

Incepem de la solutia banala, dinamica de O(N^2 * K), pe care o optimizam.

Fie A[i][j] = costul minim pentru a aduna primele i frunze in j gramezi.

A[i][j] = min(A[k-1][j-1] + cost(k, i) (si anume costul de a aduna frunzele de la k la i intr-o gramada in k))

In scrierea de mai sus consideram k pentru care se obtine minimul ca fiind "tatal" lui A[i][j].

Incepem prin a observa ca daca un tata nu mai este bun pentru A[i][j], pe masura ce i creste, atuci urmatorul tata va fi in dreapta.

Scriem ce inseamna ca un tata k1 este mai bun decat alt tata k2 (k1 < k2). Consideram ca suntem la pasul j (trebuie sa grupam in j gramezi), g[x] = greutatea frunzei x

A[k1-1][j-1] + suma(x de la k1 la i, g[x] * (x-k1)) < A[k2-1][j-1] + suma(x de la k2 la i, g[x] * (x-k2))

Aceasta se poate rescrie ca:

(A[k1-1][j-1] - A[k2-1][j-1] + cost(k1,k2-1)) / (k2-k1) + suma(x de la 1 la k2-1, g[x]) < -suma(x de la 1 la i, g[i])

adica un g(k1, k2) < f(i) (g este functie reala)

Avand acesta proprietate putem construi un deque (double end queue). In aceasta stiva/coada inseram elemente in dreapta si scoatem atat prin stanga cat si prin dreapta.

Fie q aceasta stiva/coada. In ea vom avea la un moment dat k1, k2, .., kr cu proprietea:

f(i) > g(k1, k2) > g(k2, k3) > .. > g(kr-1, kr)

Deci la fiecare pas (pentru fiecare i):

1. inseram in dreapta lui q pe i (scotand eventualele elemente ca relatia de mai sus sa se pastreze)

2. eliminam in stanga elemente pana cand f(i) > g(primul element, al doilea element)

Cel mai bun tata pentru f(i) se va afla in stanga lui q.

Intrucat fiecare element este introdus o data si scos o data rezulta complexitatea de O(N * K).

Pentru mai multe detalii despre acest gen de procedee cititi intai problema batch (ioi 2002).

Pentru si mai multe detalii vedeti sursa din arhiva de teste.

Pentru fiecare test de evaluare s-au acordat 10 puncte.

Inapoi

© 2002 - 2005 Vālsan Mihai Liviu
Puteti trimite intrebari, comentarii, sau sugestii la adresa liviuvalsan@yahoo.com