Psihologia concursurilor de informatică/6 Probleme de concurs 3

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

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

⇦ înapoi la Psihologia concursurilor de informatică

Capitolul VI: Probleme de concurs (13-18)

Problema 13

Probabil că orice elev care are cât de cât experiență în programare a auzit despre problema celui mai lung subșir crescător. Când este prezentată la concurs, problema e „învelită” sub diverse forme. Aici o vom formaliza din punct de vedere matematic.

ENUNȚ: Se dă un vector cu N elemente numere întregi. Se cere să se determine cel mai lung subșir crescător.

Intrarea: Fișierul de tip text INPUT.TXT conține pe prima linie numărul N de elemente din vector (N≤10.000), iar pe fiecare din următoarele N linii se află câte un element al vectorului.

Ieșirea: În fișierul de tip text OUTPUT.TXT se vor lista pe prima linie lungimea L a celui mai lung subșir crescător, iar pe următoarele L linii subșirul în sine. Dacă există mai multe soluții, se va tipări una singură.

Exemplu:

INPUT.TXT OUTPUT.TXT
6
2
5
7
3
4
1
3
2
3
4

Timp de implementare: 45 minute.

Timp de rulare: 5 secunde.

Complexitate cerută: O(N\log N).


REZOLVARE: Începem prin a lămuri diferența dintre noțiunile de „subșir” și „subsecvență”. Fie V[1], V[2], ..., V[N], vectorul citit. Prin subșir de lungime L al vectorului V se înțelege o succesiune nu neapărat continuă de elemente V[K_{1}],V[K_{2}],\dots ,V[K_{L}], unde K_{1}<K_{2}<...<K_{L}. Prin subsecvență de lungime L a vectorului, începând de la poziția K, se înțelege succesiunea continuă de elemente V[K], V[K+1], ..., V[K+L-1].

Rezolvarea prin metoda programării dinamice este în general cunoscută și nu vom insista asupra ei. Probabil că aflarea celui mai lung subșir crescător este punctul de plecare al oricărui elev în învățarea programării dinamice. Totuși, această metodă de rezolvare are complexitatea O(N^{2}). În continuare prezentăm o metodă mai puțin cunoscută și ceva mai dificil de implementat, dar mult mai eficientă. Ea are complexitatea O(N\log N). Vom enunța principiul de rezolvare, urmat de o schiță a demonstrației de corectitudine.

Fie V vectorul citit. Se parcurge vectorul de la stânga la dreapta și se construiesc în paralel doi vectori P și Q, astfel: inițial vectorul Q este vid. Se ia fiecare element din V și se suprascrie peste cel mai mic element din Q care este strict mai mare ca el. Dacă nu există un asemenea element în Q, cu alte cuvinte dacă elementul analizat din V este mai mare ca toate elementele din Q, atunci el este adăugat la sfârșitul vectorului Q. Concomitent, se notează în vectorul P poziția pe care a fost adăugat în vectorul Q elementul din V. Iată cum se construiesc vectorii P și Q pentru exemplul din enunț:

Psycho-fig68.png

Lungimea L la care ajunge vectorul Q la sfârșitul acestei prelucrări este tocmai lungimea celui mai lung subșir crescător al vectorului V. Pentru a afla exact și care sunt elementele subșirului crescător se procedează astfel: se caută ultima apariție în vectorul P a valorii L. Să spunem că ea este găsită pe poziția K_{L}. Se caută apoi ultima apariție în vectorul P a valorii L-1, anterior poziției K_{L}. Ea va fi pe poziția K_{{L-1}}<K_{{L}}. Analog se caută în vectorul P valorile L-2, L-3, ..., 2, 1. Subșirul crescător este S=(V[K_{1}],V[K2],\dots ,V[K_{L}]).

În figura de mai sus au fost hașurate elementele respective găsite în vectorul P. Vectorul Q are la sfârșit lungimea L=3, deci cel mai lung subșir crescător are trei elemente. Se caută în vectorul P cifrele 3, 2 și 1 și se găsesc pe pozițiile K_{1}=1, K_{2}=4 și K_{3}=5, ceea ce înseamnă că cel mai lung subșir crescător este (2, 3, 4).

Demonstrația (care, fără a pierde din corectitudine, face apel la intuiție...) folosește aceleași notații de mai sus și are următoarele etape:

1. Vectorul Q este în permanență sortat crescător.

Demonstrația acestei afirmații se face prin inducție. După primul pas (inserarea elementului V[1]), vectorul Q are un singur element și este bineînțeles ordonat. Trebuie acum arătat că dacă vectorul Q este sortat după inserarea elementului V[i-1], el rămâne sortat și după inserarea lui V[i]. Într-adevăr, pentru elementul V[i] există două variante:

  • V[i] este mai mare decât toate elementele lui Q, caz în care este adăugat la sfârșitul lui Q, care rămâne sortat;
  • Există t>1 astfel încât Q[t-1]≤V[i]<Q[t], caz în care V[i] se suprascrie peste Q[t]. Dar Q[t]≤ Q[t+1] ⇒ Q[t-1]≤V[i]<Q[t+1] și vectorul Q rămâne sortat.

Această deducție ne va fi utilă în calculul complexității algoritmului.

2. Odată ce au fost scrise pentru prima oară, elementele vectorului Q nu mai pot decât să scadă sau să rămână constante. Ele nu pot crește niciodată.

Afirmația este evidentă, decurgând din modul de construcție a lui Q.

3. Elementele din vectorul V de la poziția K_{{i-1}}+1 la poziția K_{{i}}-1 sunt fie mai mici decât V[K_{{i-1}}], fie mai mari decât V[K_{i}].

Acest lucru este natural, deoarece dacă ar exista K_{{i-1}}<X<K_{i} astfel încât V[K_{{i-1}}]\leq V[X]\leq V[K_{i}], atunci șirul S ar putea fi extins cu elementul V[X], deci nu ar fi subșir maximal, contradicție.

4. Toate elementele care urmează în V după V[K_{L}] sunt mai mici decât V[K_{L}].

Dacă ar exista X>K_{L} astfel încât V[X]\geq V[K_{L}], atunci S ar putea fi extins la dreapta cu V[X], contradicție.

5. Elementul V[K_{1}] este suprascris peste poziția Q[1].

Demonstrația este imediată: Dacă elementul V[K_{1}] este inserat în Q pe o poziție t>1, rezultă că, în momentul tratării lui V[K_{1}], pe poziția t-1 în vectorul Q exista deja un număr X<V[K_{1}]. Aceasta înseamnă că S poate fi prelungit la stânga cu X, deci S nu este un subșir crescător maxim, contradicție.

6. Orice element V[K_{i}] va fi suprascris în Q pe poziția următoare celei pe care a fost scris V[K_{{i-1}}]

Demonstrație: Să presupunem că V[K_{{i-1}}] a fost scris peste Q[t]. Înainte de a ajunge să tratăm elementul V[K_{i}], a trebuit să tratăm elementele V[K_{{i-1}}+1],V[K_{{i-1}}+2],\dots ,V[K_{{i}}-1], care, după cum s-a stabilit la punctul (3), pot fi:

  • mai mici decât V[K_{{i-1}}], caz în care ele vor fi scrise în vector pe poziții mai mici sau egale cu t, iar Q[t] va scădea, deci Q[t]\leq V[K_{{i-1}}] (conform punctului 2);
  • mai mari decât V[K_{i}], caz în care vor fi scrise în Q pe poziții mai mari decât t, așadar Q[t+1]>V[K_{i}].

