• Informatii generale
• Clasament
•  
• Grupe de varsta
• Clasele 5-6
• Clasele 7-8
• Clasa a 9-a
• Clasa a 10-a
• Clasele 11-12

Solutii preONI 2008, Runda finala

• Lista de probleme
• Joc8
• Patrat
• Fibo
• Pusculita
• Suma3
• Pitici2
• Carti
• Euro2
• Zip
• Lacat
• Online

Joc8

Din descrierea jocului se desprinde algoritmul cautarii binare, algoritm care nu trebuia sa fie cunoscut de concurenti, deoarece este descris in enunt. Singurele dificultati constau in intelegerea si implementarea modelului descris.

Citeste x,y
  gasit = fals
  cat timp nu gasit si (x <= y) executa:
    z = (x + y) div 2
    Citeste: raspuns
    Daca raspuns = 1 atunci
      gasit = adevarat
    altfel
      Citeste: raspuns
      Daca raspuns = 1 atunci
        y = z - 1
      altfel
        x = z + 1
      Sfarsit(Daca)
    Sfarsit(Daca)
  Sfarsit(Cat timp)
  Daca gasit atunci
    Scrie: z
  altfel
    Scrie: 0
  Sfarsit(Daca)
Sfarsit(Algoritm)

Patrat

Problema se rezolva simplu daca construim vectorul ok, unde ok_i va fi true daca si numai daca i respecta proprietatile din enunt. Pentru a construi acest vector putem proceda astfel:

pentru i = 1, 20000
     ok[i] = false
pentru i = 1, [radical(20000)]
    pentru j = i+1, [radical(20000)]
        daca i * i + j * j <= 20000
            ok[i * i + j * j] = true

Pentru a afisa toate numerele intre x si y ce se pot scrie ca suma de patrate este suficient sa iteram un i intre cele doua margini si sa afisam acele valori care indeplinesc ok_i = true.

Fibo

Problema poate fi abordata in mai multe feluri:

• Luam in considerare pe rand toate numerele mai mici sau egale cu numarul dat N si generam reprezentarea lor in sistemul Fibonacci. Apoi verificam sirul de caractere pentru a stabili daca este sau nu palindrom.
• Este posibil sa abordam problema si invers, adica sa generam sirul de caractere palindrom formate din cifre 1 si 0. Lungimea sirului de caractere va fi egala cu lungimea sirului Fibonacci continand numere mai mici sau egale cu n. Cum al 30-lea termen fibonacci depaseste 10⁶ avem cel mult 2¹⁶ posibilitati de a genera palindroame.

Pusculita

for q:=0 to s do
   for w:=1 to n do
      if (q>=greutate[w]) and (sir[q]-sir[q-greutate[w]]>valoare[w])
      then 
          sir[q]:=sir[q-v[w]]+valoare[w];

Suma3

Problema se rezolva prin metoda backtracking, dar pentru a obtine un program cat de cat performant este nevoie de diverse optimizari. Prima data se observa ca nu trebuie generate sume mai mari decat valoarea minima actuala. Aceasta valoare se actualizeaza dupa caz pe parcursul generarii solutiilor impreuna cu sirul care contine traseul. A doua optimizare este mai interesanta: vom pastra fiecare element al tabloului dat si sub forma unui sir ordonat dupa valoarea elementelor, impreuna cu pozitia din tablou.

Pitici2

Rezolvarea optima ruleaza in timp liniar: Daca toate punctele se afla pe o singura dreapta, problema devine triviala. In caz contrar putem gasi trei puncte necolineare, sa le notam cu A, B si C.
Avem doua cazuri:

• Dreptele AB, BC si AC acopera toate punctele: am obtinut solutia.
• Exista un punct D, care nu este acoperit de niciuna dintre dreptele de mai sus. Daca exista trei drepte, care acopera toata multimea de puncte, putem avea doua cazuri:
  • Doua drepte acopera cate doua puncte din A, B, C si D, iar a treia acopera alte puncte. Pentru verificarea acestui caz incercam toate cele trei imperecheri posibile (AB+CD,AC+BD,AD+BC).
  • O dreapta acopera doua puncte din A, B, C si D, iar doua trec prin cate un punct din cele ramase. Acest caz se trateaza in felul urmator: sa consideram o anumita imperechere, care defineste doua drepte, de exemplu AB+CD. Daca punctele neacoperite de aceste doua drepte nu sunt colineare, sa consideram un punct E, care nu se afla pe cele doua drepte. Daca multimea de puncte se poate acoperi cu trei drepte, punctul E trebuie sa se afle pe una din ele. Stiind ca E nu se afla pe AB, incercam variantele AB+CE si AB+DE. Pentru celelalte imperecheri procedam in mod simetric.

Carti

O stare a cartilor de pe masa se poate reprezenta printr-un numar din intervalul [0, 8191] in felul
urmator: scriind numarul in sistem binar obtinem forma b₁₂b₁₁...b₁b₀, unde b_i = 1, daca si numai daca cartea cu valoarea i+1 se afla pe masa.
Sa consideram vectorul win_i cu semnificatia:

• win_i = true, daca jucatorul care este la mutare in starea i are strategie sigura de castig
• win_i = false, in caz contrar

Determinarea valorilor win_i este destul de simpla. Daca dintr-o stare se poate ajunge intr-o stare in care jucatorul pierde, inseamna ca starea curenta este o stare cu strategie sigura de castig:

• win_i = true, daca din starea i se poate ajunge intr-o stare j astfel incat win_j = false
• win_i = false, in caz contrar

Dintr-o stare i se poate ajunge intr-o stare j daca j se poate obtine din i prin scaderea a cel mult k biti consecutivi. Asadar pentru a vedea in ce stari putem ajunge dintr-o stare i, trebuie sa incercam toate valorile lui k posibile si toate pozitiile pe care poate aparea sirul de biti consecutivi.

win[state]:=0;
for i:=1 to k do
begin
mask:=0;
for j:=0 to i-1 do mask:=mask or (1 shl j);
for j:=0 to 13-i do
if (state and (mask shl j))=(mask shl j)
then
if not DoesWin(state-(mask shl j))
then
begin
win[state]:=1;
break;
end;
if win[state]=1
then break;
end;

Ramane sa calculam numarul nr asociat starii initiale de pe masa, si daca win_nr = true sa afisam Alice, iar in caz contrar sa afisam Bob. Pentru a calcula win_nr vom avea nevoie de examinarea a 2^N stari, asadar algoritmul final are complexitatea O(2^N * K) pentru fiecare configuratie din fisierul de intrare.

Euro2

Povestea din enunt "ascunde" urmatoarea problema: sa se determine cel mai lung subsir care este crescator pana la o anumita pozitie, apoi este descrescator.

Problema se poate rezolva corect utilizand in mai multe feluri metoda programarii dinamice, dar rezolvarile vor avea performante diferite.

1. Cel mai simplu algoritm de tip brute force genereaza toate cele 2^N submultimi ale multimii numerelor date, si le verifica pentru a decide daca au proprietatea ceruta. Aceasta solutie are o complexitate O(N * 2^N).

2. Solutii mai performante obtinem utilizand algoritmi de determinare a celui mai lung subsir crescator (descrescator), apeland la metoda programarii dinamice. Rezolvarea corecta consta in determinarea lungimii celui mai lung subsir crescator considerand ca si capat al acestuia pe rand, fiecare element al sirului dat, si lungimea celui mai lung subsir descrescator considerand ca prim element al acestuia, pe rand, fiecare element al sirului dat. Avand aceste lungimi, prin combinarea lor si determinarea maximului sumelor perechilor de lungimi corespunzatoare, obtinem rezultatul in complexitate O(N). Lungimile mentionate se pot calcula cu unul din algoritmii cunoscuti avand complexitatile O(N²) sau, optim, O(Nlog₂N).

Zip

Problema se poate imparti in doua parti. Prima data se construieste un graf complet cu n noduri, in care ponderea unei muchii semnifica numarul maxim de caractere care pot fi comune daca cuvintele corespunzatoare nodurilor respective se scriu unul dupa celalalt. Dupa construirea grafului ramane sa determinam drumul cel mai lung, care contine exact m noduri. Numarul cautat va fi (m * k - lungimea acestui drum). Prima parte se poate rezolva cu algoritmul trivial in O(n²*k²), sau folosind functia prefix din algoritmul Knuth-Morris-Pratt in O(n²*k). A doua parte se poate rezolva cu metoda backtracking in O(n^m). Evident, aceasta metoda este mult prea lenta, chiar si cu optimizarile posibile. O metoda mai rapida este folosirea metodei programarii dinamice si are o complexitate de O(n²*m). Se calculeaza matricea d, cu semnificatia: d[i,j] este drumul de lungime maxima, care trece prin i noduri si se termina in nodul j. Evident, valoarea cautata va fi max(d[m,i], i = 1, 2 ... n).

Lacat

Problema se poate rezolva in mai multe feluri, algoritmii respectivi avand complexitati diferite.

1. Prezentam rezolvarea consacrata, care modeleaza efectiv pasii care trebuie efectuati conform regulii jocului. Se aplica metoda Divide et Impera, unde avem urmatoarele subprobleme:

• TotiJos(m): Elibereaza primele m inele (in ordine oarecare), restul inelelor raman neschimbate

Algoritm TotiJos(m):
    Pentru i = m, 1 executa:
        Daca lacat[i] atunci
            Jos(i)
        Sfarsit(Daca)
    Sfarsit(Pentru)
Sfarsit(Algoritm)

• Jos(i): Elibereaza al i-lea inel, inelele avand numere de ordine j > i raman neschimbate (inelele avand numere de ordine j < i pot fi in orice pozitie dupa efectuarea operatiei)

Algoritm Jos(i):
    Daca (i > 1) si (!lacat[i-1]) atunci
        Sus(i-1)
    Sfarsit(Daca)
    Daca (i > 2) atunci
        TotiJos(i-2)
    Sfarsit(Daca)
    lacat[i] = fals           {al i-lea inel jos}
    Scrie: 'J', i
Sfarsit(Algoritm)

• Sus(i): Pune la loc al i-lea inel, inelele avand numere de ordine j > i raman neschimbate (inelele avand numere de ordine j < i pot fi in orice pozitie dupa efectuarea operatiei).

Algoritm Sus(i):
    Daca (i > 1) si (!lacat[i-1]) atunci
        Sus(i-1)
    Sfarsit(Daca)
    Daca i > 2 atunci
        TotiJos(i-2)
    Sfarsit(Daca)
    lacat[i] = adevarat  	      {al i-lea inel sus}
    Scrie: 'S', i
Sfarsit(Algoritm)

In programul principal se initializeaza sirul lacat cu valoarea adevarat (reprezentand faptul ca acestia sunt sus, adica lacatul este inchis). Apoi se apeleaza subprogramul TotiJos(n).

Deoarece numarul pasilor trebuie afisat la inceput, acesta poate fi calculat cu un algoritm liniar:

Algoritm Calculeaza():
    nrpasi = 1
    Pentru q = 2, n executa:
        nrpasi = nrpasi * 2
        Daca q este numar impar atunci
            nrpasi = nrpasi + 1
        Sfarsit(Daca)
    Sfarsit(Pentru)
Sfarsit(Algoritm)

2. O abordare bazata pe parcurgerea in adancime a spatiului solutiilor are complexitatea O(2ⁿ) si astfel in timpul acordat functioneaza doar daca n ≤ 11 datorita limitelor de memorie.

3. Cea de a treia posibilitate ar fi fost implementarea unei parcurgeri in latime obtinand solutii in timpul acordat daca n ≤ 16.

4. Cel de a patrulea algoritm (cunoscut sub denumirea DFSID) functioneaza in timpul acordat doar pentru n ≤ 5.

Online

Problema cere costul arborelui partial de cost minim, graful initial schimbandu-se la fiecare pas. Prima idee ar fi rularea unui algoritm clasic pentru gasirea arborelui partial de cost minim de K + 1 ori. In functie de algoritmul folosit si de metoda de implementare, obtinem complexitati diferite. Folosind algoritmul Kruskal putem obtine complexitati de O(K * N * M), O(K * (M * log M + N²)) sau O(K * M * log M). Folosind algoritmul Prim putem obtine complexitatea O(K * N²), sau O(K * M * log N) in cazul folosirii heap-urilor la implementare.
Totusi niciuna dintre aceste variante nu se incadreaza in timp pentru limitele date, asa ca propunem urmatorul algoritm, avand complexitatea O(N² + K * N). Prima data se gaseste arborele partial de cost minim pentru graful initial, folosind algoritmul Prim. Pentru urmatorii K pasi avem doua posibilitati:

1. Muchia curenta este intre doua noduri din arborele partial minim actual. Daca muchia are lungime mai mica, suprascriem muchia din arbore si costul arborelui se imbunatateste cu diferenta costurilor. Daca muchia are lungime mai mare sau egala, arborele ramane neschimbat.
2. Muchia nu face parte din arbore. Fiindca arborele are numar maxim de muchii din punctul de vedere al aciclitatii, o noua muchie va forma cu siguranta un ciclu. Pentru a ajunge iarasi la un arbore, din acest ciclu trebuie stearsa o muchie. Pentru ca arborele care rezulta sa aiba cost minim, vom sterge muchia cu cost maxim din ciclu.