Din GInfo 6/99 SOLUȚIILE problemelor propuseVă prezentăm în continuare câteva dintre soluțiile oficiale pentru problemele propuse în cadrul taberei de pregătire de la Mediaș. Soluțiile aparțin autorilor problemelor.
P069901: A. P. M.Adăugarea unei muchii într-un arbore generează un ciclu. Presupunem că introducem o muchie între nodul i și nodul j. Pentru ca APM-ul grafului astfel obținut să nu se schimbe, trebuie ca muchia de cost maxim de pe drumul de la i la j din arborele inițial să aibă costul mai mic sau egal cu muchia introdusă. Pe această observație se bazează întreaga strategie. Se determină muchiile de cost maxim de pe fiecare drum dintre oricare două puncte ale arborelui inițial; se ordonează crescător atât vectorul acestora cât și costurile muchiilor care ne sunt puse la dispoziție. Fișierul de ieșire va conține toate perechile de două noduri distincte pentru care avem la dispoziție o valoare mai mare sau egală cu muchia de cost maxim de pe drumul dintre cele două noduri.
P069903: Spre culmiIdeea de rezolvare este următoarea: se baleiază vectorul de la stânga la dreapta, pentru a se construi subșirurile cu o singură parcurgere. Fiecare element este adăugat la sfârșitul unuia dintre subșirurile deja formate sau, dacă acest lucru nu este posibil, el este pus separat pentru a începe un nou subșir. Fie exemplul dat: N=7, V=(9, 2, 4, 7, 10, 11, 8). Atunci primul element (9) va fi în mod evident începutul unui subșir. De asemenea și 2, deoarece el nu poate fi pus în același subșir cu 9. Elementul 4 se leagă de 2 (este așezat în același subșir cu el), pentru că nu se poate lega de 9, și ar fi o pierdere inutilă să îl așezăm într-un subșir separat. Elementul 7 se leagă de subșirul deja format (2, 4). Ce se întâmplă însă cu elementul 10? El poate fi atașat atât subșirului (9), cât și subșirului (2, 4, 7). În situațiile în care un element poate fi alipit la mai mul te subșiruri, se preferă alipirea la subșirul care se termină într-un număr cât mai mare. De ce? Dacă alipim 10 la subșirul (2, 4, 7), obținem subșirurile (2, 4, 7, 10) și (9). Dacă însă alipim 10 la subșirul (9), obținem subșirurile (2, 4, 7) și (9, 10). În primul caz, capetele subșirurilor aveau valorile 10 și 9; în acest caz, capetele subșirurilor au valorile 7 și 10; această variantă este mai folositoare deoarece capetele subșirurilor sunt mai mici, ceea ce este bine pentru alipirea în continuare a altor numere (cum este numărul 8, de exemplu). Dacă s-ar fi alipit 10 la subșirul (2, 4, 7), s-ar fi obținut în final 3 subșiruri: (9), (2, 4, 7, 10, 11) și (8), adică o soluție neoptimă. În concluzie, pentru fiecare element V[i] trebuie să aflăm, dintre toate subșirurile deja create, capătul cu valoarea cea mai mare, dar strict mai mică decât V[i]. Pentru aceasta se recomandă menținerea valorilor de la capetele subșirurilor într-un vector separat, sortat, asupra căruia se pot efectua căutări binare. De asemenea, vom reține pentru fiecare element din V succesorul său în subșirul crescător din care face parte. Pentru fiecare element din vector se efectuează deci o căutare binară, ca urmare complexitatea algoritmului are ordinul O(N log N).
P069904: Apărați cetateaNumărul minim de oșteni care trebuie plasați este egal cu valoarea fluxului maxim în multigraful orientat dat de problemă (în care sursa este orașul Brașov, iar destinația este orașul Mediaș). Demonstrația acestui fapt este foarte ușor de intuit dacă se cunoaște algoritmul Ford Fulkerson de aflare a fluxului maxim într-un graf. Demonstrația se realizează în două etape:
Etapa 1 Vom arăta că sunt suficienți FM (FM reprezintă valoarea fluxului maxim) oșteni pentru a bloca accesul de la sursă la destinație.
Etapa 2 Vom arăta că nu putem bloca accesul de la sursă la destinație cu mai puțin de FM oșteni.
Etapa 2 este foarte simplu de arătat. Să presupunem prin reducere la absurd că putem bloca accesul de la sursă la destinație cu un număr de doar S oșteni (S<FM). Vom elimina arcele selectate (cele pe care vom amplasa oșteni) din graful inițial. Cu toate acestea, datorită modului de operare a algoritmului Ford Fulkerson, vom reuși să mai găsim drumuri de la sursă la destinație, cu o valoare totală de cel puțin FM-S. Astfel am găsit o contradicție cu ipoteza că cei S oșteni pot bloca accesul de la sursă la destinație. Etapa 1 o vom demonstra prin selectarea efectivă a unui număr de arce având suma costurilor FM și care blochează accesul de la sursă la destinație. Pentru aceasta vom considera mulțimea A a nodurilor la care s-a ajuns la ultima iterație a algoritmului Ford Fulkerson. Fie X mulțimea vârfurilor grafului inițial și V mulțimea arcelor grafului inițial. Atunci mulțimea arcelor (i,j) cu proprietatea că (i,j) aparține lui V, i aparține lui S și j aparține lui X\S este o mulțime de arce cu proprietățile cerute. Demonstrația acestui fapt este de asemenea evidentă și se bazează pe modul de operare al algoritmului Ford Fulkerson. În afara celor spuse mai sus, mai existau probleme referitoare la memorarea grafului, în așa fel încât algoritmul Ford Fulkerson să fie cât mai rapid. Clasica matrice de adiacență devenea, în cazul dimensiunii mari a datelor de intrare, imposibil de utilizat. O posibilă soluție era implementarea folosind listele de vecini. Pentru fiecare nod, era necesară folosirea a două liste de vecini (una pentru muchiile reale și una pentru muchiile de întoarcere) cu legături între ele, pentru a putea actualiza rapid drumurile găsite la fiecare iterație a algoritmului Ford Fulkerson.
P069905: Axa OXSoluția problemei este realizată prin metoda backtracking. Așezarea punctelor pe axă determină un arbore binar în care se va face căutarea soluției. Punctul de coordonate 0 și cel aflat la distanța maximă citită din fișierul de intrare, reprezintă puncte figurate pe axă. Tehnica permite așezarea unui nou punct pe axă (simetric față de punctele extreme) dacă toate celelalte distanțe pe care le generează față de punctele deja figurate există. Vectorul a memorează distanțele (a[i] indică de câte ori apare distanța i). Odată cu așezarea unui punct pe axă se va face și decrementarea elementelor din a corespunzătoare. Evident, dacă această acțiune nu este posibilă se încearcă poziția simetrică, sau se revine pe un nivel anterior.
P069907: La grădinițăI. Dacă noțiunea de lanț corect are accepțiunea 1) Relația de recurență pe care se bazează determinarea numărului cerut: NR[i,j]:=NR[i-1,j]+NR[i,j-1]; Avansând cu ea în tabloul NR, rezultatul îl obținem în componenta NR[m,n] II. Dacă noțiunea de lanț corect are accepțiunea 2) relațiile de recurență căutate sunt mai dificil de obținut.
P069908: PătrateDacă n este număr par atunci partiția este următoarea:
n/2-1 pătrățele Dacă n este impar atunci se face descompunerea:
iar pătratul (*) se descompune în n-3 pătrățele la fel ca în cazul anterior.
P069910: La ora de germanăSoluția se bazează pe observația că dacă cuvintele au aceeași lungime atunci se poate aplica principiul optimalității. Problema se reduce la a determina într-un graf un drum prin K noduri, de cost maxim și care poate conține cicluri. Nodurile corespund cuvintelor, iar costul muchiei care leagă nodul I de nodul J este lungimea maximă a unui prefix din J care este sufix în I (cu alte cuvinte, cât poate "pătrunde" cuvântul I în cuvântul J).
Observație: Avem muchii și din I în I pentru orice I.
Aplicăm metoda programării dinamice, astfel: notăm cu A[I,J] costul maxim al unui drum care trece prin I noduri și ajunge în J. Avem condițiile inițiale A[0,J]=0 și relația de recurență: A[I,J]=max{A[I-1,L]+D[L,J]|L=1,N}, iar maximul se regăsește într-una din celulele A[K,J], J=1,N. Lungimea minimă este K*L-MAX, iar cuvântul poate fi găsit ușor parcurgând o matrice "predecesor" P[I,J] pe care o construim în același timp cu matricea A. Complexitatea algoritmului este O(N2*(K+Ti)), unde Ti este timpul necesar determinării unei "intersecții" între două cuvinte. Acest lucru poate fi realizat trivial în O(L2), dar se poate realiza și în O(L) folosind metoda de determinare a unui prefix-sufix maxim din algoritmul KMP pe cuvântul obținut prin alăturarea celor două cuvinte, respectiv pe un singur cuvânt în cazul unei bucle IźI.
P069912: NumereProblema generalizează modul de reprezentare a unui număr natural m într-o bază b. Dacă se ia x1=x2=...xn=b se obține: m=a0+a1b+a2b2+...+akbk, cu 0Łai<b, pentru 0ŁiŁk.
Determinarea numerelor a0, a1,..., ak se realizează folosind teorema împărțirii cu rest astfel: m=a0+q1x1; q1=a1+q2x2; ... qk-1=ak-1+qkxk; qk=ak+qk+1xk algoritmul se termină când qk+1=0, sau k=n. Dacă qk+1>0, atunci problema nu are soluție. Condițiile ai<xi+1, sunt verificate datorită teoremei împărțirii cu rest.
[cuprins] |