Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-01-27 19:02:39.
Revizia anterioară   Revizia următoare  

Solutii Winter Challenge 2008 runda 1

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 organizata mai din timp.

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

PozitieNumeScor
1
bogdan2412Bogdan-Cristian Tataroiu
bogdan2412
239
2
gcosminGheorghe Cosmin
gcosmin
160
3
victorsbVictor Rusu
victorsb
120

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.

As vrea sa le multumesc lui Adrian Airinei si lui Andrei Grigorean pentru sprijinul acordat, si, totodata, intregii echipei infoarena.


Mult succes in continuare,

Echipa Winter Challenge.


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

Primar

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

Problema are doua parti: aflarea discriminarii minime si gasirea componentei Consiliului Local.

Pentru prima parte era nevoie sa se observe faptul 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, respectiv, 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 stoca sub forma unor liste, ale caror campuri retin urmatorul punct nemarcat pe OX si, respectiv, urmatorul punct nemarcat pe OY. Daca unii utilizatori InfoArena, nu sunt obisnuiti cu implementarea listelor, pot tine niste vectori ( NextOXi si NextOYi ) in care sa retina indicii urmatoarelor puncte nemarcate.

Complexitatea primei parti este O(N * log2N) pentru sortare, iar complexitatea celei de-a doua parti este O(N). In total, complexitatea algoritmului este O(N * log2N).

Jetoane2

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

  • Ai, j = 1 daca intervalul de jetoane dintre pozitiile i si j poate fi eliminat, sau 0, altfel.
  • Bi, j, k = 1 daca intre pozitiile i si j se poate plasa al k-lea cuvant si se poate elimina tot intervalul, sau 0, altfel.

Astfel Bi, j k = 1 daca si numai daca exista un p ∈ [i, j], astfel incat:

  1. Cuvk, l = Sirp+l, ∀ 1lLungk
  2. Ai, p-1 = A (i+Lung{k}) , j = 1

Sirp+l reprezinta sirul initial, Cuvk, l reprezinta a l-a litera din al k-lea cuvant si Lungk, lungimea acestuia. Dinamica se va calcula, crescator, dupa lungimea intervalului [i, j]. Daca ∃ k astfel incat Bi, j, k = 1, atunci Ai, 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 Ai, j = 1.

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

Exista si o solutie de complexitate O(N * L3), care, in practica, merge mai repede. Aceasta solutie a fost data de catre Cosmin Gheorghe si o voi publica imediat dupa ce primesc acordul sau.

Tero

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

Fiind niste limite de timp foarte mari, cautare binara + flux 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) 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*N3) (in practica merge cu mult mai repede), va trebui sa facem doua optimizari:

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

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 foarte mare la aceasta problema), a fost Bogdan Tataroiu.

In arhiva vom incerca sa schimbam testele astfel incat aceasta solutie sa nu obtina punctaj maxim.

Primar (problema usoara)

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

Problema are doua parti: aflarea discriminarii minime si gasirea componentei Consiliului Local.

Pentru prima parte era nevoie sa se observe faptul 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, respectiv, 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 stoca sub forma unor liste, ale caror campuri retin urmatorul punct nemarcat pe OX si, respectiv, urmatorul punct nemarcat pe OY. Daca unii utilizatori InfoArena, nu sunt obisnuiti cu implementarea listelor, pot tine niste vectori ( NextOXi si NextOYi ) in care sa retina indicii urmatoarelor puncte nemarcate.

Complexitatea primei parti este O(N * log2N) pentru sortare, iar complexitatea celei de-a doua parti este O(N). In total, complexitatea algoritmului este O(N * log2N).

Jetoane2 (problema medie)

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

  • Ai, j = 1 daca intervalul de jetoane dintre pozitiile i si j poate fi eliminat, sau 0, altfel.
  • Bi, j, k = 1 daca intre pozitiile i si j se poate plasa al k-lea cuvant si se poate elimina tot intervalul, sau 0, altfel.

Astfel Bi, j k = 1 daca si numai daca exista un p ∈ [i, j], astfel incat:

  1. Cuvk, l = Sirp+l, ∀ 1lLungk
  2. Ai, p-1 = A (i+Lung{k}) , j = 1

Sirp+l reprezinta sirul initial, Cuvk, l reprezinta a l-a litera din al k-lea cuvant si Lungk, lungimea acestuia. Dinamica se va calcula, crescator, dupa lungimea intervalului [i, j]. Daca ∃ k astfel incat Bi, j, k = 1, atunci Ai, 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 Ai, j = 1.

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

Exista si o solutie de complexitate O(N * L3), care, in practica, merge mai repede. Aceasta solutie a fost data de catre Cosmin Gheorghe si o voi publica imediat dupa ce primesc acordul sau.

Tero (problema grea)

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

Fiind niste limite de timp foarte mari, cautare binara + flux 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) 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:

  1. se va reface reteaua reziduala L0 (vezi articolul lui Mugurel) doar daca exista un drum nesaturat, ce contine 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 (si singurul care a obtinut punctaj maxim la aceasta problema), a fost Bogdan Tataroiu.

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