Se obține lanțul de inegalități Q[t]\leq V[K_{{i-1}}]\leq V[K_{i}]\leq Q[t+1], de unde rezultă conform modului de construcție că V[K_{i}] va fi scris peste Q[t+1]. Cu aceasta, folosind și punctul (5), am demonstrat că V[K_{i}] este scris pe poziția Q[i], ∀i=1, 2, ..., L. După tratarea primelor K_{L} elemente din V, vectorul Q are lungimea L. Mai rămâne de văzut ce se întâmplă cu elementele V[K_{L}+1],\dots ,V[N].

7. Elementele care îi urmează lui V[K_{L}] se scriu în Q pe poziții mai mici sau egale cu L.

Acest fapt este intuitiv dacă se ține cont de punctul (4). Deducem că la final vectorul Q are lungime L, adică aceeași cu a lui S. Modul de reconstituire a lui S din vectorul P este corect. Trebuie să avem grijă ca, atunci când căutăm în vectorul P o apariție a valorii X, să o alegem pe ultima disponibilă, altfel pot apărea erori. Spre exemplu, pentru vectorii dați în exemplu, V=(2, 5, 7, 3, 4, 1) și P=(1, 2, 3, 2, 3, 1), dacă se alege prima apariție a lui 2 (pe poziția a doua), avem subșirul S=(2, 5, 4) care nu este crescător. Dacă însă alegem ultima apariție a lui 2 (pe poziția a patra), avem subșirul crescător maximal S=(2, 3, 4).

Calculul complexității este ușor de făcut:

  • Pentru construcția vectorilor P și Q sunt necesare N inserții în vectorul Q, care este sortat; o inserție binară cere O(\log N), așadar complexitatea primei părți este O(N\log N).
  • Pentru reconstituirea lui S se face o singură parcurgere a vectorului P, deci O(N).

Complexitatea totală a algoritmului este O(N\log N).

#include <stdio.h>
#include <stdlib.h>
#define Infinity 30000
typedef int Vector[10001];

Vector V,P,Q,*S;
int N,Len; /* Len = Lungimea vectorului Q */

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

  fscanf(F,"%d",&N);
  for(i=1;i<=N;i++) fscanf(F,"%d",&V[i]);
  fclose(F);
}

int Insert(int K,int Lo,int Hi)
{ int Mid=(Lo+Hi)/2;

  if (Lo==Hi)
    { if (Hi>Len) Q[++Len+1]=Infinity;
      Q[Lo]=K;
      return Lo;
    }
    else if (K<Q[Mid]) return Insert(K,Lo,Mid);
                     else return Insert(K,Mid+1,Hi);
}

void BuildPQ(void)
{ int i,Place;

  Len=0;Q[1]=Infinity;
  for (i=1;i<=N;i++)
    P[i]=Insert(V[i],1,Len+1);
}

void BuildS(void)
{ int i,K=N;

  S=malloc(sizeof(*S));
  for (i=Len;i;i--)
    { while (P[K]!=i) K--;
      (*S)[i]=V[K];
    }
}

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

  fprintf(F,"%d\n",Len);
  for(i=1;i<=Len;i++) fprintf(F,"%d\n",(*S)[i]);

  fclose(F);
}

void main(void)
{
  ReadData();
  BuildPQ();
  BuildS();
  WriteSolution();
}

Menționăm că în sursa de mai sus se putea construi vectorul S peste vectorul Q, deoarece pentru construirea lui S nu avem nevoie decât de elementele vectorului P. În acest fel, programul ar fi avut nevoie numai de trei vectori, iar volumul total de date nu ar fi depășit un segment. Am preferat totuși varianta în care vectorul S este alocat dinamic pentru a evita confuziile.


Problema 14

Continuăm cu două probleme foarte asemănătoare. Atât de asemănătoare, încât diferența dintre ele pare - la o privire superficială - neglijabilă. Totuși, algoritmul de rezolvare se schimbă fundamental.

ENUNȚ: N grămezi de mere trebuie împărțite la N copii. Deoarece copiii sunt buni prieteni, trebuie ca împărțirea să se facă în mod echitabil, fiecare primind același număr de mere. Spiritul de dreptate al copiilor este atât de puternic, încât ei preferă ca unele mere să nu fie date nici unui copil, decât ca unii să primească mai multe mere ca alții. O condiție suplimentară este ca fie toate merele dintr-o grămadă să fie împărțite copiilor, fie grămada să nu mai fie împărțită deloc. Desigur, interesul este ca fiecare copil să primească un număr cât mai mare de mere.

Să se selecteze un număr de grămezi din cele N astfel încât numărul total de mere să se dividă cu N, iar suma selectată să fie maximă. Dacă există mai multe soluții, se cere una singură.

Intrarea: Fișierul de intrare INPUT.TXT conține pe prima linie numărul N de grămezi (1≤N≤100). Pe a doua linie se dau cantitățile de mere din cele N grămezi (N numere naturale pozitive, toate mai mici ca 200, separate prin spații).

Ieșirea: În fișierul OUTPUT.TXT se va scrie pe prima linie numărul maxim de mere găsit. Pe a doua linie se vor tipări indicii grămezilor selectate, în ordine crescătoare.

Exemplu:

INPUT.TXT OUTPUT.TXT
4
3 2 5 7
12
1 3 4
[1]

Timp de implementare: 45 minute - maxim o oră.

Timp de rulare: 1 secundă.

Complexitate cerută: O(N^{2}).

REZOLVARE: O primă modalitate, de altfel foarte comodă, este să verificăm toate posibilitățile de a selecta grămezi. Aceasta presupune să generăm toate submulțimile mulțimii de grămezi, iar pentru fiecare submulțime să calculăm suma merelor. În felul acesta putem afla submulțimea pentru care suma merelor se divide cu N și este maximă. Din nefericire, această soluție, banal de implementat, are o complexitate exponențială, mai precis O(N\times 2^{N}), deoarece există 2^{N} submulțimi ale mulțimii grămezilor și pentru fiecare submulțime putem calcula suma merelor în timp liniar. Prin urmare, suntem departe de complexitatea cerută în enunț.

Punctul de plecare pentru rezolvarea corectă a problemei este din nou principiul de optimalitate al programării dinamice. Să notăm cu M[1], M[2], ..., M[N] cantitățile de mere din fiecare grămadă. Să considerăm că submulțimea optimă conține în total S mere, iar grămada cu numărul N face parte din ea. Fie K restul împărțirii lui M[N] la N, deci

M[N]\equiv K{\pmod  {N}}

Atunci suma S - M[N] dă restul (N-K) mod N la împărțirea prin N, de unde deducem că

S-M[N]\equiv N-K{\pmod  {N}}

De asemenea, putem afirma că S - M[N] este cea mai mare dintre toate sumele care se pot obține folosind grămezile 1, 2, ..., N-1 și care dau același rest la împărțirea prin N. Demonstrația nu este grea: dacă ar exista o sumă mai mare decât S - M[N] congruentă cu (N-K) modulo N, am putea folosi această sumă și grămada M[N] pentru a obține o sumă S’>S astfel încât

S'\equiv 0{\pmod  {N}}

Această observație ne sugerează și metoda de rezolvare a problemei. Pentru a afla care este submulțimea de sumă maximă, avem două variante:

  • Grămada N face parte din această submulțime, caz în care trebuie să descoperim cea mai mare sumă care se poate obține adunând grămezi dintre primele N-1 și care dă restul (N-K) la împărțirea prin N;
  • Grămada N nu face parte din această submulțime, caz în care trebuie să descoperim cea mai mare sumă care se poate obține adunând grămezi dintre primele N-1 și care se împarte exact la N.

Pentru că nu putem ști de la început dacă grămada a N-a face sau nu parte din submulțimea maximală, trebuie să avem răspunsul pregătit pentru ambele situații. Mai mult, pentru a putea afla care sunt sumele maxime formate cu primele N-1 grămezi care dau diferite resturi (în cazul nostru 0 sau N-K) la împărțirea prin N, trebuie să reluăm exact aceeași problemă: grămada cu numărul N-1 poate face sau nu parte din submulțime. În concluzie, putem formaliza problema astfel: avem nevoie să putem răspunde la toate întrebările de forma „Care este suma maximă care se poate forma cu grămezi din primele P astfel încât restul la împărțirea prin N să fie Q?”. Vom nota răspunsul la această întrebare cu R[P,Q] (unde 1≤PN și 0≤Q<N). Răspunsurile tuturor întrebărilor se pot deci dispune într-o matrice R, iar scopul nostru este să-l aflăm pe R[N,0]. Am observat că pentru a-l putea afla pe R[P,Q] avem nevoie de două valori din linia P-1 a matricei (după cum grămada P face sau nu parte din submulțimea optimă). Pentru a afla toate elementele liniei P a matricei, este deci foarte probabil să avem nevoie de întreaga linie P-1.

Astfel, problema se reduce la a compune o linie a matricei din cea precedentă. Dacă presupunem că grămada P nu intră în componența submulțimii optime, atunci linia P este identică cu linia P-1:

R[P,Q]=R[P-1,Q],\forall 0\leq Q<N

Dacă presupunem că grămada P face parte din submulțime, atunci avem egalitatea:

R[P,Q]=R[P-1,(Q-M[P])\,{\bmod  \,}N]+M[P],\forall 0\leq Q<N

Alegând dintre aceste variante pe cea care ne convine mai mult, obținem:

R[P,Q]=\max {\begin{Bmatrix}R[P-1,Q]\\R[P-1,(Q-M[P])\,{\bmod  \,}N]+M[P]\end{Bmatrix}}\forall 0\leq Q<N

În felul acesta se completează fără nici un fel de probleme matricea R. După cum am spus, R[N,0] indică suma maximă divizibilă cu N. Mai rămâne de văzut cum se face reconstituirea soluției. De fapt, nu avem decât să parcurgem aceleași etape ale raționamentului, dar în sens invers. Respectiv: dacă R[N,0] = R[N-1,0], atunci deducem că grămada a N-a nu a fost folosită pentru a se obține suma maximă și avem nevoie să obținem suma maximă divizibilă cu N din primele N-1 grămezi (adică R[N-1,0]). Dacă R[N,0] ≠ R[N-1,0], atunci grămada a N-a a fost folosită și avem nevoie să obținem suma maximă de rest (N-M[N]) modulo P folosind primele N-1 grămezi. Pe cazul general, pentru a obține suma maximă de rest Q folosind primele P grămezi, avem două posibilități:

  • Dacă R[P,Q] = R[P-1,Q], atunci grămada P nu este folosită și trebuie să obținem același rest Q folosind doar primele P-1 grămezi;
  • Dacă R[P,Q] ≠ R[P-1,Q], atunci grămada P este folosită și trebuie să obținem restul (Q- M[P]) modulo N folosind primele P-1 grămezi;

Menționăm că programul este puțin diferit de ceea ce s-a explicat până acum, în sensul că prima linie din matricea R corespunde ultimei grămezi de mere, a doua linie corespunde penultimei grămezi de mere ș.a.m.d. Cu alte cuvinte, grămezile de mere sunt procesate în ordine inversă. Am făcut acest lucru pentru a ușura procedura de aflare a soluției; se observă că prima oară se decide dacă ultima grămadă face parte din submulțime, apoi penultima etc. Deci și la găsirea soluției se generează grămezile în ordine inversă. Prin această dublă inversiune, indicii grămezilor de mere selectate vor fi listați în ordine crescătoare. Dacă am fi prelucrat grămezile de mere în ordinea lor din fișier, s-ar fi impus scrierea unei proceduri recursive pentru afișarea soluției.

Să facem și calculul complexității acestui program. Citirea datelor se face în O(N), la fel și reconstituirea soluției. Pentru a completa o linie din matrice, avem nevoie să parcurgem linia precedentă, adică O(N). Pentru compunerea întregii matrice, timpul necesar este pătratic.

Mai trebuie făcută o singură observație referitoare la modul de inițializare a matricei. Vom adăuga în matricea R linia cu numărul 0, care va conține sumele maxime ce se pot obține fără a folosi nici o grămadă. Desigur, se poate obține numai suma 0, care dă restul 0 la împărțirea prin N, iar alte sume nu se pot obține. Vom pune deci R[0,0]=0 și R[0,i]=Impossible pentru orice 1 ≤ i < N, unde Impossible este o constantă specială (preferabil negativă, pentru a nu se confunda cu valorile obișnuite din matrice).

#include <stdio.h>
#define NMax 101
#define Impossible -30000

int M[NMax], R[NMax][NMax], N;
void ReadData(void)
{ FILE *F = fopen("input.txt", "rt");
  int i;

  fscanf(F, "%d\n", &N);
  for (i=1; i<=N; fscanf(F, "%d", &M[i++]));
  fclose(F);
}

void Share(void)
{ int i,j;

  R[0][0]=0;
  for (i=1; i<N; R[0][i++]=Impossible);

  for (i=1; i<=N; i++)
    {
      for (j=0; j<N; j++)
        R[i][j] = R[i-1][j];
      for (j=0; j<N; j++)
        if (R[i-1][j] != Impossible
           && R[i-1][j] + M[N+1-i] > 
              R[i][ (R[i-1][j]+M[N+1-i]) % N ])
         R[i][ (R[i-1][j]+M[N+1-i]) % N ] =
         R[i-1][j] + M[N+1-i];
    }
}

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

  fprintf(F, "%d\n", R[N][0]);
  j=0;
  for (i=N; i; i--)
    if (R[i][j] != R[i-1][j])
      {
        fprintf(F, "%d ", N+1-i);
        j = (j + N - M[N+1-i]%N) % N;
      }
  fprintf(F, "\n");
  fclose(F);
}

void main(void)
{
  ReadData();
  Share();
  WriteSolution();
}


Problema 15

Problema următoare a fost propusă la proba de baraj de la Olimpiada Națională de Informatică, Slatina 1995 și este un exemplu tipic de aplicare a principiului lui Dirichlet.

ENUNȚ: La un SHOP din Slatina se găsesc spre vînzare P-1 (P este un număr prim) produse unicat de costuri X(1)$, X(2)$, ..., X(P-1)$. Nici unul din produse nu poate fi cumpărat prin plata exactă cu bancnote de P$. în SHOP intră un olimpic care are un număr nelimitat de bancnote de P$ și o singură bancnotă de Q$ (1 ≤ QP-1). Ce produse trebuie să cumpere olimpicul pentru a putea plăti exact produsele cumpărate?

Intrarea: Datele de intrare se dau în fișierul de intrare INPUT.TXT ce conține două linii:

  • pe prima linie valorile lui P și Q;
  • pe a doua linie valorile costurilor produselor.

Ieșirea se va face în fișierul OUTPUT.TXT unde se vor lista în ordine crescătoare indicii produselor cumpărate de olimpic.

Exemplu:

INPUT.TXT OUTPUT.TXT
5 4
1 3 6 7
1 2

Timp de implementare: la Slatina s-au acordat cam 90 de minute, dar 45 ar trebui să fie suficiente.

Timp de rulare pentru fiecare test: 1 sec.

Complexitate cerută: O(P).

Enunțul original nu specifica nici o limită maximă pentru valoarea lui P. Vom adăuga noi această limită, respectiv P < 10000.

REZOLVARE: Problema se reduce la a găsi un grup de obiecte pentru care suma costurilor să fie divizibilă cu P sau să fie congruentă cu Q modulo P. Am văzut deja în problema precedentă că dispunem de o soluție O(N^{2}) pentru a găsi un număr de elemente care să se dividă cu P. În cazul nostru, trebuie să observăm însă că nu avem P obiecte, ci numai P-1; în schimb, dispunem de o bancnotă suplimentară de valoare Q. Aceste diferențe vor fi explicate mai târziu și se va vedea că ele nu schimbă cu nimic natura problemei. Diferența esențială provine din faptul că nu se mai cere ca suma numerelor să fie maximă, ca în problema precedentă. Orice combinație de numere care dau o sumă potrivită este suficientă.

Să începem prin a explica principiul lui Dirichlet, care de altfel face apel numai la intuiție și nu necesită cunoștințe speciale de matematică. Acest principiu spune că dacă distribuim N obiecte în K cutii, atunci cel puțin într-o cutie se vor afla minim \lceil N/K\rceil obiecte (aici prin \lceil N/K\rceil se înțelege „cel mai mic întreg mai mare decât[2] N/K”). Demonstrația se face prin reducere la absurd: dacă în fiecare cutie s-ar afla mai puțin decât \lceil N/K\rceil obiecte, atunci numărul total de obiecte ar fi mai mic decât K\times \lceil N/K\rceil , adică mai mic decât N.

Spre exemplu, oricum am distribui 7 obiecte în 4 cutii, putem fi siguri că cel puțin într-o cutie se vor afla minim \lceil 7/4\rceil =2 obiecte. Într-adevăr, dacă toate cutiile ar conține cel mult câte un obiect, atunci numărul total de obiecte nu ar putea fi mai mare ca 4, ceea ce este absurd.

Să vedem acum cum s-ar putea aplica acest principiu la problema de față. Să facem notația

S(k)=\sum _{{i=1}}^{{k}}X(i)

și convenția S(0) = 0. Prin urmare, putem scrie egalitatea

S(k_{2})-S(k_{1})=\sum _{{i=k_{1}}}^{{k_{2}}}X(i)

Dacă găsim în vectorul S două valori S(k_{1}) și S(k_{2}) care dau același rest la împărțirea prin P, înseamnă că diferența lor se divide cu P, deci șirul de obiecte k_{1}+1,k_{1}+2,\dots ,k_{2} poate constitui o soluție.

Să presupunem pentru început că dispunem de P obiecte. Se pune întrebarea: ce valori poate lua restul împărțirii lui S(k) prin P? Desigur, orice valoare între 0 și P-1. Există deci în total P resturi distincte. Pe de altă parte, există P+1 elemente în vectorul S (se consideră și elementul S(0)). Începem să recunoaștem aici principiul lui Dirichlet, în care „obiectele” sunt resturile S(0)\,{\bmod  \,}P,\,S(1)\,{\bmod  \,}P,\,\dots ,S(P)\,{\bmod  \,}P, iar cutiile sunt clasele de resturi modulo P. Avem de distribuit P+1 obiecte în P cutii, așadar cel puțin într-o cutie se vor afla \lceil (P+1)/P\rceil =2 obiecte. Prin urmare, vor exista cu siguranță doi indici k_{1}<k_{2} astfel încât S(k_{2})-S(k_{1})\equiv 0{\pmod  {P}}. Nu avem decât să tipărim secvența k_{1}+1,k_{1}+2,...,k_{2}.

Să vedem acum ce se întâmplă dacă avem numai P-1 obiecte, așa cum este cazul problemei. Atunci avem numai P resturi posibile, deci se poate ca toate elementele din S să dea resturi distincte la împărțirea prin P. Dar în acest caz, există un indice k astfel încât S(k)\equiv Q{\pmod  {N}}, deci trebuie doar să tipărim secvența de indici 1, 2, ..., k.

Pentru a reuni aceste două cazuri într-unul singur, putem considera expresia S(k) drept un alt mod de a scrie expresia S(k) - S(0). Problema se reduce la a căuta doi indici k_{1},k_{2}\in \{0,1,2,...,P\} astfel încât (S(k_{2})-S(k_{1}))\,{\bmod  \,}N\in [0,Q]. Să nu uităm că trebuie să efectuăm această operație într-un timp liniar, deci nu avem voie să comparăm pur și simplu două câte două elementele vectorului S. Vom prezenta modul în care se pot găsi două elemente congruente modulo P, cazul celălalt tratându-se analog. Metoda constă în crearea unui alt vector, L, în care L(i) = j înseamnă că suma S(j) dă restul i la împărțirea prin P. Inițial, toate elementele vectorului L vor avea o valoare specială, eventual negativă. Apoi se parcurge vectorul S și pentru fiecare S(j) se efectuează operația L(S(j) mod P)=j. În momentul în care se încearcă reatribuirea unui element din L care are deja o valoare dată, înseamnă că am găsit cei doi indici pe care îi căutam.

Iată un exemplu. Dacă P=7 și X=(8, 8, 2, 6, 13, 3), rezultă vectorul S=(8, 16, 18, 24, 37, 40). Resturile la împărțirea prin 7 sunt respectiv 1, 2, 4, 3, 2 și 5.

Psycho-fig69.png

După cum se vede, restul 2 poate fi obținut atât cu primele două obiecte, cât și cu primele 5, deci suma prețurilor obiectelor 3, 4 și 5 este divizibilă cu 7.

Un ultim detaliu de implementare constă în aceea că nu este necesară memorarea vectorului S, ci numai a elementului curent; orice alte informații care ne trebuie la un moment dat le putem afla din vectorii X și L. Pentru memorarea elementului curent din S, se pornește cu valoarea 0 și la fiecare pas se adaugă valoarea elementului corespunzător din X.

#include <stdio.h>
#define NMax 10000
#define None -1

int X[NMax], L[NMax], P, Q;

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

  fscanf(F, "%d %d\n", &P, &Q);
  for (i=1; i<P; fscanf(F, "%d", &X[i++]));
  fclose(F);
}

void FindSum(void)
{ long S=0;
  FILE *F = fopen("output.txt", "wt");
  int i,j;

  for (i=1, L[0]=0; i<P; L[i++] = None);
  i=0;
  while ( L[ (S+=X[++i]) % P ]==None && // Restul 0
          L[ (S%P+P-Q) % P ]==None )    // Restul Q
    L[S%P]=i;
  for (j = 1 + ((L[S%P]!=None)? L[S%P]: L[ (S%P+P-Q) % P ]);
       j <= i; fprintf(F, "%d ", j++));
  fclose(F);
}

void main(void)
{
  ReadData();
  FindSum();
}


Problema 16

Următoarele probleme aparțin categoriei de probleme pe care, dacă ne grăbim, le putem clasifica drept „ușoare”. Într-adevăr, ele au soluții vizibile și foarte la îndemână, dar și soluții mai subtile și mult mai performante. Pentru a obliga cititorul să se gândească și la aceste soluții, am ales limite pentru datele de intrare suficient de mari încât să facă nepractice rezolvările „la minut”.

ENUNȚ: (Generarea unui arbore oarecare când i se cunosc gradele) Se dă un vector cu N numere întregi. Se cere să se construiască un arbore cu N noduri numerotate de la 1 la N astfel încât gradele celor N noduri să fie exact numerele din vector. Dacă acest lucru nu este posibil, se va da un mesaj de eroare corespunzător.

