• 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

Sponsori

Organizarea finalei preONI este posibila datorita generosilor nostri sponsori: