View source for Psihologia concursurilor de informatică/6 Probleme de concurs 2

⇦ înapoi la [[Psihologia concursurilor de informatică]]

= Capitolul VI: Probleme de concurs (7-12) =

== Problema 7 ==

Problema programării unui turneu de fotbal a fost dată spre rezolvare la a III-a Balcaniadă de Informatică, Varna 1995. Vom prezenta mai întâi enunțul nemodificat al problemei, după care vom adăuga câteva detalii care o vor face mai „provocatoare”.

'''ENUNȚ''': Una din sarcinile Ministerului Sporturilor dintr-o țară balcanică este de a organiza un campionat de fotbal cu '''''N''''' echipe (numerotate de la 1 la '''''N'''''). Campionatul constă din '''''N''''' etape (dacă '''''N''''' este impar) sau '''''N'''''-1 etape (dacă '''''N''''' este par); orice două echipe dispută între ele un joc și numai unul. Scrieți un program care realizează o programare a campionatului.

'''Intrarea''': Numărul de echipe '''''N''''' (2 ≤ '''''N''''' ≤ 24) va fi dat la intrarea standard (tastatură).

'''Ieșirea''' se va face în fișierul text <tt>OUTPUT.TXT</tt> sub forma unui tabel cu numere întregi avînd '''''N''''' linii. Al '''''j'''''-lea element din linia '''''i''''' este numărul echipei care joacă cu echipa '''''i''''' în etapa '''''j''''' (evident, dacă '''''i''''' joacă cu '''''k''''' în etapa '''''j''''', atunci în tabel '''''k''''' joacă cu '''''i''''' în aceeași etapă). Dacă echipa '''''i''''' este liberă în etapa '''''j''''', atunci al '''''j'''''-lea element al liniei '''''i''''' este zero.

'''Exemple''':

{|class="wikitable"
! <tt>INPUT.TXT</tt> ||  <tt>OUTPUT.TXT</tt>
|-
| <tt>3</tt>
| <tt>2 3 0<br>
1 0 3<br>
0 1 2</tt>
|-
| <tt>4</tt>
| <tt>2 3 4<br>
1 4 3<br>
4 1 2<br>
3 2 1</tt>
|}

'''Timp de implementare''': circa 1h 45’

'''Timp de execuție''': 33 secunde

Iată și modificările pe care le propunem pentru a aduce cu adevărat problema la nivel de concurs:

* Limita pentru numărul de echipe este '''''N''''' ≤ 200;
* '''Timpul de implementare''' este de 45 minute;
* '''Timpul de execuție''' este de 2-3 secunde;
* '''Complexitatea cerută''' este <math>O(N^2)</math>.

'''REZOLVARE''': Vom lăsa pe seama cititorului conceperea, implementarea și testarea unei rezolvări backtracking (adoptată de majoritatea în timpul concursului). De altfel, la Balcaniadă concurenții au avut la dispoziție calculatoare 486 / 50 Mhz, iar un backtracking îngrijit funcționa cam până la '''''N''''' = 18 în timpul impus, ceea ce asigura cam 75% din punctajul maxim. În afară de aceasta, se mai puteau face și alte lucruri nu tocmai elegante, având în vedere că datele de ieșire nu erau foarte mari. Pentru '''''N'''''>18, mulți concurenți lăsau programul să meargă până când termina (câteva minute bune sau chiar mai mult), apoi scriau rezultatele într-un fișier temporar. Matricea rezultată era inclusă ca o constantă în codul sursă. Programul care era dat comisiei de corectare se prefăcea că „se gândește” timp de câteva secunde, apoi scria pur și simplu matricea în fișierul de ieșire. Cu aceasta s-au luat punctaje foarte apropiate de maxim. Totuși, pentru '''''N'''''=24 un backtracking ar fi stat foarte mult pentru a găsi soluția. Tot timpul acesta, calculatorul era blocat, neputând fi folosit. De aceea, mulți concurenți nu au luat punctajul maxim, preferând să renunțe la ultimele teste și să rezolve celelalte probleme. Oricum, backtracking-ul este în acest caz o soluție pentru care raportul punctaj obținut / timp consumat este foarte convenabil.

Există însă și o soluție care poate asigura un punctaj maxim fără bătăi de cap și fără să folosească „date preprocesate”. Ea are complexitatea <math>O(N^2)</math> și nu face decât o singură parcurgere a matricei de ieșire. Ce-i drept, autorul a pierdut cam trei ore pentru a o găsi și implementa în timp de concurs, compromițând aproape rezolvarea celorlalte două probleme din ziua respectivă, dar comisia de corectare a fost plăcut impresionată, programul fiind singurul care mergea instantaneu. Rămâne ca voi să alegeți între eleganță și eficiență...

