• Home
• Clasament
• Organizatori
• Sponsori si premii
• Regulament
• Aparitii in presa
• Runde
• Runda 1
• Runda 2
• Runda 3
• Runda 4
• Runda Finala

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

• 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.

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.

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] * P₁ + m[2] * P₂ + ... + m[N] * P_N

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 nivel_x 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 nivel_y 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 nivel_y era minim, si cum nivel_u < nivel_y 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.

Sponsori

Organizarea finalei preONI este posibila datorita generosilor nostri sponsori: