*Care e algoritmul preferat?*

Greu de spus exact, dar voi descrie ceva ce mi-a placut intodeauna foarte mult - algoritmii in timp liniar bazati pe ideea de lista dublu sortata, in care la fiecare pas se insereaza un element nou, stergandu-se mai intain elementele din coada listei care sunt mai "proaste". De exemplu, pentru problema sirului divizat: se da un sir de numere A[1..N], se cere un M maxim astfel incat toate A[1..M-1] sunt mai mici decat A[M] si toate A[M+1..2M] sunt mai mari decat A[M]. Se poate rezolva in timp daca la fiecare pas (pentru fiecare M) putem afla minimul elementelor A[M+1..2M}. Putem rezolva problema in timp liniar daca mentinem o lista dublu sortata pentru a afla la fiecare pas minimul elementelor A[M+1..2M]: lista e sortata crescator dupa valoare si dupa pozitie. Ideea este ca daca in zona curenta de interes avem doua numere A si B, A e la stanga decat B, si A > B, nu ne va mai interesa niciodata A, deci il putem arunca.
Cand inseram un numar nou X mai intai stergem repetat ultimul element al listei pana cand acesta e mai mic ca X, apoi inseram pe X la sfarsitul listei. La fiecare pas se sterge si cate un element de la inceputul listei. Minimul va fi intotdeauna ultimul element din lista. Pentru o problema mai avansata care foloseste aceasta metoda, vedeti problema Batch de la IOI 2002.

Greu de spus exact, dar voi descrie ceva ce mi-a placut intodeauna foarte mult - algoritmii in timp liniar bazati pe ideea de lista dublu sortata, in care la fiecare pas se insereaza un element nou, stergandu-se mai intain elementele din coada listei care sunt mai "proaste". De exemplu, pentru problema sirului divizat: se da un sir de numere A[1..N], se cere un M maxim astfel incat toate A[1..M-1] sunt mai mici decat A[M] si toate A[M+1..2M] sunt mai mari decat A[M]. Se poate rezolva in timp daca la fiecare pas (pentru fiecare M) putem afla minimul elementelor A[M+1..2M}. Putem rezolva problema in timp liniar daca mentinem o lista dublu sortata pentru a afla la fiecare pas minimul elementelor A[M+1..2M]: lista e sortata crescator dupa valoare si dupa pozitie. Ideea este ca daca in zona curenta de interes avem doua numere A si B, A e la stanga decat B, si A > B, nu ne va mai interesa niciodata A, deci il putem arunca. Cand inseram un numar nou X mai intai stergem repetat ultimul element al listei pana cand acesta e mai mic ca X, apoi inseram pe X la sfarsitul listei. La fiecare pas se sterge si cate un element de la inceputul listei. Minimul va fi intotdeauna ultimul element din lista. Pentru o problema mai avansata care foloseste aceasta metoda, vedeti problema Batch de la IOI 2002.

*Cate probleme crezi ca ai rezolvat la viata ta?*