Dacă ținem cont și de restricțiile suplimentare propuse, rezolvarea backtracking nu mai este valabilă. În această situație, iată care este metoda care stă la baza rezolvării în timp pătratic. În primul rând se reduce cazul când '''''N''''' este impar la un caz când '''''N''''' este par, prin mărirea cu 1 a lui '''''N''''' și introducerea unei echipe fictive. În fiecare etapă se consideră că echipa care trebuia să joace cu echipa fictivă stă de fapt „pe bară”. Iată de exemplu cum se rezolvă cazul '''''N'''''=3:

a) Se programează un campionat cu 4 echipe, echipa 4 fiind echipa fictivă:

{|class="wikitable"
! Echipa || Etapa 1 || Etapa 2 || Etapa 3
|-
| '''1''' || 2 || 3 || 4
|-
| '''2''' || 1 || 4 || 3
|-
| '''3''' || 4 || 1 || 2
|-
| '''4''' || 3 || 2 || 1
|}

b) Se neglijează ultima linie din tabel, meciurile echipei fictive nefiind importante:

{|class="wikitable"
! Echipa || Etapa 1 || Etapa 2 || Etapa 3
|-
| '''1''' || 2 || 3 || 4
|-
| '''2''' || 1 || 4 || 3
|-
| '''3''' || 4 || 1 || 2
|}

c) Peste tot unde apare cifra 4, ea este înlocuită cu 0:

{|class="wikitable"
! Echipa || Etapa 1 || Etapa 2 || Etapa 3
|-
| '''1''' || 2 || 3 || 0
|-
| '''2''' || 1 || 0 || 3
|-
| '''3''' || 0 || 1 || 2
|}

Mai rămâne să vedem cum se tratează cazul când '''''N''''' este par. E destul de greu de dat o demonstrație matematică metodei care urmează; de fapt, nici nu există una, problema fiind rezolvată în timp de concurs prin inducție incompletă (adică s-a constatat cu creionul pe hârtie că metoda merge pentru '''''N'''''=4, 6, 8 și 10, apoi s-a scris programul care să facă același lucru și s-a constatat că merge și pentru valori mai mari). Să tratăm și aici cazul '''''N'''''=8, apoi să generalizăm procedeul.

Vor fi șapte etape și, fără a reduce cu nimic generalitatea problemei, putem presupune că echipa 1 joacă pe rând cu echipele 2, 3, 4, 5, 6, 7 și 8. Deocamdată tabelul arată astfel:

{|class="wikitable"
! Echipa || Etapa 1 || Etapa 2 || Etapa 3 || Etapa 4 || Etapa 5 || Etapa 6 || Etapa 7
|-
| '''1''' || 2 || 3 || 4 || 5 || 6 || 7 || 8
|-
| '''2''' || 1 ||   ||   ||   ||   ||   ||
|-
| '''3''' ||   || 1 ||   ||   ||   ||   ||
|-
| '''4''' ||   ||   || 1 ||   ||   ||   ||
|-
| '''5''' ||   ||   ||   || 1 ||   ||   ||
|-
| '''6''' ||   ||   ||   ||   || 1 ||   ||
|-
| '''7''' ||   ||   ||   ||   ||   || 1 ||
|-
| '''8''' ||   ||   ||   ||   ||   ||   || 1
|}

Echipa 2 are deja programat un meci cu echipa 1 în prima etapă și mai are de programat meciurile cu echipele 3, 4, 5, 6, 7 și 8 în celelalte etape. Așezarea se poate face oricum, cu condiția ca echipele 1 și 2 să nu își aleagă același partener în aceeași etapă. De exemplu, putem programa meciul 2-3 în etapa a 3-a, meciul 2-4 în etapa a 4-a, ..., iar meciul 2-8 în etapa a 2-a. Astfel am completat linia a doua a tabloului:

{|class="wikitable"
! Echipa || Etapa 1 || Etapa 2 || Etapa 3 || Etapa 4 || Etapa 5 || Etapa 6 || Etapa 7
|-
| '''1''' || 2 || 3 || 4 || 5 || 6 || 7 || 8
|-
| '''2''' || 1 || 8 || 3 || 4 || 5 || 6 || 7
|-
| '''3''' ||   || 1 || 2 ||   ||   ||   ||
|-
| '''4''' ||   ||   || 1 || 2 ||   ||   ||
|-
| '''5''' ||   ||   ||   || 1 || 2 ||   ||
|-
| '''6''' ||   ||   ||   ||   || 1 || 2 ||
|-
| '''7''' ||   ||   ||   ||   ||   || 1 || 2
|-
| '''8''' ||   || 2 ||   ||   ||   ||   || 1
|}

Echipa 3 are programate meciurile cu 1 și 2 și mai are de programat meciurile cu echipele 4, 5, 6, 7 și 8. Pentru a nu crea conflicte (adică două echipe să nu-și aleagă același adversar), putem aplica același procedeu: pornim de la etapa a 5-a și completăm toate celulele goale ale liniei a 3-a cu numerele de la 4 la 8, mergând circular spre dreapta:

{|class="wikitable"
! Echipa || Etapa 1 || Etapa 2 || Etapa 3 || Etapa 4 || Etapa 5 || Etapa 6 || Etapa 7
|-
| '''1''' || 2 || 3 || 4 || 5 || 6 || 7 || 8
|-
| '''2''' || 1 || 8 || 3 || 4 || 5 || 6 || 7
|-
| '''3''' || 7 || 1 || 2 || 8 || 4 || 5 || 6
|-
| '''4''' ||   ||   || 1 || 2 || 3 ||   ||
|-
| '''5''' ||   ||   ||   || 1 || 2 || 3 ||
|-
| '''6''' ||   ||   ||   ||   || 1 || 2 || 3
|-
| '''7''' || 3 ||   ||   ||   ||   || 1 || 2
|-
| '''8''' ||   || 2 ||   || 3 ||   ||   || 1
|}

Se folosește aceeași metodă pentru a completa și celelalte linii ale matricei. Pentru fiecare linie '''''i''''' ('''''i''''' ≤ '''''N'''''-1):

* Se caută pe linia '''''i''''' apariția valorii '''''i'''''-1;
* Se caută primul spațiu liber (mergând circular spre dreapta). Primul spațiu liber înseamnă prima etapă în care se poate programa meciul dintre echipele '''''i''''' și '''''i'''''+1 (trebuie ca ambele să fie libere în acea etapă). Se constată experimental că trebuie început de la a doua poziție liberă de după apariția valorii '''''i'''''-1;
* Se merge circular spre dreapta și, în căsuțele libere întâlnite se trec valorile '''''i'''''+1,    '''''i'''''+2, ..., '''''N'''''. Concomitent, pe aceleași coloane ale liniilor '''''i'''''+1, '''''i'''''+2, ..., '''''N''''' se trece valoarea '''''i'''''.

{|class="wikitable"
! Echipa || Etapa 1 || Etapa 2 || Etapa 3 || Etapa 4 || Etapa 5 || Etapa 6 || Etapa 7
|-
| '''1''' || 2 || 3 || 4 || 5 || 6 || 7 || 8
|-
| '''2''' || 1 || 8 || 3 || 4 || 5 || 6 || 7
|-
| '''3''' || 7 || 1 || 2 || 8 || 4 || 5 || 6
|-
| '''4''' || 6 || 7 || 1 || 2 || 3 || 8 || 5
|-
| '''5''' || 8 || 6 || 7 || 1 || 2 || 3 || 4
|-
| '''6''' || 4 || 5 || 8 || 7 || 1 || 2 || 3
|-
| '''7''' || 3 || 4 || 5 || 6 || 8 || 1 || 2
|-
| '''8''' || 5 || 2 || 6 || 3 || 7 || 4 || 1
|}

Fiecare linie a matricei poate fi parcursă in acest fel de maxim 2 ori (o dată pentru găsirea coloanei de start și o dată pentru completarea liniei), deci numărul total de celule vizitate este cel mult <math>2 \times N^2</math>. Complexitatea pătratică este cea optimă, deoarece programul trebuie în orice caz să tipărească la ieșire circa <math>N^2</math> numere.

<syntaxhighlight lang="c">
#include <stdio.h>
#define NMax 200
unsigned char A[NMax+1][NMax+1];
int N,RealN;

void FindNextFree(int Line,int *K)
/* Cauta (circular) urmatorul spatiu liber pe linia Line */
{ do *K=*K%(N-1)+1;
  while (A[Line][*K]);
}

void MakeMatrix(void)
{ int i,j,k;

  for (i=1;i<=N;i++)
    for (j=1;j<=N;j++) A[i][j]=0;
  for (i=1;i<N;i++)  /* Pentru fiecare echipa */
    { if (i==1)      /* Alege coloana de start */
        j=1;
        else { j=0;
               do j++; while (A[i][j]!=i-1);
               FindNextFree(i,&j);
               FindNextFree(i,&j);
             }
      for (k=i+1;k<=N;k++) /* Completeaza circular linia */
        { A[i][j]=k;
          A[k][j]=i;
          if (k<N) FindNextFree(i,&j);
        }
    }
}

void WriteMatrix(void)
{ int i,j;
  FILE *F=fopen("output.txt","wt");

  for (i=1;i<=RealN;i++)
    { for (j=1;j<N;j++)
        fprintf(F,"%4d",A[i][j]>RealN ? 0 : A[i][j]);
      fprintf(F,"\n");
    }
  fclose(F);
}

void main(void)
{
  printf("N=");scanf("%d",&RealN);
  N=RealN+RealN%2; /* Se adauga 1 daca RealN e impar */
  MakeMatrix();
  WriteMatrix();
}
</syntaxhighlight>


== Problema 8 ==

Problema '''codului lui Pruffer'''<ref>Greșeală în original, corect: Prüfer</ref> pentru arborii generali, mai exact cea a decodificării acestui cod, este genul de problemă care nu este excesiv de grea, dar care necesită un artificiu fără de care nu se poate ajunge la complexitatea optimă.

'''ENUNȚ''': Un arbore general neorientat conex cu '''''N'''''+2 vârfuri se poate codifica eficient printr-un vector cu '''''N''''' numere, astfel:

* Numerotăm nodurile de la 1 la '''''N'''''+2 într-o ordine oarecare;
* Eliminăm cea mai mică frunză (nod de grad 1) și adăugăm în vector numărul nodului de care ea aparținea;
* Reluăm procedeul pentru arborele rămas: tăiem cea mai mică frunză și adăugăm în vector numărul nodului de care ea aparținea;
* Repetăm procedeul până mai rămân doar două noduri.

Vectorul rezultat se numește codificare Pruffer a arborelui dat. Iată un exemplu de construcție a codului Pruffer atașat arborelui din figura de mai jos: 

[[File:Psycho-fig64.png]]

Codul lui Pruffer se obține astfel:

* Îl tăiem pe 3 și scriem 1;
* Îl tăiem pe 4 și scriem 5;
* Îl tăiem pe 6 și scriem 2;
* Îl tăiem pe 2 și scriem 5;
* Îl tăiem pe 5 și scriem 1;

Deci codificarea este (1, 5, 2, 5, 1) (și mai rămâne muchia 1-7, lucru care este evident, deoarece 1 și 7 sunt singurele noduri care nu au fost tăiate).

Așadar fiecărui arbore oarecare cu '''''N'''''+2 noduri i se poate atașa un vector cu '''''N''''' componente numere naturale cuprinse între 1 și '''''N'''''+2. Se poate demonstra că funcția definită între cele două mulțimi (mulțimea arborilor și mulțimea vectorilor) este bijectivă. De aici rezultă două lucruri:

# Există <math>(N+2)^N</math> arbori generali cu '''''N'''''+2 noduri.
# Codificarea Pruffer admite și decodificare (deoarece funcția de codificare este bijectivă). Tocmai aceasta este problema de rezolvat. Se dă un vector de '''''N''''' numere întregi, fiecare cuprins între 1 și '''''N'''''+2. Se cere să se tipărească cele '''''N'''''+1 muchii ale arborelui  decodificat.

'''Intrarea''' se face din fișierul text <tt>INPUT.TXT</tt> care conține două linii. Pe prima linie se dă '''''N''''' (1 ≤ '''''N''''' ≤ 10000), pe a doua cele '''''N''''' numere separate prin spații.

'''Ieșirea''' se va face în fișierul text <tt>OUTPUT.TXT</tt>. Acesta va conține muchiile arborelui, câte una pe linie, o muchie fiind indicată prin vârfurile adiacente separate printr-un spațiu.

'''Exemplu''':

{|class="wikitable"
! <tt>INPUT.TXT</tt> ||  <tt>OUTPUT.TXT</tt>
|-
| <tt>5<br>1 5 2 5 1</tt>
| <tt>5 2<br>
1 3<br>
4 5<br>
7 1<br>
6 2<br>
1 5</tt>
|}

'''Timp de implementare''': 45 minute.

'''Timp de rulare''': 2-3 secunde.

'''Complexitate cerută''': <math>O(N)</math>.

'''REZOLVARE''': Să pornim de la exemplul particular prezentat mai sus, urmând ca apoi să generalizăm algoritmul.

Primim la intrare '''''N'''''=5 (deducem că arborele are 7 noduri) și codificarea   (1, 5, 2, 5, 1). Primul element din vector este 1. Știm deci că, la primul pas, a fost eliminată o frunză al cărei părinte este nodul 1. Întrebarea este: ce număr purta respectiva frunză? În nici un caz 1, deoarece numărul 1 îl avea tatăl ei. Nici 2, nici 5 nu ar putea fi, deoarece aceste numere apar mai târziu în codificare, deci „mai este nevoie” de ele și nu pot fi încă eliminate. Rămân 3, 4, 6 și 7. Dintre acestea noi știm că a fost tăiată cea mai mică frunză. Este însă ușor de văzut că toate nodurile enumerate sunt frunze în arborele inițial (deoarece nu mai apar în vector, adică nici un alt nod nu mai este legat de ele), deci îl vom alege pe cel mai mic cu putință, adică pe 3. Rezultă că prima muchie tăiată a fost (1,3).

Pe poziția a doua în codificare apare numărul 5. Ce număr ar putea avea frunza tăiată? 1 și 2 mai apar ulterior în codificare deci nu pot fi eliminate încă, 5 este chiar tatăl frunzei necunoscute, iar 3 a fost deja eliminat. Dintre 4, 6 și 7, frunza cu numărul cel mai mic este 4, deci următoarea muchie tăiată este (4,5).

În continuare apare un 2. Cel  mai mic nod care nu mai apare în vector și nici nu a fost deja eliminat este 6, deci muchia este (6,2). Se observă că mai departe nu mai apare nici un 2 în codificare, de unde deducem că după tăierea nodului 6, nodul 2 a devenit frunză și va putea fi la rândul său eliminat. Cu un raționament analog, următoarele muchii eliminate sunt (2,5) și (5,1), iar singurele noduri rămase sunt 1 și 7. Arborele a fost reconstituit corect.

Deci procedeul general este: pentru fiecare număr dintre cele '''''N''''' din vector, nodul care aparținea de el poartă cel mai mic număr care nu intervine ulterior în codificare și nu a fost tăiat deja. Astfel se generează '''''N''''' muchii. A '''''N'''''+1-a muchie are drept capete ultimele noduri rămase netăiate.

Acesta este algoritmul. Trebuie să ne ocupăm acum de partea de implementare.

Pentru a testa la orice moment dacă un nod mai apare sau nu în vector, este bine să se creeze la citirea datelor un vector care să rețină numărul de apariții în codificare al fiecărui nod. Pentru exemplul dat, vectorul de apariții va fi '''''Apar'''''=(2,1,0,0,2,0,0), semnificând că 1 și 5 apar de câte două ori, 2 apare o singură dată, iar 3, 4, 6 și 7 nu apar deloc. La fiecare pas, când se „restaurează” o muchie, se decrementează poziția corespunzătoare tatălui în vectorul de apariții. Un număr nu mai apare ulterior în codificare dacă pe poziția sa din vectorul de apariții se află un 0.

Astfel, o primă versiune de program ar putea fi:

<pre>
intrare: N, V[1..N].
construieste vectorul Apar[1..N+2]
pentru i de la 1 la N:
  cauta primul j pentru care Apar[j]=0 si j nu a fost taiat;
  scrie muchia (j,V[i]);
  Apar[j] = Apar[j]-1;
  marcheaza nodul j ca fiind taiat.
</pre>

După cum se observă, căutarea celui mai mic nod j se face în timp liniar, ceea ce înseamnă că algoritmul complet va necesita un timp pătratic. Pentru a-l reduce la o complexitate liniară, începem prin a observa că la fiecare pas alegem frunza cu numărul cel mai mic. Aceasta înseamnă că, în general, numărul frunzei alese spre a fi tăiată va crește la fiecare pas. Astfel, prima oară am tăiat nodul 4, apoi nodul 7. Singurul caz când va fi tăiată o frunză mai mică decât cea dinaintea ei este atunci când unui nod cu număr mic i se taie toate frunzele și devine el însuși o frunză, putănd fi tăiat. În exemplul nostru, nodul 2 nu putea fi eliminat de la început, deși avea un număr mic, deoarece mai avea atașată frunza 6. După eliminarea muchiei (6,2), nodul 2 a devenit frunză și a fost eliminat imediat.

Putem deci păstra într-o variabilă (care în program se numește '''''Next''''') următoarea frunză care care trebuie eliminată. Dacă prin decrementarea numărului de apariții la pasul curent nu s-a creat nici un zero în vectorul '''''Apar''''', sau s-a creat un zero, dar pe o poziție '''''K'''''>'''''Next''''', atunci totul este bine și la pasul următor se va elimina nodul '''''Next'''''. Dacă s-a creat un zero pe o poziție '''''K''''' mai mică decât '''''Next''''', rezultă că în arbore există acum două frunze, '''''K''''' și '''''Next''''', '''''K''''' fiind mai mică, deci prioritară. Atunci la pasul următor se va elimina frunza de pe poziția '''''K''''', urmând ca peste doi pași să se revină la frunza '''''Next'''''. Dacă prin eliminarea acestei frunze '''''K'''''  s-a creat un alt zero în vectorul de apariții, tot pe o poziție '''''K’''''' mai mică decât Next, se va trece mai întâi la acea poziție, urmând ca după aceea să se revină la poziția '''''Next''''' etc.

La prima vedere, pare necesară menținerea unei stive în care să depunem numerele '''''Next, K, K’'''''... și să le scoatem din stivă pe măsură ce nodurile respective sunt eliminate. Acest lucru ar presupune în continuare un algoritm pătratic. Totuși nu este așa deoarece, odată ce am tăiat un nod și l-am marcat ca atare, putem fi siguri că nu ne vom mai intâlni cu el până la sfârșitul decodificării, deci nu mai este necesară stocarea lui. Există o pseudo-stivă care are înălțimea 2: frunza asupra căreia se operează curent și nodul care urmează, '''''Next'''''.

În acest fel, numărul total de incrementări al variabilei '''''Next''''' nu depășește '''''N''''' (iar ea nu este niciodată decrementată), deci programul este rezolvat în timp liniar. Facem observația că algoritmul <math>O(N)</math> este optim; nu poate exista unul mai bun deoarece există <math>O(N)</math> muchii care trebuie tipărite.

<syntaxhighlight lang="c">
#include <stdio.h>
#define NMax 10002
typedef int Vector[NMax];

Vector V,Apar;
int N;

void ReadData(void)
{ int i;
  FILE *InF=fopen("input.txt","rt");

  fscanf(InF,"%d",&N);
  for (i=1;i<=N+2;Apar[i++]=0);
  for (i=1;i<=N;i++)
    { fscanf(InF,"%d",&V[i]);
      Apar[V[i]]++;
    }
  fclose(InF);
}

void Decode(void)
{ int Current=0,Next,i;
  FILE *OutF=fopen("output.txt","wt");

  do; while (Apar[++Current]);    /* Se cauta prima frunza */
  Next=Current;
  for (i=1;i<=N;i++)
    { fprintf(OutF,"%d %d\n",Current,V[i]);
      if (Current==Next) do; while (Apar[++Next]);
      /* Daca am ajuns la ultimul 0, mai caut unul */
      Apar[V[i]]--;
      Current=(V[i]<Next) && (Apar[V[i]]==0) ? V[i] : Next;
      /* Daca exista o frunza mai mica decat Next, */
      /* ea este prioritara, altfel revin la Next */
    }
  fprintf(OutF,"%d %d\n",Current,Next);
  fclose(OutF);
}

void main(void)
{
  ReadData();
  Decode();
}
</syntaxhighlight>


== Problema 9 ==

Iată o problemă care necesită pentru reducerea complexității un artificiu asemănător celui din problema codului Pruffer. Ea a fost propusă în 1995 la concursul de selecție a echipelor României pentru IOI și CEOI. Deși cerința este puțin modificată pentru a nu ne izbi de dificultăți secundare, ideea generală de abordare este aceeași.

'''ENUNȚ''': Președintele companiei X dorește să organizeze o petrecere cu angajații. Această companie are o structură ierarhică în formă de arbore. Fiecare angajat are asociat un număr întreg reprezentând măsura sociabilității sale. Pentru ca petrecerea să fie agreabilă pentru toți participanții, președintele dorește să facă invitațiile astfel încât:

* el însuși să participe la petrecere;
* pentru nici un participant la petrecere să nu fie invitat și șeful lui direct;
* suma măsurilor sociabilităților invitaților să fie maximă.

Se cere să se spună care este suma maximă a sociabilităților care se poate obține.

'''''Intrarea''''' se face din fișierul <tt>INPUT.TXT</tt> care conține trei linii de forma:

<pre>
N
T(1) T(2) ... T(N)
S(1) S(2) ... S(N)
</pre>

unde '''''N''''' este numărul de angajați ai companiei, inclusiv președintele ('''''N''''' ≤ 1000), '''''T'''''('''''k''''') este numărul de ordine al șefului direct al lui '''''k''''' (dacă '''''T'''''('''''k''''') = 0, atunci '''''k''''' este președintele), iar '''''S'''''('''''k''''') este măsura sociabilității lui '''''k'''''. Valorile vectorului '''''S''''' sunt de tipul întreg.

'''Ieșirea''': Pe ecran se va tipări suma maximă a sociabilităților ce se poate obține.

'''Exemplu''': Pentru intrarea:

<pre>
7
2 5 2 5 0 4 2
2 5 3 13 8 4 3
</pre>

pe ecran se va afișa numărul 20 (fiindcă la petrecere participă 1, 3, 5, 6 și 7).

'''Timp de implementare''': 1h - 1h 15’.

'''Timp de rulare''': 2-3 secunde.

'''Complexitate cerută''': <math>O(N)</math>. De asemenea, menționăm că s-a specificat '''''N''''' ≤ 1000 numai pentru ca programul sursă de mai jos să nu se complice și să distragă atenția asupra unor lucruri neimportante. În mod normal, limita trebuia să fie '''''N''''' ≤ 10000.

'''REZOLVARE''': Vom expune mai întâi principiul de rezolvare al problemei, apoi vom aborda detaliile de implementare.

