Psihologia concursurilor de informatică/6 Probleme de concurs 3

From Algopedia
Revision as of 11:30, 11 March 2018 by Cata (talk | contribs)

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);
}
  1. Greșeală în original, corect: 1 2 4
  2. Greșeală în original. Corect: mai mare sau egal cu