Intrarea: Datele de intrare se află în fișierul INPUT.TXT. Pe prima linie se află numărul de noduri N (N ≤ 10000), iar pe a doua linie se află cele N numere separate prin spații. Toate numerele sunt strict pozitive și mai mici ca 10000.

Ieșirea se va face în fișierul OUTPUT.TXT. Dacă problema are soluție, se va tipări arborele prin muchiile lui. Fiecare muchie se va lista pe câte o linie, prin nodurile adiacente separate printr-un spațiu. Dacă problema nu are soluție, se va afișa un mesaj corespunzător.

Exemple:

INPUT.TXT OUTPUT.TXT
6
1 2 3 2 1 1
1 4
2 5
3 6
4 6
5 6
3
2 2 1
Problema nu are solutie!

Timp de implementare: 30 minute - 45 minute.

Timp de rulare: 2-3 secunde.

Complexitate cerută: O(N\log N); dacă vectorul citit la intrare se presupune sortat, se cere o complexitate O(N).

REZOLVARE: Să începem prin a ne pune întrebarea: când are problema soluție și când nu?

Se știe că un arbore oarecare cu N noduri are N-1 muchii. Fiecare din aceste muchii va contribui cu o unitate la gradele nodurilor adiacente. Deducem de aici că suma gradelor tuturor nodurilor este egală cu dublul numărului de muchii, adică, notând cu G[1], G[2], ..., G[N] gradele nodurilor,

\sum _{{i=1}}^{{N}}G[i]=2\cdot (N-1)

Am aflat deci o condiție necesară pentru ca problema să aibă soluție. O a doua condiție este ca toate nodurile să aibă grade cuprinse între 1 și N-1. Totuși, ținând cont de afirmația enunțului că toate numerele din vector sunt strict pozitive, rezultă că a doua condiție nu mai trebuie verificată. Iată de ce: să presupunem că am verificat prima condiție și am constatat că suma celor N numere este 2(N-1), iar unul dintre numere este cel puțin N. Atunci ar rezulta că suma celorlalte N-1 numere este cel mult N-2, de unde rezultă că există cel puțin un nod de grad 0, ceea ce contrazice informația din enunț. Prin urmare, numai prima condiție este importantă, cea de-a doua fiind redundantă.

Vom demonstra că această condiție este și suficientă indicând efectiv modul de construcție a arborelui în cazul în care ea este satisfăcută. Începem prin a sorta vectorul de numere. Acest lucru era oricum de așteptat, deoarece complexitatea N\log N ne-o permite. Trebuie numai să avem grijă să alegem un algoritm de sortare de complexitate N\log N. Programul care urmează folosește heapsort-ul. Odată ce am sortat vectorul, trebuie să reconstituim muchiile în timp liniar, și iată cum:

  • Se poate demonstra că primele două elemente din vectorul sortat au valoarea 1. Într-adevăr, dacă toate elementele ar fi mai mari sau egale cu 2, atunci suma lor ar fi mai mare sau egală cu 2N, ori noi știm că suma trebuie să fie 2N-2, adică există cel puțin două elemente egale cu 1 în vector. Acest lucru rezultă imediat dacă ne gândim că orice arbore are cel puțin două frunze.
  • Vom căuta în vector primul număr mai mare sau egal cu 2. Se pune întrebarea: există întotdeauna acest număr? Nu cumva există un arbore în care toate nodurile au grad 1? Să aplicăm condiția precedentă și să vedem ce se întâmplă. Dacă toate nodurile au grad 1, atunci suma gradelor este N, ceea ce conduce la ecuația:
N=2\cdot (N-1)\implies N=2
  • Iată deci că există un singur arbore în care toate nodurile sunt frunze, anume cel cu 2 noduri unite printr-o muchie. Vom reveni mai târziu la acest caz particular. Deocamdată presupunem că există în vector un număr mai mare ca 1, pe poziția K în vector. Atunci vom uni nodul 1 din arbore (care știm că are gradul 1) cu nodul K. În felul acesta, nodul 1 și-a completat numărul necesar de vecini și poate fi neglijat pe viitor, iar G[K] va fi decrementat cu o unitate, întrucât nodul K și-a completat unul din vecini. Astfel, problema s-a redus la un arbore cu N-1 noduri numerotate de la 2 la N.
  • Vectorul G este în continuare sortat, deoarece G[K-1] = 1 < G[K] ≤ G[K+1] înainte de decrementarea lui G[K], deci după decrementare vom avea G[K-1] = 1 ≤ G[K] < G[K+1], adică dubla relație de ordonare se păstrează.
  • Întrucât secvența G[2], G[3], ..., G[N] reprezintă gradele unui arbore, putem aplica același raționament ca mai înainte pentru a deduce că G[2]=1. Cu ce nod vom uni nodul 2? Dacă G[K]>1, îl vom uni cu nodul K. Dacă prin decrementare, G[K] a ajuns la valoarea 1, vom trece la nodul K+1 (despre care știm că are gradul mai mare ca 1) și vom trasa muchia 2 ↔ (K+1).
  • Procedeul acesta se repetă până când au fost trasate N-2 muchii. Aceasta înseamnă că a mai rămas o singură muchie de trasat. Iată deci că, mai devreme sau mai târziu, este oricum inevitabil să ajungem la cazul particular de arbore de care am amintit mai devreme. Deoarece la primul pas am unit nodul 1 cu nodul K, la al doilea pas am unit nodul 2 cu un alt nod (K sau K+1) ș.a.m.d., rezultă că în N-2 iterații, toate nodurile de la 1 la N-2 și-au completat numărul de vecini. De aici rezultă că ultima muchie pe care o vom trasa este (N-1) ↔ N; putem să tipărim această muchie „cu ochii închiși”, fără nici un fel de teste suplimentare. Ultima muchie trasată este diferită de celelalte și necesită o operație separată de trasare din cauză că, în timp ce primele N-2 iterații uneau o frunză cu un nod intern, această ultimă iterație are de unit două frunze, deci nu are sens să mai căutăm un nod de grad mai mare ca 1.

Aceasta este metoda de lucru. Calculul complexității este simplu: Avem nevoie doar de doi indici: Unul care marchează frunza curentă (în program el se numește pur și simplu i) și care avansează la fiecare pas, și unul care marchează primul număr mai mare ca 1 din vector (în program se numește First) și care se incrementează cu cel mult 1 la fiecare pas (deci de mai puțin de N ori în total). De aici rezultă complexitatea liniară a algoritmului.

Să vedem cum se comportă această metodă pe cazul particular al exemplului 1:

Psycho-fig70.png

Mai trebuie remarcat că soluția nu este unică. Propunem ca temă cititorului să scrie un program care să verifice în timp O(N\log N) dacă soluția furnizată de un alt program este corectă.

#include <stdio.h>
int G[10001], N;
long Sum;
FILE *OutF;

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

  fscanf(F,"%d\n",&N);
  for (i=1, Sum=0; i<=N; i++)
    { fscanf(F,"%d",&G[i]);
      Sum+=G[i];
    }
  fclose(F);
}

void Sift(int K, int N)
/* Cerne al K-lea element dintr-un heap de N elemente */
{ int Son;

  /* Alege un fiu mai mare ca tatal */
  if (K<<1<=N)
    { Son=K<<1;
      if (K<<1<N && G[(K<<1)+1]>G[(K<<1)])
        Son++;
      if (G[Son]<=G[K]) Son=0;
    }
    else Son=0;
  while (Son)
    { /* Schimba G[K] cu G[Son] */
      G[K]=(G[K]^G[Son])^(G[Son]=G[K]);
      K=Son;
      /* Alege un alt fiu */
      if (K<<1<=N)
        { Son=K<<1;
          if (K<<1<N && G[(K<<1)+1]>G[(K<<1)])
            Son++;
          if (G[Son]<=G[K]) Son=0;
        }
        else Son=0;
    }
}

