USACO decembrie 2004, divizia GOLD - idei de solutii
(Categoria Competitii, autor(i) Silviu Ganceanu)
Setul de probleme pe marginea caruia voi discuta in urmatoarele randuri se afla disponibil in sectiunea download impreuna cu datele de test si rezultatele finale ale concursului (cei care nu stiu setul de probleme si vor sa citeasca articolul sunt rugati sa parcurga mai intai textele problemelor).
Voi incepe prin cateva observatii in legatura cu evolutia concurentilor din Romania in acest concurs. Asadar un clasament (neoficial) alcatuit intre acestia ar arata in urmatorul mod:
| 1 | Vladu Adrian | 783 puncte |
|---|---|---|
| 2 | Stancu-Mara Sorin | 782 puncte |
| 3 | Andrei-Marius Teodorescu | 710 puncte |
| 4 | Fechete Dan Ionut | 490 puncte |
| 5 | Pasaila Daniel | 436 puncte |
| 6 | Paul Diac | 406 puncte |
Restul concurentilor au avut punctaje sub 400 de puncte. Primii doi din clasamentul "nostru" au reusit sa se strecoare intre primele 20 de locuri din clasamentul final dar, din nou, remarc lipsa unui roman in topul celor mai buni. Sper mai multe de la concursurile viitore! Mai vreau sa precizez ca Romania nu a dispus de tot arsenalul avut in dotare si concurenti cu rezultate in competiile internationale anterioare precum Dan Crestez si Dan Spatarel nu au fost prezenti in concurs (cel putin nu cu numele lor!). Ei sunt rugati sa participe in viitoarele concursuri (sau sa renunte la pseudonime - daca e cazul), spre binele lor si spre prestigiul Romaniei!
Setul de probleme a fost unul dificil dar deosebit de frumos, necesitand cunostinte avansate de programare dinamica, structuri de date si teoria grafurilor. Totusi, pentru un concurent experimentat, problemele nu erau in totalitate noi. Spun asta pentru ca toate problemele aveau in substrat idei deja folosite in alte concursuri (CEOI, IOI si chiar barajele noastre).
Lasand comentariile deoparte sa trecem la ce ne intereseaza cel mai mult: solutiile.
Divide
Problema se rezolva prin programare dinamica. Prima idee, destul de intuitiva de altfel, este o solutie de complexitate O(L * B). Sa notam cu BSTl = numar minim de stropitori de care avem nevoie pentru a acoperi complet intervalul [0, l] cu l par. Avem urmatoarea recurenta:
- BSTl = INFINIT daca l este inclus intr-un interval al unei vaci
- BSTl = minim(BSTl - 2 * x) + 1, cu x intre A si B astfel incat 2 * x este mai mic sau egal cu l
Printr-o implementare directa a recurentei de mai sus obtinem o solutie care foloseste O(L) memorie si O(L * B) operatii (cu observatia ca spatiul de memorie se poate reduce la O(B)).
Pentru a reduce complexitatea la O(L) operatii se utilizeaza o coada care pastreaza valorile BSTx cu x in intervalul [i - 2*B, i - 2*A] sortate crescator. Se observa cum se modifica coada cand se trece de la pozitia i la pozitia i + 2 (practic "intra" valoarea BSTi + 2 - 2*A si "iese" valoarea BSTi - 2*B. Nu voi intra in detalii despre modul cum lucreaza aceasta coada. Pe aceeasi idee (utilizarea acestei cozi) se rezolva si problema secventa (preOJI 2004 - infoarena) si trans (prima proba a selectiei lotului national largit, Buzau 2004).
Obstacle
Si aceasta problema se rezolva tot programare dinamica. Asadar avem BSTi, 0 = distanta minima parcursa pentru a ajunge la capatul din stanga al gardului numarul i si BSTi, 1 = distanta minima parcursa pentru a ajunge la capatul din dreapta al gardului numarul i. De asemenea notam cu Capi, 0 = pozitia capatului din stanga al gardului i in sistemul de coordonte si Capi, 1 = analog pentru capatul din dreapta. Avem urmatoarele recurenta:
- BSTi, j = minim(BSTk, l + dst(Capk, l, Capi, j) cu k de la i + 1 la N, l si j fiind 0 sau 1 si cu proprietatea ca drumul pe Oy dintre Capk, l la gardul $i nu se interpune nici un alt gard.
Aceasta recurenta implementata direct ne da o solutie O(N2) care, putin optimizata, ar fi putut obtine punctajul maxim. Totusi exista o solutie O(N log N) care utilizeaza o structura de date numita arbori de intervale. Practic noi trebuie sa aflam pentru fiecare gard i care este gardul pe care cade o bila lasata libera din capatul din stanga si din capatul din dreapta. Aceste informatii ne permit reducerea complexitatii recurentei de mai sus la O(N) (nu va mai spun cum, ganditi si voi!). Pentru a afla informatiile despre care vorbeam se parcurg cele N garduri de la 1 la N (in ordinea asta!) si se proiecteaza, pe rand, pe axa Ox. Practic se pastreaza axa Ox ca un interval [-200.000, 200.000] si, pentru un gard i, se egaleaza toate pozitiile din intervalul [Capi, 0, Capi, 1] cu i. Pentru un afla gardul pe care cade bila se interogheaza arborele pentru fiecare capat al gardului i. Explicatiile mele nu dezvaluie modul in care lucreaza acest arbore de intervale (mi-ar lua cateva zeci de randuri bune daca as intra in detalii). Pentru cei care nu au idee cum functioneaza acest "monstru informatic" le recomand citirea articolului scris pe tema aceasta din sectiunea Download.
Skiarea
Problema se poate rezolva utilizand cunostinte de teoria grafurilor. Mai intai se contruiesc componentele conexe ale fiecarei celule printr-un algoritm de tipul FLOOD FILL. Prin componenta conexa intelegem set de celule din matrice cu aceeasi valoarea si care indeplineste propietatea ca intre oricare doua celule exista drum (dupa regulile din enunt). Odata aflate aceste componente conexe se construieste un graf asociat lor in urmatorul mod:
- fiecare componenta conexa are asociat un nod
- intre doua noduri x si y exista drum daca componenta conexa asociata lui x este "vecina" cu componenta conexa a lui y (este usor de intuit ce inseamna "vecina") si daca valoarea celulelor din x este mai mare decat valoarea celulelor din y.
Graful astfel construit este aciclic (acesta se demostreaza usor). In acest graf aflam nodurile in care nu intra nici o muchie - noduri "sursa" - (fie numarul lor P) si toate nodurile din care nu iese nici o muchie - noduri "destinatie" - (fie numarul lor Q). Solutia pentru problema noastra va fi:
- maxim dintre P si Q, daca graful are doua sau mai multe noduri
- 0, daca graful are un singur nod.
Toate cele trei etape (FLOOD FILL-ul, construirea grafului, aflarea nodurilor "sursa" si "destinatie") se pot realiza in O(N*M) operatii utilizand O(N*M) spatiu de memorie. Mare atentie insa: nici unul dintre pasi nu trebuie realizat recursiv!! (pentru ca altfel se iese din segmentul de stiva pe testele mari).