Algoritmul are la bază programarea dinamică și necesită o parcurgere de jos în sus a arborelui, decizia pentru fiecare nod depinzând de valorile tuturor fiilor lui. Ne propunem să aflăm două caracteristici pentru fiecare nod '''''k''''':

* P(k) - suma maximă a sociabilităților care se poate obține în subarborele de rădăcină '''''k''''' în cazul în care '''''k''''' participă la petrecere;
* Q(k) - suma maximă a sociabilităților care se poate obține în subarborele de rădăcină '''''k''''' în cazul în care '''''k''''' nu participă la petrecere;

Dacă reușim să determinăm aceste caracteristici, nu ne rămâne decât să-l tipărim pe '''''P'''''('''''R''''') ('''''R''''' fiind rădăcina arborelui). Într-adevăr, problema cere să se determine suma maximă a sociabilităților din întregul arbore, adică din subarborele de rădăcină '''''R'''''. În plus, se mai cere ca '''''R''''' să participe la petrecere. Rămâne de aflat cum se stabilește relația între caracteristicile unui nod și cele ale fiilor săi.

* Dacă angajatul '''''k''''' participă la petrecere, atunci automat nici unul din subordonații săi direcți nu participă, și obținem relația:
: <math>P(k) = S(k) + \sum_j Q(j)</math>, '''''j''''' fiu al lui '''''k'''''
* Dacă angajatul '''''k''''' nu participă la petrecere, atunci subordonații săi direcți pot să participe sau nu la petrecere, după cum este mai avantajos, și obținem relația:
: <math>Q(k) = \sum_j \max\{P(j), Q(j)\}</math>, '''''j''''' fiu al lui '''''k'''''

Problema care se pune acum este cum să facem parcurgerea arborelui într-un mod cât mai avantajos. Pseudocodul (recursiv) sub forma sa cea mai generală este:

<pre>
procedura Calcul(k, P, Q)
  P ← S(k), Q ← 0
  pentru fiecare fiu j al lui k:
    Calcul(j, P1, Q1)
    P ← P + Q1
    Q ← Q + max (P1, Q1)
  intoarce P,Q
</pre>

Soluția „de bun simț” este de a construi arborele alocat dinamic. Ar apărea însă o sumedenie de dificultăți. În primul rând, arborele este general, deci nu se cunoaște numărul maxim de fii pe care îi poate avea un nod (pe cazul cel mai defavorabil, rădăcina poate avea '''''N'''''-1 fii). Aceasta înseamnă că legătura trebuie să fie de tip tata (fiecare nod pointează la tatăl său), ceea ce complică procedura de parcurgere: nu se poate apela procedura recursiv, dintr-un nod pentru toți fiii săi, deoarece nu se cunosc fiii, ci numai tatăl! O altă modalitate de alocare a arborelui ar fi cu doi pointeri pentru fiecare nod: unul către primul său fiu și unul către fratele său din dreapta (exemplul din enunț are reprezentate grafic mai jos cele două metode de construcție).

[[File:Psycho-fig65.png]]

Probabil că veți fi de acord cu mine că e riscant să te aventurezi la o asemenea implementare în timp de concurs, deoarece lucrul cu pointeri presupune o atenție deosebită. Greșelile sunt mai greu de observat și de multe ori duc la blocarea calculatorului, care trebuie resetat mereu, pierzându-se astfel o mulțime de timp. Trebuie deci căutată o metodă de parcurgere a arborelui care să nu necesite o alocare dinamică a memoriei. Putem încerca astfel: inițial '''''P'''''('''''i''''')='''''S'''''('''''i''''') și '''''Q'''''('''''i''''')=0 pentru orice nod. Urmează acum să tratăm pe rând fiecare nod. Cum ? Știm că pentru fiecare nod '''''k''''', numerele '''''P'''''('''''k''''') și '''''Q'''''('''''k''''') intervin în expresia lui '''''P'''''('''''T'''''('''''k''''')) și '''''Q'''''('''''T'''''('''''k''''')). Uitându-ne la formulele de mai sus, observăm că tot ce avem de făcut este să incrementăm '''''P'''''('''''T'''''('''''k''''')) cu '''''Q'''''('''''k''''') și '''''Q'''''('''''T'''''('''''k''''')) cu max{'''''P'''''('''''k'''''),'''''Q'''''('''''k''''')}.