void HeapSort(void)
{ int i;

  /* Construieste heap-ul */
  for (i=N>>1; i;) Sift(i--,N);
  /* Sorteaza vectorul */
  for (i=N; i>=2;)
    { G[1]=(G[1]^G[i])^(G[i]=G[1]);
      Sift(1,--i);
    }
}

void Match(void)
{ int i, First=1;

  while (G[First]==1 && First<N) First++;
  /* Trebuie adaugata si conditia First<N
     pentru a acoperi cazul particular N=2 */
  for (i=1; i<=N-2; i++)
    { fprintf(OutF,"%d %d\n", i, First);
      First+=(--G[First]==1);
    }
  fprintf(OutF,"%d %d\n", N-1, N);
}

void main(void)
{
  ReadData();
  OutF=fopen("output.txt","wt");
  if (Sum==(N-1)<<1)
    { HeapSort();
      Match();
    }
    else fputs("Problema nu are solutie!\n",OutF);
  fclose(OutF);
}


Problema 17

Iată un nou exemplu de problemă care admite două rezolvări: una evidentă, dar neeficientă și una mai puțin evidentă dar cu mult mai eficientă.

ENUNȚ: Fie V un vector. Arborele cartezian atașat vectorului V este un arbore binar care se obține astfel: Dacă vectorul V este vid (are 0 elemente), atunci arborele cartezian atașat lui este de asemenea vid. Altfel, se selectează elementul de valoare minimă din vector și se pune în rădăcina arborelui, iar arborii cartezieni atașați fragmentelor de vector din stânga (respectiv din dreapta) elementului minim se pun în subarborele stâng, respectiv drept al rădăcinii. Iată, de exemplu, care este arborele cartezian al următorului vector cu 8 elemente:

Psycho-fig71.png

În figură au fost încadrate prin dreptunghiuri punctate porțiunile din stânga, respectiv din dreapta elementului minim, împreună cu subarborii atașați. Trebuie observat că arborele cartezian atașat unui vector poate să nu fie unic, în cazul în care există mai multe elemente de valoare minimă. Vom impune ca o condiție suplimentară ca elementul care va fi trecut în rădăcină să fie cel mai din stânga dintre minime (cel cu indicele cel mai mic). Astfel, arborele cartezian este unic.

Cerința problemei este ca, dându-se un vector, să i se construiască arborele cartezian.

Intrarea: Fișierul de intrare INPUT.TXT conține pe prima linie valoarea lui N (N ≤ 10000), iar pe a doua N numere naturale mai mici ca 30000, separate prin spații.

Ieșirea se va face în fișierul text OUTPUT.TXT sub următoarea formă:

T_{1}\quad T_{2}\quad T_{3}\quad \dots \quad T_{N}

unde T_{i} este indicele în vector al elementului care este părintele lui V[i] în arborele cartezian. Dacă V[i] este rădăcina arborelui, atunci T_{i}=0.

Exemplu: Pentru exemplul dat mai sus, fișierul INPUT.TXT este:

8
8 2 4 1 5 3 6 4

După cum reiese din figură, tatăl elementului 8 este elementul 2, adică al doilea în vector; tatăl elementului 2 este elementul 1, adică al 4-lea în vector; tatăl elementului 5 este elementul 3, adică al 6-lea în vector ș.a.m.d. Fișierul de ieșire este deci:

2 4 2 0 6 4 8 6

Complexitate cerută: O(N).

Timp de implementare: 45 minute - 1h.

Timp de rulare: 2 secunde.

REZOLVARE: Nu întâmplător s-a impus o complexitate liniară pentru rezolvarea acestei probleme. Altfel, ea ar fi trivială în O(N^{2}), prin următoarea metodă: scriem o procedură care parcurge vectorul și caută minimul, apoi se reapelează pentru bucățile de vector aflate în stânga, respectiv în dreapta minimului. Pentru a demonstra că această variantă de rezolvare are complexitate pătratică, să ne imaginăm cum s-ar comporta ea pe cazul:

V=(N\quad N-1\quad N-2\quad \dots \quad 2\quad 1)

La primul apel, procedura ar face N comparații pentru a parcurge vectorul (deoarece elementul minim este ultimul în vector) și s-ar reapela pentru porțiunea din vector care cuprinde primele N-1 elemente. La al doilea apel, ar face N-1 comparații și s-ar reapela pentru primele N-2 elemente etc. În concluzie, numărul total de comparații făcute este

N+(N-1)+(N-2)+\cdots +1={\frac  {N(N+1)}{2}}

de unde rezultă complexitatea. O problemă interesantă, pe care îi vom lăsa plăcerea cititorului să o rezolve, este de a demonstra că această versiune nu poate atinge o complexitate mai bună decât O(N\log N) și de a arăta care sunt cazurile cele mai favorabile pe care se obține această complexitate.

A doua metodă este și ea destul de ușor de înțeles și de implementat. Ceea este mai greu de acceptat este că ea are complexitate liniară, așa cum vom încerca să explicăm la sfârșit. Iată mai întâi principiul de rezolvare: vom porni cu un arbore cartezian vid și, la fiecare pas, vom adăuga câte un element al vectorului V la acest arbore, astfel încât structura obținută să rămână un arbore cartezian. La al k-lea pas, vom adăuga elementul V[k] în arbore și vom restructura arborele în așa fel încât să obținem arborele cartezian atașat primelor k elemente din V. Trebuie să ne concentrăm atenția asupra a două lucruri:

  1. Cunoscând arborele cartezian atașat primelor k-1 vârfuri și elementul V[k], cum se obține arborele cartezian atașat primelor k vârfuri?
  2. Cum reușim să actualizăm de N ori arborele astfel încât timpul total consumat să fie liniar?

Pentru a răspunde la prima întrebare, pe lângă vectorii V și T, mai este necesară o stivă S, în care vom stoca elemente ale vectorului V. Inițial, stiva este vidă. Atunci când un nou element X sosește, el va fi introdus în stivă imediat după ultimul număr din stivă care are o valoare mai mică sau egală cu X. Toate elementele care se aflau înainte în stivă pe poziții mai mari sau egale cu poziția pe care a fost inserat X vor fi eliminate din stivă, iar elementul care se afla exact pe poziția lui X va deveni fiul stâng al lui X. X însuși va deveni fiul drept al predecesorului său în stivă. La fiecare moment, primul element din stivă este rădăcina arborelui cartezian.

Pentru a înțelege mai bine principiul de funcționare al stivei, să analizăm mai de aproape exemplul din enunț.

La început stiva este vidă. Primul element din V are valoarea 8, drept care îl vom pune în stivă, iar arborele cartezian va avea un singur nod:

Psycho-fig72.png

Următorul element sosit este 2. Acesta este mai mic decât 8, deci trebuie introdus înaintea lui în stivă. El va fi deci primul element din stivă și rădăcina arborelui cartezian la acest moment. Concomitent, 8 va fi eliminat din stivă și va deveni fiul stâng al lui 2:

Psycho-fig73.png

Se observă că arborele obținut este tocmai arborele cartezian atașat secvenței (V[1], V[2]). Următorul element este 4, care este mai mare decât 2, deci trebuie adăugat în vârful stivei. Nici un element nu este eliminat din stivă, iar 4 devine fiul drept al lui 2:

Psycho-fig74.png

Următorul element sosit este 1, care este mai mic decât toate numerele din stivă. Stiva se va goli, iar numărul 2 (cel peste care se va scrie 1) va deveni fiul stâng al lui 1:

Psycho-fig75.png

Deja arborele începe să semene cu forma sa finală. Urmează elementul 5, care va fi adăugat în stivă și „atârnat” în dreapta lui 1:

Psycho-fig76.png

Elementul 3 este mai mic[3] ca 1, căruia îi va deveni fiu drept, dar mai mare[4] ca 5, pe care îl va elimina din stivă:

Psycho-fig77.png

Următorul număr, 6, va fi adăugat la extremitatea dreaptă a arborelui și în vârful stivei:

Psycho-fig78.png

În sfârșit, elementul 4 va fi fiul drept al lui 3 și îl va elimina din stivă pe 6, care îi va deveni fiu stâng:

Psycho-fig79.png

Se observă că arborele a ajuns tocmai la forma sa corectă. Trebuie acum să ne ocupăm de un detaliu de implementare. Pentru a afla poziția pe care trebuie inserat un element în stivă avem două metode:

  1. Putem să căutăm în stivă de la dreapta la stânga (ar fi mai corect spus „de la vârf spre bază”) până dăm de un element mai mic decât cel de inserat; programul folosește această metodă și îi vom discuta în final eficiența.
  2. Putem face o căutare binară în stivă, întrucât elementele din stivă au valori crescătoare de la bază spre vârf (lăsăm demonstrația acestei afirmații în seama cititorului). O căutare binară într-un vector de k elemente poate necesita, în cazul cel mai nefavorabil, \log k comparații. În cazul cel mai nefavorabil, când vectorul V este sortat crescător, elementele vor fi introduse pe rând în stivă și nu vor mai fi scoase, deci la fiecare pas se vor face \log k comparații, unde k ia valori de la 1 la N. Complexitatea care rezultă este mai slabă decât cea cerută:

O(\log 1+\log 2+\cdots +\log N)=O(\sum _{{k=1}}^{{N}}\log k)=O(\log \prod _{{k=1}}^{{N}}k)=O(\log N!)=O(N\cdot \log N)

Acesta este unul din puținele cazuri în care căutarea binară este mai ineficientă decât cea secvențială.

Pentru ușurința programării, sursa C de mai jos reține în stiva S nu valorile elementelor, ci indicii lor în vectorul V (deoarece aceștia sunt ceruți pentru construcția vectorului T).

#include <stdio.h>
#define NMax 10001

int V[NMax], /* Vectorul */
    T[NMax], /* Vectorul de tati */
    S[NMax], /* Stiva */
    N;       /* Numarul de elemente */

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

  fscanf(F,"%d\n",&N);
  for (i=1; i<=N;)
    fscanf(F, "%d", &V[i++]);
}

void BuildTree(void)
{ int i,k,LenS=0;

  S[0]=0; /* Pentru ca initial T[1] sa fie 0 */
  for (i=1; i<=N; i++)
    { /* Cauta pozitia pe care va fi inserat V[i] */
      k=LenS+1;
      while (V[S[k-1]]>V[i]) k--;
      /* Face corecturile in S si T */
      T[i]=S[k-1];
      if (k<=LenS) T[S[k]]=i;
      /* i este ultimul element din stiva, deci... */
      S[LenS=k]=i;
    }
}

void WriteSolution(void)
{ FILE *F=fopen("output.txt","wt");
  int i;
  for (i=1; i<=N;)
    fprintf(F,"%d ",T[i++]);
  fprintf(F,"\n");
}

void main(void)
{
  ReadData();
  BuildTree();
  WriteSolution();
}

Acum să analizăm și complexitatea acestui algoritm. În primul rând, ea nu poate fi mai bună decât O(N), pentru că aceasta este complexitatea funcțiilor de intrare și ieșire. Procedura BuildTree se compune dintr-un ciclu for în care se execută patru operații în timp constant și o instrucțiune repetitivă while. Numărul total de operații în timp constant care se execută în procedură este prin urmare O(N). Problema este: care este numărul total maxim de evaluări ale condiției logice din bucla while? Aparent, bucla while se execută de O(N) ori, deci numărul total de evaluări ar fi O(N^{2}). Să aruncăm totuși o privire mai atentă.

Fiecare evaluare a condiției din bucla while are ca efect decrementarea lui k și, implicit, eliminarea unui element deja existent în stivă. Pe de altă parte, fiecare element este introdus în stivă o singură dată și deci nu poate fi eliminat din stivă decât cel mult o dată. Așadar numărul maxim de elemente ce pot fi eliminate din stivă pe parcursul executării procedurii BuildTree este N-1, deci numărul total de evaluări ale condiției este O(N). De aici rezultă că programul are complexitate liniară.


Problema 18

ENUNȚ: Se dă un vector nesortat cu elemente numere reale oarecare. Considerând că vectorul ar fi sortat, se cere să se găsească distanța maximă între două elemente consecutive ale sale, fără însă a sorta efectiv vectorul.

Intrarea: Fișierul INPUT.TXT conține pe prima linie numărul N de elemente din vector (N ≤ 5000). Pe următoare linie se dau numerele separate prin spații.

Ieșirea: Pe ecran se va tipări un mesaj de forma:

Distanța maximă este D

Exemplu: Pentru fișierul de intrare cu conținutul

4
5 3.2 2 3.7

răspunsul trebuie să fie

Distanța maximă este 1.5

Timp de implementare: 30 minute.

Timp de rulare: 2-3 secunde.

Complexitate cerută: O(N).

REZOLVARE: Desigur că primul lucru la care ne gândim este să sortăm vectorul și să îl parcurgem apoi de la stânga la dreapta, căutând distanța maximă între două elemente consecutive. Complexitatea unui asemenea algoritm este O(N\log N). Nici această soluție nu este rea, iar la un concurs, comisiei de corectare i-ar veni destul de greu să găsească teste care să departajeze un algoritm în O(N\log N) de unul liniar, chiar și pentru N = 5000. Totuși, vom arăta care este algoritmul liniar; în primul rând de dragul „artei”, iar în al doilea rând pentru că nu este cu mult mai greu de implementat decât o sortare.

Primul lucru care trebuie făcut este găsirea maximului și a minimului din vector; să notăm aceste valori cu V_{{{\mathit  {max}}}} și V_{{{\mathit  {min}}}}. Aceste operații se fac în timp liniar, eventual chiar la citirea datelor din fișier. Apoi se împarte intervalul [V_{{{\mathit  {max}}}},V_{{{\mathit  {min}}}}[5] de pe axa reală în N-1 intervale egale. Iată cazul exemplului din enunț, unde V_{{{\mathit  {min}}}}=2 și V_{{{\mathit  {max}}}}=5:

Psycho-fig80.png

Lungimea fiecărui interval va fi deci de

D={\frac  {V_{{{\mathit  {max}}}}-V_{{{\mathit  {min}}}}}{N-1}}\quad (în cazul nostru D=1)

De ce s-a făcut această împărțire? Dacă notăm cu D_{{{\mathit  {max}}}} distanța maximă pe axă între două numere vecine, adică tocmai valoarea pe care o căutăm, se poate demonstra că D_{{{\mathit  {max}}}}\geq D. Într-adevăr, între cele N numere de pe axă se formează N-1 intervale. Dacă presupunem că D_{{{\mathit  {max}}}}<D, rezultă că distanța între oricare două numere consecutive de pe axă este mai mică decât D. De aici deducem că distanța dintre primul și ultimul număr, adică , este mai mică decât de (N-1) ori D. Dar aceasta duce la relația:

V_{{{\mathit  {max}}}}-V_{{{\mathit  {min}}}}<(N-1)\cdot {\frac  {V_{{{\mathit  {max}}}}-V_{{{\mathit  {min}}}}}{N-1}}\implies V_{{{\mathit  {max}}}}-V_{{{\mathit  {min}}}}<V_{{{\mathit  {max}}}}-V_{{{\mathit  {min}}}},

relație care este absurdă; demonstrația afirmației D_{{{\mathit  {max}}}}\geq D este completă.

Următorul pas pe care îl avem de făcut este să parcurgem încă o dată vectorul de numere și să aflăm pentru fiecare element căruia dintre intervalele de lungime îi aparține. Și această operație se poate face în O(N). Convenim ca dacă un număr X se află exact la limita dintre două intervale, adică

X=V_{{{\mathit  {min}}}}+k\cdot D,\quad 0\leq k<N

el să fie considerat ca aparținând intervalului din dreapta. Aceasta înseamnă că elementul de valoare V_{{{\mathit  {max}}}} nu aparține nici unuia din cele N-1 intervale, ci celui de-al N-lea interval, [V_{{{\mathit  {max}}}},V_{{{\mathit  {max}}}}+D]. Să vedem la ce ne ajută acest lucru. Din moment ce D_{{{\mathit  {max}}}}\geq D, rezultă că este imposibil ca distanța maximă să se producă între două numere din același interval, deoarece distanța în cadrul aceluiași interval nu poate atinge valoarea D. Este deci obligatoriu ca distanța maximă să apară între două elemente din intervale distincte. Să urmărim în figura următoare ce alte proprietăți mai au aceste numere:

Psycho-fig81.png

Dacă X și Y sunt valorile între care diferența este maximă, este de la sine înțeles că între ele nu mai există nici un număr, deoarece se prespune că X și Y sunt consecutive în vectorul sortat. Aceasta înseamnă însă că X este cel mai mare număr din intervalul său, iar numărul X’ nu poate exista acolo unde a fost el figurat. Analog, Y este cel mai mic număr din intervalul său, iar numărul Y’ nu poate exista. De fapt, în nici unul din intervalele dintre cele care le cuprind pe X și Y nu poate exista nici un număr.

Prin urmare, diferența maximă se poate produce numai între maximul unui interval și minimul imediat următor. Următorul pas în găsirea soluției presupune aflarea pentru fiecare din cele N-1 intervale (sau N dacă îl considerăm și pe ultimul, cel care nu îl conține decât pe V_{{{\mathit  {max}}}}) a minimului și a maximului. Și acest pas se execută în O(N), deoarece procesarea fiecărui element din vector se reduce la numai două comparări, cu minimul și cu maximul intervalului în care se încadrează el. Vor rezulta doi vectori care în program se vor numi Lo și Hi. Iată care sunt valorile lor pentru exemplul nostru:

Psycho-fig82.png

Deoarece în intervalul [4,5) nu se află elemente, rezultă că elementele corespunzătoare din vectorii Lo și Hi trebuie să aibă o valoare specială care să informeze programul asupra acestui lucru. De exemplu, sursa oferită mai jos folosește următorul artificiu: inițializează vectorul Lo cu valori foarte mari (V_{{{\mathit  {max}}}}+1), astfel încât orice număr „repartizat” într-un interval să modifice această valoare. Similar, vectorul Hi este inițializat cu V_{{{\mathit  {min}}}}-1. Dacă pentru un interval aceste valori se păstrează până la sfârșit, putem trage concluzia că în respectivul interval nu se află nici un număr.

În continuare, elementele vectorilor Lo și Hi se amestecă formând un nou vector W care de data aceasta este sortat. Sortarea este foarte ușoară, pentru că nu avem decât să așezăm numerele în ordinea Lo[1], Hi[1], Lo[2], Hi[2], ..., Lo[N], Hi[N]. Deși la prima vedere pare că noul vector rezultat are 2N elemente, de fapt el are numai N elemente, pentru că:

  • Dacă într-un interval K există un singur număr, (cazul intervalelor [2,3) și [5,6)) sau există numai numere egale, atunci Lo[K] = Hi[K] și este suficient să copiem în W una singură dintre aceste două valori;
  • Dacă într-un interval nu există nici un număr, putem să nu copiem nici o valoare în vectorul W.

Astfel, construcția vectorului W se poate face în timp liniar, mai exact în O(2N). Se observă că la această construcție se poate întâmpla ca unele numere să „dispară”, adică să nu fie trecute în vectorul W. De exemplu, dacă între numerele 3.2 și 3.7 ar mai fi existat un număr, 3.5, el nu ar fi fost nici minim, nici maxim pentru intervalul său, deci nu ar fi fost copiat. Totuși, trierea în acest fel a elementelor nu afectează în nici un fel soluția. În cazul nostru, nu se întâmplă să dispară nici un element, deci W = (2, 3.2, 3.7, 5).

După ce am construit vectorul W, nu mai avem decât să-l parcurgem de la stânga la dreapta și să tipărim diferența maximă întâlnită între două numere consecutive (repetăm, vectorul W este sortat), această ultimă etapă necesitând și ea un timp liniar. Nu se poate obține o complexitate inferioară celei liniare, întrucât citirea datelor presupune ea însăși N operații.

Ca un detaliu de implementare, odată ce au fost construiți vectorii Lo și Hi, vectorul V nu mai este necesar, deci putem construi chiar în el vectorul W, pentru a economisi memorie.

#include <stdio.h>
#define NMax 5000
float V[NMax+1], Lo[NMax+1], Hi[NMax+1];
float Delta, Max, Min;
int N;

void ReadData(void)
/* Citeste vectorul si afla maximul si minimul */
{ FILE *F=fopen("input.txt", "rt");
  int i;

  fscanf(F, "%d\n", &N);
  fscanf(F, "%f", &V[1]);
  Max=Min=V[1];

  for (i=2; i<=N; i++)
    {
      fscanf(F, "%f", &V[i]);
      if (V[i]>Max) Max=V[i];
        else if (V[i]<Min) Min=V[i];
    }
  fclose(F);
}

void Split(void)
{ int i, K;

  Delta = (Max-Min)/(N-1);
  /* Se initializeaza vectorii Lo si Hi */
  for (i=0; i<=N; Lo[i]=Max+1, Hi[i++]=Min-1);

  /* Se construiesc intervalele */
  for (i=1; i<=N; i++)
    {
      K = (V[i]-Min)/Delta;
      if (V[i]<Lo[K]) Lo[K]=V[i];
      if (V[i]>Hi[K]) Hi[K]=V[i];
    }
}

void Rebuild(void)
/* Rescrie vectorul V, pentru a economisi memorie,
   pastrand numai capetele intervalelor */
{ int i, M=0;

  for (i=0;i<N; i++)
    {
      if (Lo[i] != Max+1) V[++M]=Lo[i];
      if (Hi[i] != Min-1 && Hi[i] != Lo[i]) V[++M]=Hi[i];
    }
  N=M;
}

void FindGap(void)
/* Acum cautarea distantei maxime se face
   secvential, vectorul fiind sortat */
{ int i;
  float Gap=0;

  for (i=2; i<=N; i++)
    if (V[i]-V[i-1] > Gap)
      Gap = V[i]-V[i-1];
  printf("Distanta maxima este %0.3f\n", Gap);
}

void main(void)
{
  ReadData();
  if (Max==Min)
    puts("0");
  else
    {
      Split();
      Rebuild();
      FindGap();
    }
}
  1. Greșeală în original, corect: 1 2 4
  2. Greșeală în original. Corect: mai mare sau egal cu
  3. Greșeală în original.
  4. Greșeală în original.
  5. Greșeală în original.