Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-06-25 21:49:34.
Revizia anterioară   Revizia următoare  

Comentarii aici...

Solutii Runda Finala

Orase

(problema usoara, clasa a 9-a)

Sarpe

(problema medie, clasa a 9-a)

Vom calcula intai numarul de posibilitati pentru cazul in care 1 se afla in unul din colturi. Sa presupunem ca l-am asezat in coltul stanga sus. Distingem doua cazuri:

  • 2 este asezat la dreapta lui 1 caz in care exista un singur mod de completare
123...
2N2N-12N-2...
  • 2 este asezat in coltul dreapta jos caz in care vom avea de completat tabla ramasa cu numerele 3, 4, ... 2N punand 3 la dreapta lui 2 lucru care este echivalent cu completarea unei table cu N-1 coloane cu 1 fixat in unul din colturi.
1 ...
23...

In concluzie numarul de moduri in care se poate completa tabla de dimensiune N cu 1 pus intr-un colt fixat este N. Analizam acum cazul in care 1 este pus pe una din coloanele 2, 3 , ... N-1. 2 nu poate fi pus sub 1 deoarece tabla s-ar imparti in doua bucati care nu sunt conexe si nu se poate completa comform cerintei. Daca 2 este pozitionat in stanga lui 1 toate coloanele 1, 2, ... i se vor completa in mod unic.

i...21...
i+1...2*i - 12*i...

Deci vor ramane de completat N-i coloane care trebuie completate cu 2*i+1 pus intr-un colt fixat. Deci vom avea in total N-i posibilitati. In mod analog daca 2 se afla in dreapta vom avea i-1 posibilitati. Numarul total de posibilitati cand 1 se afla pe una din coloanele 2, 3, ... N-1 va fi suma de la 2 la N-1 din 2(N-i+i-1) adica 2(N-2)(N-1) deoarece se poate incepe de sus sau de jos. Raspunsul cautat va fi 4N + 2(N-1)(N-2), N > 1. Operatiile trebuiau efectuate pe numere mari.

Sate

(problema grea, clasa a 9-a, problema usoara, clasa a 10-a)

Branza

(problema medie, clasa a 10-a)

Aceasta problema se rezolva folosind metoda programarii dinamice. O solutie triviala are complexitatea O(N*T) si se realizeaza calculand vectorul m[i] = costul minim pentru a obtine un kg de branza in saptamana i. Acesta se obtine folosind formula m[i] = min{C[j] + (i-j)*S | i-j ≤ T}.
Pentru a reduce complexitatea la O(N) se observa ca pentru calculul lui m[i] avem nevoie doar de valorile lui C cuprinse intre max(1, i-T) si i, interval a carei dimensiuni nu poate decat sa creasca sau sa ramana constanta. Se foloseste un deque in care se introduc pe rand valorile din C modificate corespunzator pentru a asigura gasirea minimului cerut la fiecare pas. Astfel la pasul i se va introduce in deque valoarea C[i] + (N-i)*S, pentru a mentine relatia de ordine corespunzatoare relatiei de recurenta intre elementele structurii. La pasul i se considera elementul din coada deque-ului (fie acela provenit de la C[j]) din care se scade (N-j)*S pentru a obtine pe m[i].
Solutia ceruta este m[1] * P1 + m[2] * P2 + ... + m[N] * PN

Gradina

(problema grea, clasa a 10-a)

P-Sir

(problema usoara, clasele 11-12)

Eval

(problema medie, clasele 11-12)

Obiective

(problema grea, clasele 11-12)

Putem asocia problemei un graf orientat care are proprietatea:

(*): Oricum am alege 3 noduri A, B, C din graf astfel incat sa existe drum de la A la C si de la B la C, atunci exista drum de la A la B sau de la B la A ( posibil ambele ).

Un query (x y) cere determinarea numarului minim de arce care trebuiesc reorientate astfel incat sa avem drum de la x la y. Problema se poate rezolva optim in complexitate O(N + M + T), dar in concurs o solutie O( (N + T) log N + M log M ) era suficienta pentru obtinerea punctajului maxim.

Graful initial se transforma intr-un graf aciclic, graful componentelor tare conexe, pe care il vom nota G*. In continuare, cand ne referim la nodul x in G* ne referim la nodul componentei tari conexe care il contine pe x. Numim radacina pentru G* acel nod care are gradul intern 0 ( nodul in care nu intra nici o muchie ). Exista un singur astfel de nod, deoarece, daca ar exista cel putin doua, conditia (*), impreuna cu proprietatea de conexitate a grafului suport, nu ar mai fi respectata.
Cum G* este aciclic, putem sorta nodurile lui astfel incat daca exista muchie de la x la y in G*, x va aparea inaintea lui y in sortare ( sortare topologica ). Pentru fiecare nod din G* sortam lista lui de adiacenta conform ordinii din sortarea topologica. Sortarea se poate face liniar, cu radixsort, sau cu algoritmul quicksort.

Dupa sortarea listelor de adiacenta, se efectueaza o parcurgere DF din radacina lui G*.

  • Propozitie 1: Arborele DF rezultat din parcurgerea de mai sus contine numai muchii de arbore sau muchii inainte.

Cum G* este aciclic, nu pot exista muchii de intoarcere ( inapoi ). Vom demonstra ca nu exista muchii transversale. Definim nivelx ca fiind numarul de noduri de la x la radacina parcurgand numai muchii de arbore.
Presupunem prin reducere la absurd ca exista o muchie transversala x->y. Selectam acea muchie transversala x->y pentru care nively este minim. Y nu poate fi radacina lui G*, pentru ca, in caz contrar, muchia x->y ar fi muchie de intoarcere si ar forma un ciclu, dar G* este aciclic. Deci exista un nod u care este tatal lui y. Demonstram ca pentru tripletul (x u y) conditia (*) nu este indeplinita.
Exista drum de la x la y si de la u la y. Drum de la x la u nu poate exista deoarece u se afla in alt subarbore si, pentru a trece dintr-un subarbore in altul, trebuie se parcurgem muchii transversale. Dar x->y era muchia transversala pentru care nively era minim, si cum nivelu < nively si nu exista muchii de intoarcere => nu putem ajunge din x in u. Nu putem ajunge nici din u in x datorita modului in care au fost sortate listele de adiacenta. Sa presupunem ca putem ajunge din u in x. Cum avem muchia x->y, x apare inaintea lui y in sortarea topologica, deci va aparea in listele de adiacenta mai devreme. Cand facem parcurgerea DF din nodul u, vom trece mai intai prin nodul x si de abia dupa aceea prin nodul y, iar muchia x->y nu mai este muchie transversala.
Propozitia a fost demonstrata.

  • Propozitie 2: Orice arbore DF care are doar muchii de arbore si muchii inainte indeplineste proprietatea (*).

Daca exista numai muchii de arbore si avem un triplet (A B C) care respecta ca exista drum de la A la C si de la B la C, atunci si A si B se afla in lista predecesorilor lui C. Unul din nodurile A sau B trebuie sa apara primul in aceasta lista, deci vom avea drum fie de la A la B, fie de la B la A.
Cand inseram muchiile inainte nu apar triplete noi pentru care sa existe drum de la A la C si de la B la C, deci propozitia a fost demonstrata.

Arborele DF contine deci numai muchii de arbore si muchii inainte. Pentru un query (x y) vom aplica o strategie de tip greedy. Fie L = Lowest_Common_Ancestor(x, y). Pentru a reorienta un numar minim de muchii, trebuie sa reorientam acele muchii care ne duc cat mai aproape de radacina. Astfel, trebuie sa ajungem intr-un nod u, stramos al lui x, pentru care nivelunivelL. Daca putem ajunge din x in u, putem cobori in arbore pana in y. Pentru acest pas vom folosi un algoritm liniar, de genul celui folosit in determinarea muchiilor critice in grafuri neorientate.
Fie lowx nodul cel mai apropiat de radacina in care se poate ajunge din x prin reorientarea a exact unei singure muchii si levelx nivelul lui lowx. Relatia de recurenta este:

levelx = minim(levelparinte[x]; levely | y fiu al lui x; levelu | u->x muchie inainte )

Simultan cu vectorul level construim si vectorul low.

Pe baza informatiilor astfel calculate, construim un arbore cu N noduri in care tatal nodului i, i de la 1 la N, va fi lowi. Acum trebuie sa aflam nodul u din acest arbore care indeplineste nivelunivelL si u se afla cat mai aproape de x. Raspunsul pe query va fi dat de diferenta de nivel dintre u si x.
Pentru a afla nodul u in timp logaritmic ne putem intoarce pe stramosi ai lui x pe baza de puteri ale lui 2 sau putem afla nodul u in O(1), demonstrand ca nodul cautat u este fie L, fie parinteL in acest arbore.

Sponsori

Organizarea finalei preONI este posibila datorita generosilor nostri sponsori: