Psihologia concursurilor de informatică/6 Probleme de concurs 2

From Algopedia
Revision as of 12:50, 9 March 2018 by Cata (talk | contribs)

Jump to: navigation, search

⇦ î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 OUTPUT.TXT 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:

INPUT.TXT OUTPUT.TXT
3 2 3 0

1 0 3
0 1 2

4 2 3 4

1 4 3
4 1 2
3 2 1

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 O(N^{2}).

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 O(N^{2}) ș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ă:

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:

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:

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:

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:

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:

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 (iN-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.
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 2\times N^{2}. Complexitatea pătratică este cea optimă, deoarece programul trebuie în orice caz să tipărească la ieșire circa N^{2} numere.

#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();
}


Problema 8

Problema codului lui Pruffer 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:

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:

  1. Există (N+2)^{N} arbori generali cu N+2 noduri.
  2. 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 INPUT.TXT 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 OUTPUT.TXT. 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:

INPUT.TXT OUTPUT.TXT
5
1 5 2 5 1
5 2

1 3
4 5
7 1
6 2
1 5

Timp de implementare: 45 minute.

Timp de rulare: 2-3 secunde.

Complexitate cerută: O(N).

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:

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.

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 O(N) este optim; nu poate exista unul mai bun deoarece există O(N) muchii care trebuie tipărite.

#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();
}