Psihologia concursurilor de informatică/6 Probleme de concurs 3

From Algopedia
Revision as of 10:50, 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();
}
  1. Greșeală în original, corect: 1 2 4