Există o singură problemă: Pentru a putea folosi numerele '''''P'''''('''''k''''') și '''''Q'''''('''''k''''') trebuie să ne asigurăm că ele au fost deja calculate corect, în funcție de caracteristicile tuturor fiilor lui '''''k'''''. În cazul frunzelor, problema este rezolvată, deoarece ele nu au fii. Pentru nodurile interne, este necesar să știm câți fii au ele și câți din aceștia au fost tratați. În momentul în care toți fiii unui nod au fost tratați, poate fi tratat și nodul în sine. În program, vectorul '''''F''''' reține numărul de fiii netratați ai fiecărui nod. La tratarea unui nod '''''k''''' se face decrementarea lui '''''F'''''('''''T'''''('''''k''''')). Un nod '''''k''''' poate fi ales spre tratare dacă F('''''k''''')=0. Se observă că formatul datelor de intrare permite cu ușurință construcția vectorului '''''F''''' (numărul de fii al lui '''''k''''' este egal cu numărul de apariții al lui '''''k''''' în vectorul T).

Un algoritm mai ușor de implementat ar fi:

<pre>
numara fiii fiecarui nod
repeta de N-1 ori:
  cauta un nod k cu F(k)=0
  P(T(k)) ← P(T(k))+Q(k)
  Q(T(K)) ← Q(T(K))+max{P(k),Q(k)}
  F(T(K)) ← F(T(K))-1
scrie P(R)
</pre>

Partea delicată a acestui algoritm este căutarea unui nod '''''k''''' cu '''''F'''''('''''k''''')=0. Dacă ea se face secvențial, pornind de fiecare dată de la primul nod și cercetând fiecare element, programul care rezultă are complexitatea <math>O(N^2)</math>. Această căutare trebuie deci optimizată, și iată cum: În principiu, putem căuta nodurile cu '''''F'''''('''''k''''')=0 mergând numai în sensul crescător al indicilor în vector. Vom folosi, ca și la problema codului lui Pruffer, două variabile: '''''K''''' și '''''Next'''''. '''''K''''' este nodul tratat în prezent, iar '''''Next''''' este nodul care urmează a fi tratat la pasul următor, așadar '''''Next''''' > '''''K'''''. După tratarea nodului '''''K''''' și decrementarea lui '''''F'''''('''''T'''''('''''k''''')), pot surveni trei situații:

# '''''F'''''('''''T'''''('''''k'''''))>0 și în vectorul '''''F''''' nu a apărut nici un alt element zero, caz în care nimic nu se schimbă, algoritmul continuând cu tratarea nodului '''''Next''''';
# '''''F'''''('''''T'''''('''''k'''''))=0 și '''''T'''''('''''k''''')>'''''Next''''', caz în care de asemenea se poate trata nodul '''''Next''''' (deoarece selectarea nodurilor cu '''''F'''''('''''k''''')=0 se face în ordine crescătoare a indicilor);
# '''''F'''''('''''T'''''('''''k'''''))=0 și '''''T'''''('''''k''''')<'''''Next''''', caz în care se va trata mai întâi nodul '''''T'''''('''''k'''''), urmând a se reveni apoi la nodul '''''Next'''''.

Pentru motivele explicate la codul lui Pruffer, acest algoritm nu necesită menținerea unei stive, iar timpul total de căutare este <math>O(N)</math>. Facem observația că nu se poate găsi un algoritm mai bun, deoarece trebuie parcurse toate cele '''''N''''' noduri ale arborelui.

Iată în încheiere cum arată arborele cu valorile P și Q atașate fiecărui nod:

[[File:Psycho-fig66.png]]

<syntaxhighlight lang="c">
#include <stdio.h>
#define NMax 1000
typedef long Vector[NMax+1];

Vector T,S,P,Q,F; /* T = Vectorul de tati,
                     S = sociabilitatile,
                     P,Q = caracteristicile,
                     F = numarul de fii */
int N,Root;

void InitData(void)
{ int i;
  FILE *InF=fopen("input.txt","rt");

  fscanf(InF,"%d",&N);
  for (i=1;i<=N+1;F[i++]=0);
  for (i=1;i<=N;i++)
    { fscanf(InF,"%d",&T[i]);
      if (T[i]) F[T[i]]++; else Root=i;
    }
  for (i=1;i<=N;i++) fscanf(InF,"%d",&S[i]);
  fclose(InF);

  for (i=1;i<=N;P[i++]=S[i]);
  for (i=1;i<=N;Q[i++]=0);
}

void FindNext(int *K,int *Next)
{ F[T[*K]]--;
  F[*K]=-1;
  if ((F[T[*K]]>0) || (T[*K]>*Next))
    { *K=*Next;
      while (F[*Next]) (*Next)++;
    }
    else *K=T[*K];
}

void TraverseTree(void)
{ int K=0,Next,i;

  do; while (F[++K]);
  Next=K; do; while (F[++Next]);
  for (i=1;i<N;i++)
    { P[T[K]]+=Q[K];
      Q[T[K]]+=(P[K]>Q[K]) ? P[K] : Q[K];
      FindNext(&K,&Next);
    }
}

void main(void)
{
  InitData();
  TraverseTree();
  printf("%ld\n",P[Root]);
}
</syntaxhighlight>

<references/>