h3. Secv
Subsirul trebuie sa contina toate elementele din sirul original in ordine crescatoare asa ca primul pas este sa ne formam acest subsir C. Avand acest subsir, parcurgem vectorul initial pentru a gasi pozitia de start a noii subsecvente. Dupa ce am gasit o posibila pozitie de start s incercam sa gasim subsirul C avand ca pozitie de start s. Din toate aceste subsecvente o alegem pe aceea cu lungimea minima. Asftel, complexitatea algoritmului ajunge la O(N*M), unde N este lungimea secventei initiale si M lungimea subsirului C. Problema se poate rezolva in aceeasi complexitate si cu programare dinamica, lasam acesta rezolvare ca exercitiu pentru concurenti!
Subsirul trebuie sa contina toate elementele din sirul original in ordine crescatoare asa ca primul pas este sa ne formam acest subsir {$C$}. Avand acest subsir, parcurgem vectorul initial pentru a gasi pozitia de start a noii subsecvente. Dupa ce am gasit o posibila pozitie de start s incercam sa gasim subsirul $C$ avand ca pozitie de start {$s$}. Din toate aceste subsecvente o alegem pe aceea cu lungimea minima. Asftel, complexitatea algoritmului ajunge la {$O(N*M)$}, unde $N$ este lungimea secventei initiale si $M$ lungimea subsirului {$C$}. Problema se poate rezolva in aceeasi complexitate si cu programare dinamica, lasam acesta rezolvare ca exercitiu pentru concurenti!
Car
h3. Car
La prima vedere problema pare simpla si abordabila cu o cautare in latime, dar la o citire mai atenta problema se dovedeste putin mai grea.
Cerinta e una de gasire a drumului minim intr-un graf in care nodurile sunt reprezentate de trei intregi (i,j,dir), i si j avand semnificatia liniei si coloanei din matrice iar dir reprezinta directia cu care am intrat pe pozitia curenta. Muchiile din graful nostru au costurile dupa cum s-a explicat in enunt. Pentru gasirea drumului putem folosi algoritmul Dijkstra care foloseste un heap pentru expandarea nodurilor, complexitatea unei astfel de rezolvari ar fi fost O(N*M lg (N*M)) dar un asemenea algoritm nu ar fi luat punctaj maxim. O observatie care ne poate reduce constanta algoritmului ar fi ca nu are rost sa folosim curbe de 180 sau de 135 de grade, pentru ca am fi ajuns in aceeiasi pozitie mai repede. Pentru a nu folosi memorie prea multa pentru reprezentarea nodurilor in coada noastra de prioritati am putea folosi un singur intreg in loc de trei astfel:
La prima vedere problema pare simpla si abordabila cu o cautare in latime, dar la o citire mai atenta problema se dovedeste putin mai grea. Cerinta e una de gasire a drumului minim intr-un graf in care nodurile sunt reprezentate de trei intregi ({$i,j,dir$}), $i$ si $j$ avand semnificatia liniei si coloanei din matrice iar $dir$ reprezinta directia cu care am intrat pe pozitia curenta. Muchiile din graful nostru au costurile dupa cum s-a explicat in enunt. Pentru gasirea drumului putem folosi algoritmul Dijkstra care foloseste un heap pentru expandarea nodurilor, complexitatea unei astfel de rezolvari ar fi fost $O(N*M lg (N*M))$ dar un asemenea algoritm nu ar fi luat punctaj maxim. O observatie care ne poate reduce constanta algoritmului ar fi ca nu are rost sa folosim curbe de $180$ sau de $135$ de grade, pentru ca am fi ajuns in aceeiasi pozitie mai repede. Pentru a nu folosi memorie prea multa pentru reprezentarea nodurilor in coada noastra de prioritati am putea folosi un singur intreg in loc de trei astfel:
x = ((i - 1) * m + (j - 1)) * 8 + dir
== code(cpp) |x = ((i - 1) * m + (j - 1)) * 8 + dir
==
si decodificarea ar fi
dir = x % 8; x /= 8;
== code (cpp) |dir = x % 8; x /= 8;
j = (x % m) + 1;
i = (x / m) + 1;
==
Pentru a avea o viteza mai mare la codificare si decodificare putem folosi operatii pe biti: dir sa fie reprezentat pe 3 biti i, pe urmatorii 9 biti, iar j pe urmatorii 9 biti (i,j <= 500 < 2^9=512), astfel codificarea si decodificarea devin
x = (i << 9) + j + (dir << 18);
Pentru a avea o viteza mai mare la codificare si decodificare putem folosi operatii pe biti: $dir$ sa fie reprezentat pe $3$ biti {$i$}, pe urmatorii $9$ biti, iar $j$ pe urmatorii $9$ biti ({$i,j ≤ 500 < 2^9^=512$}), astfel codificarea si decodificarea devin
== code(cpp) |x = (i << 9) + j + (dir << 18);
dir = x >> 18;
j = (x & 511);
i = (x >> 9) & 511;
==
Costurile muchiilor in graful nostru sunt mici si un algoritm ca cel
al lui Dijkstra nu tine cont de aceasta proprietate. Daca aceste costuri sunt mici atunci si costul final al drumului de la sursa la destinatie va fi mic deci ne permitem sa folosim pentru fiecare valoare posibila a costului unui drum de la sursa la destinatie cate o lista. Cand am determinat pentru un nod distanta minima de la sursa la el, il inseram intr-o astfel de lista, observam ca expandarea unui astfel de nod poate afecta numai urmatoarele 4 liste (prin expandare ne referim la actualizarea distantei minime de la sursa a vecinilor nodului curent). O astfel de rezolvare ar arata cam asa (pseudo-C):
for (dir =0; dir < 8; dir++)
al lui Dijkstra nu tine cont de aceasta proprietate. Daca aceste costuri sunt mici atunci si costul final al drumului de la sursa la destinatie va fi mic deci ne permitem sa folosim pentru fiecare valoare posibila a costului unui drum de la sursa la destinatie cate o lista. Cand am determinat pentru un nod distanta minima de la sursa la el, il inseram intr-o astfel de lista, observam ca expandarea unui astfel de nod poate afecta numai urmatoarele $4$ liste (prin expandare ne referim la actualizarea distantei minime de la sursa a vecinilor nodului curent). O astfel de rezolvare ar arata cam asa (pseudo-C):
lst[0].add(starti,startj,dir,0);
current_cost = 0;
while (lst[0].size()+lst[1].size()+lst[2].size>0){
while (lst[curent_cost % 3].size()>0) {
x = lst[curent_cost % 3].pop();
expand(x);
}
curent_cost++;
}
== code(cpp) |for (dir =0; dir < 8; dir++)
lst[0].add(starti,startj,dir,0);
current_cost = 0;
while (lst[0].size()+lst[1].size()+lst[2].size>0){
while (lst[curent_cost % 3].size()>0) {
x = lst[curent_cost % 3].pop();
expand(x);
}
curent_cost++;
}
==
Am folosit numai trei liste pentru ca am tinut cont de optimizarea precizata mai sus de a nu folosi numai curbele la 0 grade, 45 grade si 90
grade. Fiecare nod poate fi expandat o singura data, si poate fi introdus in liste de cel mult trei ori, deci o astfel de solutie are complexitatea ca timp si ca spatiu O(N*M). Mergand mai departe pe aceasta idee putem obtine o rezolvare putin mai buna care injumatateste timpul de executie. Costurile au fost alese intr-un mod particular permitand ca o curba de 90 de grade sa aiba acelasi cost cu doua curbe de 45, una de 135 acelasi cost ca trei de 45 si una de 180 acelasi cost ca si patru de 45. Astfel putem modifica rezolvarea noastra si sa facem numai miscarile urmatoare: rotiri de 45 de grade pe loc si miscari in fata pe directia de mers. Astfel procedura de expandare actualizeaza numai trei noduri si in cursul procedurii de actualizare putem sa lucram numai cu lista curenta si cu lista urmatoare, pentru ca efectuam numai miscari de cost zero si unu. Aceasta observatie a micsorat numarul de liste si a micsorat numarul de calcule din metoda expand, cea mai frecvent utilizata in algoritm. O astfel de
