h3. Critice
Problema este o aplicatie a algoritmului de aflare a fluxului maxim dintr-o retea. Se construieste o retea, nodurile fiind adaposturile iar capacitatile muchiilor fiind egale cu rezistentele tunelurilor. Prima solutie, care trece ~ 50% din teste, este urmatoarea:
Problema este o aplicatie a algoritmului de aflare a fluxului maxim dintr-o retea. Se construieste o retea, nodurile fiind adaposturile iar capacitatile muchiilor fiind egale cu rezistentele tunelurilor. Prima solutie, care trece $~ 50%$ din teste, este urmatoarea:
# Se calculeaza fluxul maxim in reteau construita
# Pentru fiecare muchie (separat) se creste capacitatea ei cu o unitate si se mai ruleaza inca o data algoritmul de flux maximi. Daca fluxul maxim a crescut atunci muchia este critica.
Se observa ca acest algoritm are o complexitate considerabila si trebuie sa ne gandim la ceva mai bun. Primul lucru inteligent pe care il putem observa este ca muchiile critice sunt muchiile care, dupa ce am rulat odata algoritmul de flux maxim, sunt saturate (am folosit toata capacitatea ei intr-o directie sau cealalta). Totusi nu toate muchiile saturate sunt si critice. Pentru a fi mai exacti, muchiile critice sunt acele muchii saturate care au propietatea ca de la sursa retelei (nodul 1) este drum in graful rezidual (adica graful care ne ramane daca eliminam muchiile saturate) la unul din capetele ei si respectiv de la destinatie (nodul N) la celalalt capat. Asadar se contureaza algoritmul:
Se observa ca acest algoritm are o complexitate considerabila si trebuie sa ne gandim la ceva mai bun. Primul lucru inteligent pe care il putem observa este ca muchiile critice sunt muchiile care, dupa ce am rulat odata algoritmul de flux maxim, sunt saturate (am folosit toata capacitatea ei intr-o directie sau cealalta). Totusi nu toate muchiile saturate sunt si critice. Pentru a fi mai exacti, muchiile critice sunt acele muchii saturate care au propietatea ca de la sursa retelei (nodul {$1$}) este drum in graful rezidual (adica graful care ne ramane daca eliminam muchiile saturate) la unul din capetele ei si respectiv de la destinatie (nodul {$N$}) la celalalt capat. Asadar se contureaza algoritmul:
# Se ruleaza odata algoritmul de flux maxim
# Cu ajutorul a doua parcurgeri a grafului rezidual stabilim pentru fiecare muchie critica daca propietatea este adevarata
Complexitatea (teoretica) va fi O(M^2*N + M) dar este supraestimata algoritmul de flux ruland mult mai rapid.
Complexitatea (teoretica) va fi $O(M^2^*N + M)$ dar este supraestimata algoritmul de flux ruland mult mai rapid.
h3. Ferma
La prima vedere, problema pare abordabila cu programare dinamica. O simpla rezolvare care nu tine cont de faptul ca sirul este circular este urmatoarea: A(i, j) = productivitatea maxima pentru a face i strangeri din primele j sectoare; evident raspunsul va fi A(K, N). Relatia de recurenta:
La prima vedere, problema pare abordabila cu programare dinamica. O simpla rezolvare care nu tine cont de faptul ca sirul este circular este urmatoarea: $A{~i,j~}$ = productivitatea maxima pentru a face $i$ strangeri din primele $j$ sectoare; evident raspunsul va fi {$A(K, N)$}. Relatia de recurenta:
A(i, j) = max (A(i, j-1), A(i-1, k) + suma P(k),P(k+1)..P(j)) pentru fiecare k<j, iar P reprezinta vectorul de productivitati.
* $A{~i,j~}$ = $max (A{~i,j-1~}, A{~i-1,k~} + suma P{~k~},P{~k+1~}..P{~j~})$ pentru fiecare {$k<j$}, iar $P$ reprezinta vectorul de productivitati.
O astfel de implementare are complexitate O(N^2*K) si nu se va incadra in timp. Fie S(i) = P(1)+P(2)+...P(i), atunci putem rescrie relatia de recurenta astfel:
O astfel de implementare are complexitate $O(N^2^*K)$ si nu se va incadra in timp. Fie {$S{~i~} = P{~1~}+P{~2~}+...P{~i~}$}, atunci putem rescrie relatia de recurenta astfel:
A(i, j) = max(A(i, j-1), A(i-1, k) + S(j) - S(k)), pentru fiecare k<j
* {$A{~i,j~} = max(A{~i,j-1~}, A{~i-1,k~} + S{~j~} - S{~k~})$}, pentru fiecare $k<j$
Al doilea termen este de forma A(i-1, k) - S(k) (termen independent de j) + S(j). Astfel din linia i-1 a matricii de dinamica pentru fiecare j ne trebuie valoarea maxima A(i-1, k)-S(k) cu k<j. O prima idee ar fi ca pe masura ce construim linia i sa inseram elementele din linia i-1 intr-un max-heap astfel reducand complexitatea la O(N*lgN*K).
Al doilea termen este de forma $A{~i-1,k~} - S{~k~}$ (termen independent de {$j$}) + {$S{~j~}$}. Astfel din linia $i-1$ a matricii de dinamica pentru fiecare $j$ ne trebuie valoarea maxima $A{~i-1,k~}-S{~k~}$ cu {$k<j$}. O prima idee ar fi ca pe masura ce construim linia i sa inseram elementele din linia $i-1$ intr-un max-heap astfel reducand complexitatea la {$O(N*lgN*K)$}.
Cei care au rezolvat probleme precum "secventa" de pe info-arena, "trans" de la barajul de la ONI 2004 sau "divide" de la USACO Ianuarie 2005 vor realiza imediat ca putem reduce complexitatea la O(N*K) folosind structura necesara in rezolvarea acelor probleme si anume o coada (in literatura de specialitate se intalneste ca "deque with heap order"). Aceasta structura a mai fost tratata si in solutiilor problemelor prezentate mai sus, deci nu voi intra in detalii. Este evident ca un algoritm de complexitate O(N*K) se incadreaza in timp, dar mai apare in calcul faptul ca sirul este circular. Un algoritm O(N*K) care nu trateaza acest lucru ia 40 de puncte. O prima idee ar fi sa aplicam acelasi algoritm pe fiecare permutare circulara dar se ridica complexitatea iar la O(N^2*K). Aceasta abordare ar trebui sa obtina intre 50 si 60 de puncte. Putem trata circularitatea sirului tot in O(N*K) incercand sa obtinem o secventa care contine elemente N si 1. Putem realiza acest lucru astfel:
Cei care au rezolvat probleme precum "secventa":http://www.infoarena.ro/task/secventa de pe info-arena, "trans":http://www.infoarena.ro/task/trans de la barajul de la ONI 2004 sau divide de la USACO Ianuarie 2005 vor realiza imediat ca putem reduce complexitatea la $O(N*K)$ folosind structura necesara in rezolvarea acelor probleme si anume o coada (in literatura de specialitate se intalneste ca "deque with heap order"). Aceasta structura a mai fost tratata si in solutiilor problemelor prezentate mai sus, deci nu voi intra in detalii. Este evident ca un algoritm de complexitate $O(N*K)$ se incadreaza in timp, dar mai apare in calcul faptul ca sirul este circular. Un algoritm $O(N*K)$ care nu trateaza acest lucru ia $40$ de puncte. O prima idee ar fi sa aplicam acelasi algoritm pe fiecare permutare circulara dar se ridica complexitatea iar la {$O(N^2^*K)$}. Aceasta abordare ar trebui sa obtina intre $50$ si $60$ de puncte. Putem trata circularitatea sirului tot in $O(N*K)$ incercand sa obtinem o secventa care contine elemente $N$ si {$1$}. Putem realiza acest lucru astfel:
* dupa ce realizam prima data dinamica, reinitializam linia 1 astfel A(1, i) = S(i)
* aplicam din nou dinamica -> de data aceasta algoritmul va fi obligat sa intoarca rezultate care contin neaparat elementul 1 intr-o secventa din cauza initializarii
* pentru fiecare pozitie i<=N comparam rezultatul A(i, K)+S(N)-S(i) (adaugam la secventa care il contine pe 1 o bucata care il contine pe N) cu cel mai bun obtinut
* dupa ce realizam prima data dinamica, reinitializam linia $1$ astfel $A{~1,i~} = S{~i~}$
* aplicam din nou dinamica -> de data aceasta algoritmul va fi obligat sa intoarca rezultate care contin neaparat elementul $1$ intr-o secventa din cauza initializarii
* pentru fiecare pozitie $i ≤ N$ comparam rezultatul $A{~i,K~}+S{~N~}-S{~i~}$ (adaugam la secventa care il contine pe $1$ o bucata care il contine pe {$N$}) cu cel mai bun obtinut
Astfel, problema este rezolvabila in complexitate O(N*K).
Astfel, problema este rezolvabila in complexitate {$O(N*K)$}.
h3. Poligon
Problema cere sa determinam cate puncte din cele M sunt in interiorul poligonului. O abordare imediata a acestei probleme ar fi sa determinam pentru fiecare punct in O(N) daca este sau nu in interiorul poligonului. Exista mai multe moduri de a rezolva acest lucru. Un mod ar fi sa ducem o semidreapta pornind din punctul nostru si sa vedem de cate ori intersecteaza laturile poligonului: daca intersecteaza poligonul de un numar par de ori atunci inseamna ca punctul este in exterior, iar daca ea intersecteaza de un numar impar de ori laturile poligonului inseamna ca punctul este in interior. O alta modalitate: calculam suma unghiurilor pe care le fac extremele laturilor cu punctul nostr (unghiurile sunt luate pozitive sau negative dupa cum cele 3 puncte ce formeaza unghiul sunt in sens trigonometric sau orar), daca suma unghiurilor pentru toate laturile e 0 atunci punctul e in exteriorul poligonului, iar daca suma unghiurilor e 2*Pi atunci punctul e in interiorul poligonului, pentru mai multe detalii puteti
Problema cere sa determinam cate puncte din cele $M$ sunt in interiorul poligonului. O abordare imediata a acestei probleme ar fi sa determinam pentru fiecare punct in $O(N)$ daca este sau nu in interiorul poligonului. Exista mai multe moduri de a rezolva acest lucru. Un mod ar fi sa ducem o semidreapta pornind din punctul nostru si sa vedem de cate ori intersecteaza laturile poligonului: daca intersecteaza poligonul de un numar par de ori atunci inseamna ca punctul este in exterior, iar daca ea intersecteaza de un numar impar de ori laturile poligonului inseamna ca punctul este in interior. O alta modalitate: calculam suma unghiurilor pe care le fac extremele laturilor cu punctul nostru (unghiurile sunt luate pozitive sau negative dupa cum cele $3$ puncte ce formeaza unghiul sunt in sens trigonometric sau orar), daca suma unghiurilor pentru toate laturile e $0$ atunci punctul e in exteriorul poligonului, iar daca suma unghiurilor e $2*Pi$ atunci punctul e in interiorul poligonului, pentru mai multe detalii puteti
sa va uitati pe urmatoarele pagini:
http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm
"[1]":http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
"[2]":http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm
Dimensiunile datelor de intrare ne sugereaza ca trebuie sa acceleram determinarea pozitiei punctelor fata de poligon. Daca poligonul ar fi convex, este usor sa facem acest test in O(log N): consideram un varf al poligonului si semidrepte ce pleaca din el spre celelalte varfuri, cu cautare binara gasim in ce sector determinat de doua semidrepte intra punctul pentru care vrem sa determinam incluziunea in poligon, dupa ce gasim sectorul testul de incluziune se reduce la determinarea incluziunii intr-un triunghi. Aceasta metoda eleganta si simpla merge pentru poligon convex, dar pentru unul oarecare trebuie sa gasim o alta abordare.
Dimensiunile datelor de intrare ne sugereaza ca trebuie sa acceleram determinarea pozitiei punctelor fata de poligon. Daca poligonul ar fi convex, este usor sa facem acest test in {$O(log N)$}: consideram un varf al poligonului si semidrepte ce pleaca din el spre celelalte varfuri, cu cautare binara gasim in ce sector determinat de doua semidrepte intra punctul pentru care vrem sa determinam incluziunea in poligon, dupa ce gasim sectorul testul de incluziune se reduce la determinarea incluziunii intr-un triunghi. Aceasta metoda eleganta si simpla merge pentru poligon convex, dar pentru unul oarecare trebuie sa gasim o alta abordare.
Pentru poligoane concave, mergand pe aceeasi idee, impartirea in zone pentru care este mai usor sa determinam incluziunea se va face un pic diferit. Sortam coordonatele x ale punctelor poligonului si ducem prin fiecare coordonata x distincta cate o dreapta verticala. Se formeaza astfel niste benzi verticale intersectate de laturile poligonului. Pentru fiecare banda tinem minte ce laturi ale poligonului intersecteaza aceasta banda si sortam aceste laturi pe verticala dupa mijlocul segmentului de intersectie al laturii cu banda. Acum pentru a determina daca un punct e in interiorul poligonului, determinam cu cautare binara mai intai banda din care face parte si apoi pentru banda respectiva deasupra cator segmente se afla, daca punctul e deasupra unui numar par de segmente atunci punctul e in exterior si daca e deasupra unui numar impar e interior. Astfel rezolvarea noastra are complexitatea O(N^2 log N) in faza de preprocesare si O(log N) pentru a determina pentru fiecare punct daca este interior sau
exterior poligonului. Complexitatea totala va fi O(N^2 log N + M log N).
Pentru poligoane concave, mergand pe aceeasi idee, impartirea in zone pentru care este mai usor sa determinam incluziunea se va face un pic diferit. Sortam coordonatele $x$ ale punctelor poligonului si ducem prin fiecare coordonata $x$ distincta cate o dreapta verticala. Se formeaza astfel niste benzi verticale intersectate de laturile poligonului. Pentru fiecare banda tinem minte ce laturi ale poligonului intersecteaza aceasta banda si sortam aceste laturi pe verticala dupa mijlocul segmentului de intersectie al laturii cu banda. Acum pentru a determina daca un punct e in interiorul poligonului, determinam cu cautare binara mai intai banda din care face parte si apoi pentru banda respectiva deasupra cator segmente se afla, daca punctul e deasupra unui numar par de segmente atunci punctul e in exterior si daca e deasupra unui numar impar e interior. Astfel rezolvarea noastra are complexitatea $O(N^2^ log N)$ in faza de preprocesare si $O(log N)$ pentru a determina pentru fiecare punct daca este interior sau
exterior poligonului. Complexitatea totala va fi {$O(N^2^ log N + M log N)$}.
