Diferente pentru winter-challenge-2008/runda-1/solutii intre reviziile #15 si #33

Diferente intre titluri:

Solutii Winter Challenge 2008 runda 1
Solutii Winter Challenge 2008, Runda 1

Diferente intre continut:

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.
h1. Solutii Winter Challenge 2008, Runda 1
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:
==Rankings(rounds="winter2008-1" display_entries="3" pager_style="none")==
Felicitarii "tuturor participantilor":winter-challenge-2008/clasament si, in special, primilor 3 clasati:
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.
==Rankings(rounds="winter2008-1" display_entries="3" pager_style="none")==
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.
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":forum/index.php?topic=2637.0.
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.
{@  @}
{@  @}
Mult succes in continuare,
{@  @}
Echipa Winter Challenge.
Echipa Winter Challenge.
{@  @}
{@  @}
In continuare vom prezenta solutiile oficiale ale problemelor. Daca aveti nelamuriri puteti cere explicatii suplimentare pe "forum":http://infoarena.ro/forum/.
 
h2. 'Primar':problema/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, 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 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 ( $NextOX{~i~}$ si $NextOY{~i~}$ ) in care sa retina indicii urmatoarelor puncte nemarcate.
 
h2. 'Jetoane2':problema/jetoane2 (problema 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 intre pozitiile $i$ si $j$ se poate plasa al $k$-lea cuvant si se poate elimina +tot+ intervalul, sau $0$, altfel.
 
Astfel $B{~i~}~,~ {~j~} {~k~}$ = $1$ daca si numai daca exista un $p$ ∈ [$i$, $j$], astfel incat:
 
# $Cuv{~k~}~,~ {~l~} = Sir{~p+l~}$, ∀ $1$ ≤ $l$ ≤ $Lung{~k~}$
# $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$.
 
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.
 
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 tabereie 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.
In continuare vom prezenta solutiile oficiale ale problemelor. Daca aveti nelamuriri puteti cere explicatii suplimentare pe "forum":forum.
{@  @}
{@  @}
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 la orasul atacat, parcurgand muchiile in ordinea sortarii: 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.
(toc)*{text-align:center} *Lista de probleme*
* 'Primar':winter-challenge-2008/runda-1/solutii#primar
* 'Jetoane2':winter-challenge-2008/runda-1/solutii#jetoane2
* 'Tero':winter-challenge-2008/runda-1/solutii#tero
Pentru a avea o complexitate +teoretica+ de O(M*N^3), va trebui sa facem doua optimizari:
# se va reface reteaua reziduala L0 (vezi articolul lui Mugurel) +doar daca exista un drum nesaturat, ce contine si muchia $e$+
# pentru a verifica daca fluxul creste, nu se va relua tot algoritmul de flux maxim, ci se vor folosi informatiile anterior calcualte.
==include(page="winter-challenge-2008/runda-1/solutii/primar")==
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.
==include(page="winter-challenge-2008/runda-1/solutii/jetoane2")==
In arhiva se vor schimba testele astfel incat aceasta solutie sa nu obtina punctaj maxim.
==include(page="winter-challenge-2008/runda-1/solutii/tero")==
 

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.