infoarena informatica de performanta

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

Felicitarii tuturor participantilor si, in special, primilor 3 clasati:

Pozitie	Nume	Scor
1	Bogdan-Cristian Tataroiu •bogdan2412	239
2	Gheorghe Cosmin •gcosmin	160
3	Victor Rusu •victorsb	120

Speram ca runda viitoare sa obtineti punctaje mai mari. Din pacate, si numarul de participanti a fost mai scazut ca anul trecut, dar speram ca la Runda 2 sa fie mai multi concurenti. Daca aveti pareri si sugestii despre aceasta runda exrpimati-le pe forum.

Nu in ultimul rand as vrea sa le multumesc lui Adrian Airinei si lui Andrei Grigorean pentru suportul tehnic acordat, si, totodata intregii echipe infoarena.

Mult succes in continuare,
Echipa Winter Challenge.

Primar (problema usoara)

Contrar punctajelor, aceasta a vrut sa fie problema usoara a setului.

Problema are doua parti: aflarea discriminarii minime, si gasirea componentei optime.

Pentru prima parte era nevoie de observatia ca, discriminarea pe o ulita este fie 0, fie 1. 0 era in cazul in care ulita avea un numar par de case (alegeam din prima casa un barbat, apoi o femeie, etc.) si, repsectiv, 1, cand pe ulita erau un numar impar de case.

Partea a doua necesita o analiza mai atenta. Prima solutie se bazeaza pe teoria grafurilor. Vom construi un graf bipartit, unde nodurie din partea stanga sunt reprezentate de dreptele paralele cu OX, iar nodurile din partea dreapta sunt reprezentate de dreptele paralele cu OY. Intre un nod din stanga si un nod din dreapta va exista muchie doar daca la intersectia celor doua drepte se afla o casa. Se porneste dintr-un nod cu grad impar, marcand alternativ muchiile (casele) cu 0 sau 1 si eliminandu-le. Raman, astfel, numai noduri cu grad par, care vor forma cicluri, dar care se pot rezolva folosind, din nou, algoritmul de mai sus.
O alta rezolvare pentru partea a doua, este urmatoarea:
Se pleaca dintr-un punct nemarcat si se marcheaza cu 0; se merge, pe dreapta, paralel cu OX, in urmatorul punct nemarcat, care se marcheaza cu 1; se merge, apoi, pe dreapta, paralel cu OY, in urmatorul punct nemarcat si se marcheaza cu 0, etc. Pentru o complexitate eficienta, punctele se pot tine ca niste liste, ale caror campuri retin urmatorul punct nemarcat pe OX, si urmatorul punct nemarcat pe OY. Daca unii utilizatori InfoArena, nu sunt obisnuiti cu implementarea listelor, pot tine niste vectori NextOX_i si NextOY_i in care sa retina indicii urmatoarelor puncte nemarcate pe OX, respectiv pe OY.

Jetoane2 (probelma medie)

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

• A_{i, j} = 1 daca intervalul de jetoane dintre pozitiile i si j poate fi eliminat, sau 0, altfel.
• B_{i, j, k} = 1 daca undeva intre pozitiile i si j se poate plasa al k-lea cuvant si sa poate elimina tot intervalul, sau 0, altfel.

Astel B_{i, j k} = 1 daca si numai daca exista un p ∈ [i, j], astfel incat:

1. Cuv_{k, l} = Sir_p+l, ∀ 1 ≤ l ≤ Lung_k
2. A_{i, p-1} = A _{(i+Lung{k}) , j} = 1

Sir_p+l reprezinta sirul initial, Cuv_{k, l} reprezinta a l-a litera din al k-lea cuvant si Lung_k, lungimea acestuia. Dinamica se va calcula, crescator, dupa lungimea intervalului [i, j]. Daca ∃ k astfel incat B_{i, j, k} = 1, atunci A_{i, j} = 1.

Dupa determinarea valorilor lui A si cum scorul depinde exclusiv de intervalele [i, j] ce pot fi eliminate, se va aduna la rezultat suma ponderilor de pe toate intervalele [i, j] cu A_{i, j} = 1.

Tero (problema grea)

Dupa cum multi si-au dat seama, problema este asemanatoare cu cea a lui Fechete, Trafic.

Fiind niste limite de timp foarte mari, cautare binara + fluxul 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 tabereie de pregatire a Lotului National, de catre Mugurel Ionut Andreica (Algoritmi de flux maxim in retele) 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 celui mai lenes soldat, parcurgand muchiile in ordinea sortarii, astfel: pentru o muchie e, vrem sa stabilim daca, pozitionand cel putin un soldat pe ea (crescand capacitatea la o valoare foarte mare), va creste sau nu fluxul. 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), va trebui sa facem doua optimizari:

1. se va reface reteaua reziduala L0 (vezi articolul lui Mugurel) +doar daca distanta exista un drum nesaturat, ce contine si muchia e
2. 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, a fost Bogdan Tataroiu.

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