S-a incheiat "prima runda":http://infoarena.ro/winter-challenge-2008/runda-1 a concursului "Winter Challenge":http://infoarena.ro/winter-challenge-2008/. Se pare ca problemele au fost "frumoase", desi concursul a fost organizat "pe fuga". Runda viitoare promit sa fie organizata mai din timp.

S-a incheiat "prima runda":winter-challenge-2008/runda-1 a concursului "Winter Challenge":winter-challenge-2008/. Se pare ca problemele au fost "frumoase", desi concursul a fost organizat "pe fuga". Runda viitoare promit sa fie organizata mai din timp.

Felicitarii "tuturor participantilor":http://infoarena.ro/winter-challenge-2008/clasament si, in special, primilor 3 clasati:

Felicitarii "tuturor participantilor":winter-challenge-2008/clasament si, in special, primilor 3 clasati:

==Rankings(rounds="winter2008-1" display_entries="3" pager_style="none")==
Speram ca in runda a doua sa obtineti punctaje mai mari, problemele vor avea nivelul celor de la ONI. Din pacate, si numarul de participanti a fost scazut, dar speram ca pe viitor vor fi mai multi concurenti. Daca aveti pareri sau sugestii despre aceasta runda exrpimati-le pe "forum":http://infoarena.ro/forum/index.php?topic=2637.0.

As vrea sa le multumesc lui "Adrian Airinei":http://infoarena.ro/utilizator/astronomy si lui "Andrei Grigorean":http://infoarena.ro/utilizator/wefgef pentru sprijinul acordat, si, totodata, intregii "echipe infoarena":http://infoarena.ro/echipa-infoarena.

As vrea sa le multumesc lui "Adrian Airinei":utilizator/astronomy si lui "Andrei Grigorean":utilizator/wefgef pentru sprijinul acordat, si, totodata, intregii "echipe infoarena":echipa-infoarena.

{@  @}
{@  @}

{@  @}
{@  @}

In continuare vom prezenta solutiile oficiale ale problemelor. Daca aveti nelamuriri puteti cere explicatii suplimentare pe "forum":http://infoarena.ro/forum/.

In continuare vom prezenta solutiile oficiale ale problemelor. Daca aveti nelamuriri puteti cere explicatii suplimentare pe "forum":forum/.

h2. 'Primar':problema/primar (problema usoara)

Complexitatea primei parti este $O(N * log{~2~}N)$ pentru sortare, iar complexitatea celei de-a doua parti este $O(N)$. In total, complexitatea algoritmului este $O(N * log{~2~}N)$.

h2. 'Jetoane2':problema/jetoane2 (probelma medie)

h2. 'Jetoane2':problema/jetoane2 (problema medie)

Problema se rezolva prin programare dinamica. Vom considera $2$ matrici:

Complexitatea solutiei este $O(N * L^3^ * CONST)$, unde $L$ reprezinta lungimea sirului initial, iar CONST = 10.

Exista si o solutie de complexitate $O(N * L^3^)$, care, in practica, merge mai repede. Aceasta solutie a fost data de catre "Cosmin Gheorghe":http://infoarena.ro/utilizator/gcosmin si o voi publica imediat dupa ce primesc acordul sau.

Exista si o solutie de complexitate $O(N * L^3^)$, care, in practica, merge mai repede. Aceasta solutie a fost data de catre "Cosmin Gheorghe":utilizator/gcosmin si o voi publica imediat dupa ce primesc acordul sau.

h2. 'Tero':problema/tero (problema grea)

Dupa cum multi si-au dat seama, problema este asemanatoare cu cea a lui Dan Ionut Fechete, "Trafic":http://infoarena.ro/problema/trafic.

Dupa cum multi si-au dat seama, problema este asemanatoare cu cea a lui Dan Ionut Fechete, "Trafic":problema/trafic.

Fiind niste limite de timp foarte mari, "cautare binara + flux":http://campion.edu.ro/problems.php?mode=view_solution&problem_id=279&group_number=3&year=2005 nu intra in timp.

Pentru a se incadra in limita stabilita, era necesar algoritmul lui Karzanov pentru flux maxim intr-o retea. Acest algoritm a fost prezentat in cadrul taberei de pregatire a Lotului National, de catre Mugurel Ionut Andreica ("Algoritmi de flux maxim in retele":http://infoarena.ro/downloads) si constituie o mica parte din teza sa de Masterat.

Pentru a se incadra in limita stabilita, era necesar algoritmul lui Karzanov pentru flux maxim intr-o retea. Acest algoritm a fost prezentat in cadrul taberei de pregatire a Lotului National, de catre Mugurel Ionut Andreica ("Algoritmi de flux maxim in retele":downloads) si constituie o mica parte din teza sa de Masterat.

Presupunem, intial, ca pe fiecare muchie poate fi plasat +doar un singur soldat+. Cum $S$ < $M$, acest lucru este intotdeauna posibil. Astel, fiecarei muchii i se va atribui capacitatea $1$. Rulam algoritmul de flux maxim si retinem fluxul. Calculam, pentru fiecare muchie, maximul dintre distantele de la aceasta pana la nodul $1$ si pana la nodul $N$, apoi sortam descrescator muchiile, in functie de aceasta valoare.
In continuare, vom incerca sa gasim pozitia soldatului care ajunge ultimul in orasul atacat, parcurgand muchiile in ordinea sortarii: pentru o muchie $e$, vrem sa stabilim daca, pozitionand mai mult de un soldat pe ea (crescand capacitatea la o valoare foarte mare), va creste sau nu fluxul initial. Daca nu va modifica valoarea fluxului, inseamna ca putem pune oricati soldati pe $e$, fara a influenta rezultatul final, deci muchia este inutila. Daca modifica valoarea fluxului, asta inseamna ca cel mai lenes soldat trebuie sa fie pozitionat pe $e$ si afisez valoarea maximului dintre distante pentru muchia respectiva.

Pentru a avea o complexitate +teoretica+ de O(M*N^3) (in practica merge cu mult mai repede), va trebui sa facem doua optimizari:

Pentru a avea o complexitate +teoretica+ de $O(M*N^3)$ (in practica merge cu mult mai repede), va trebui sa facem doua optimizari:

# se va reface reteaua reziduala L0 (vezi articolul lui Mugurel) +doar daca exista un drum nesaturat, ce contine muchia $e$+
# pentru a verifica daca fluxul creste, nu se va relua tot algoritmul de flux maxim, ci se vor folosi informatiile anterior calcualte.

Desi nu ar fi trebuit sa ia decat $30$ de puncte, in solutia prezentata de Ionut Fechete, se putea inlocui Edmond-Karp cu algoritmul lui Dinic (vezi articolul lui Mugurel), obtinandu-se astfel punctaj maxim. Singurul care a facut acest lucru in concrus (si singurul care a obtinut punctaj maxim la aceasta problema), a fost "Bogdan Tataroiu":http://infoarena.ro/utilizator/bogdan2412.

Desi nu ar fi trebuit sa ia decat $30$ de puncte, in solutia prezentata de Ionut Fechete, se putea inlocui Edmond-Karp cu algoritmul lui Dinic (vezi articolul lui Mugurel), obtinandu-se astfel punctaj maxim. Singurul care a facut acest lucru in concrus (si singurul care a obtinut punctaj maxim la aceasta problema), a fost "Bogdan Tataroiu":utilizator/bogdan2412.

In arhiva se vor schimba testele astfel incat aceasta solutie sa nu obtina punctaj maxim.