Difference between revisions of "Clasa a VII-a lecția 28 - 12 mar 2020"

From Algopedia
Jump to navigationJump to search
 
Line 996: Line 996:
 
* [http://varena.ro/problema/wind wind] dată la OJI 2020 clasa a 7<sup>a</sup>
 
* [http://varena.ro/problema/wind wind] dată la OJI 2020 clasa a 7<sup>a</sup>
  
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_VII/VIII_lec%C8%9Bia_27_-_31_mar_2015]
+
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_28_-_12_mar_2020]

Latest revision as of 18:46, 26 March 2020

Anunțuri

  • Sîmbătă 14 martie ora 10:00AM (ora tentativă) va avea loc un concurs la varena, organizat de Teodor Plop, instructor pregătitor la cercul de informatică de clasa a noua din liceul Vianu. El este destinat elevilor de clasa a noua și va avea probabil 3 probleme ușoare spre medii. Vă încurajez să participați.
  • Duminică 15 martie ora 10:00AM va avea loc concursul FMI No Stress organizat de Infoarena. El este destinat în general studenților începători și va consta din 9-12 probleme ușoare spre medie și va dura 5 ore. Este o bună ocazie să vă testați viteza și cunoștințele de bază (cît de siguri sînteți pe lucrul cu caractere, sau baza doi?) Vă încurajez să participați.

Probleme din care alegem ce discutăm azi

Tema 25 - rezolvări

Optim

Problema optim a fost dată la ONI 2012 clasa a 8a. Ea are o rezolvare fără programare dinamică, ineficientă și nu chiar banal de implementat și o rezolvare cu programare dinamică, eficientă și relativ ușor de implementat.

Soluția combinatorică, fără programare dinamică

Soluția comisiei, cea combinatorică, se bazează pe generarea tuturor modurilor de a plasa K înmulțiri între N operații și calculul expresiilor respective, din care vom reține minimul și maximul. Implementarea este cea de combinări modificată să calculeze incremental expresiile.

Complexitatea este O(Comb(N, K)). Pentru valori maxime obținem Comb(30, 10), aproximativ 10 milioane operații.

Soluție cu programare dinamică

Problema are două părți echivalente, minimul și maximul. Să ne concetrăm pe maxim, minimul rezolvîndu-se similar.

O definire directă a subproblemei ar putea fi:

MAX[i][j] = maximul care se poate obține cu numerele nr[0], nr[1], ..., nr[i] folosind i operații, din care j înmulțiri.

Are ea proprietatea de optimalitate?

Să vedem: dacă luăm o soluție optimă și eliminăm ultimul număr și ultima operație, ceea ce rămîne este optim?

Nu neapărat. Dacă ultima operație este o adunare, vom avea o subproblemă optimă, dar dacă este o înmulțire, nu.

Ce facem? Observăm că optimalitatea se păstrează la adunări, nu și la înmulțiri. Deci putem spune că, dacă MAX[i][j] este optim și are m înmulțiri în coadă, atunci și MAX[i-m-1][j-m] este optim, el fiind format din suma produselor anterioare, care dacă nu ar fi optimă am putea construi o sumă mai mare în MAX[i][j].

Astfel, formula de recurență este:

Răspunsul la cerință va fi: MAX[N][K].

Ce complexitate are această soluție?

Ea este O(N·K2). Înlocuind vom obține circa 2430 operații, un număr incredibil de mic. Probabil că mai mult va dura citirea celor 30 de numere.

Memoria folosită este cea a matricei de dimensiune N x K, deci O(N·K), din nou neglijabilă.

Exemplu

Iată exemplul din enunț calculat conform formulei de mai sus.

Fie numerele de la intrare:

Indice 0 1 2 3 4 5
Valoare 2 0 3 -1 7 -4

Calculul expresiilor maxime, pe linii, de la stînga la dreapta:

Înmulțiri
0 1 2 3
N
u
m
e
r
e
0 2
1 2 0
2 5 3 0
3 4 2 2 0
4 11 9 9 7
5 7 5 33 86

Program

Iată o soluție bazată pe ideile de mai sus (37 de linii de cod efectiv):

#include <stdio.h>

int nr[30], // nr[i] = numarul i, i = 0, 1, ..., n-1
  minim[30][10], // minim[i][j] = expresia de valoare minima care se
                 // poate forma din numerele nr[0..i] folosind i operatii 
                 // din care j inmultiri
  maxim[30][10]; // similar cu minim, doar ca e maxim :)

int main() {
  FILE *fin, *fout;
  int n, k, op, mul, mulcoada, produscoada, min, max, curent, lim;

  fin = fopen( "optim.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  for ( op = 0; op < n; op++ )
    fscanf( fin, "%d", &nr[op] );
  fclose( fin );

  // initializare coloana diagonala
  // minim[i][i] = produsul numerelor nr[0] * nr[1] * ... * nr[i]
  minim[0][0] = maxim[0][0] = nr[0];
  for ( mul = 1; mul <= k; mul++ )
    minim[mul][mul] = maxim[mul][mul] = maxim[mul - 1][mul - 1] * nr[mul];
  /*
  calculam elementele strict sub diagonala principala dupa formula
  de recurenta:

  minim[op][mul] = min( minim[op - 1 - mulcoada][mul - mulcoada +
                   + nr[op - mulcoada] * nr[op - mulcoada + 1] * ... * nr[op] )

  unde mulcoada variaza de la 0 la mul.
  Produsul numerelor este calculat incremental in produscoada.
  */
  for ( op = 1; op < n; op++ ) {
    lim = op < k + 1 ? op : k + 1;
    for ( mul = 0; mul < lim; mul++ ) {
      produscoada = nr[op];
      min = minim[op - 1][mul] + produscoada;
      max = maxim[op - 1][mul] + produscoada;
      for ( mulcoada = 1; mulcoada <= mul; mulcoada++ ) {
	produscoada *= nr[op - mulcoada];
	curent = minim[op - 1 - mulcoada][mul - mulcoada] + produscoada;
	if ( curent < min )
	  min = curent;
	curent = maxim[op - 1 - mulcoada][mul - mulcoada] + produscoada;
	if ( curent > max )
	  max = curent;
      }
      minim[op][mul] = min;
      maxim[op][mul] = max;
    }
  }

  fout = fopen( "optim.out", "w" );
  fprintf( fout, "%d %d\n", minim[n - 1][k], maxim[n - 1][k] );
  fclose( fout );

  return 0;
}

Joc6

Problema joc6 a fost dată la ONI 2011 baraj gimnaziu. Este o problemă tipică de programare dinamică.

Soluția comisiei

Iată ce spune comisia:

"Pentru fiecare jucător se determină secvenţele de bile cu valori consecutive. Acest lucru se poate realiza prin utilizarea unui vector caracteristic.

După determinarea secvenţelor, se selectează secvenţa de sumă maximă ce poate fi obţinută prin utilizarea bilelor speciale, în funcţie de numărul de bile speciale pe care le are jucătorul curent. Se determină maximul sumelor maxime şi jucătorul care are acest maxim."

Din păcate explicațiile sînt destul de vagi. Ce bănuiesc eu:

  • Vom face o listă de secvențe, păstrînd pentru fiecare secvență: (indice start, indice final, suma)
  • Vom încerca să cuplăm secvențe astfel:
    • Fie două secvențe consecutive dacă ele sînt despărțite de cel mult numărul de bile zero disponibile.
    • Fie trei secvențe consecutive dacă avem măcar două bile zero, iar secvențele sînt despărțite de fix un zero.

Desigur vom lua maximul sumelor.

Ce complexitate are această soluție?

Pentru detecția secvențelor avem nevoie de un vector de frecvență, deci O(n + p). Pentru parcurgerea secvențelor avem nevoie de O(p) pași. Deoarece avem k jucători complexitatea totală este O(k·(n + p).

Dar memoria? Din cauza vectorului de frecvență vom avea nevoie de O(n + p) memorie.

Este o soluție rezonabilă, poate nu foarte grea, dar care necesită creativitate și gîndire algoritmică.

Soluție cu programare dinamică

Această soluție este destul de evidentă. Din păcate ea nu necesită prea multă gîndire, ceea ce, după părerea mea, face această problemă să nu fie așa de bună pentru concurs. Totuși, fiind vorba despre baraj gimnaziu, nu este grav.

Putem defini problema de programare dinamică astfel:

S[b][i] = suma maximă ce începe cu bila i, ce se poate obține folosind b bile zero

Unde b poate fi 0, 1, sau 2 în problema noastră, dar nimic nu ne împiedică să îl mărim.

Demonstrația proprietății de optimalitate a subproblemelor este destul de ușoară, v-o las ca temă de gîndire.

Recurența este, iarăși, destul de clară:

  • Dacă bila i există la intrare, atunci o adăugăm la secvența anterioară ce începe cu bila i+1.
  • Dacă bila i nu există la intrare, atunci folosim o bilă zero. Vom avea deci aceeași valoare cu o secvență ce folosește mai puțin cu unu bile zero și care începe cu bila i+1.

Formula de recurență este:

Ce complexitate are această soluție?

Ea citește bilele și parcurge vectorul de frecvență de maxim trei ori, deci O(n + p).

Dar memoria? Din cauza vectorului de frecvență vom avea nevoie de O(n) memorie. Dacă vom calculăm matricea S[][] pe coloane vom avea nevoie de O(b) memorie, deoarece vom stoca doar o linie, dar O(b) este practic constant. Memorie totală necesară: O(n + b).

Observații:

  • Obținem un algoritm de complexitate similară ca timp și memorie.
  • Programul iese foarte scurt, circa 40 de linii efective, mulțumită programării dinamice.
  • Posibil să fie și ceva mai eficient, dar acest lucru nu contează prea mult deoarece timpul va fi dominat de citire.

Exemplu

Să presupunem că avem următoarele bile la intrare:

Bile 2 0 6 4 0

Atunci vom calcula tabelul următor:

Bile
1 2 3 4 5 6
0 1 0 1 0 1
Z
e
r
o
u
r
i
0 0 2 0 4 0 6
1 2 6 4 10 6 6
2 6 12 10 10 6 6

Maximul în acest tabel este 12, care este și răspunsul cerut.

Program

Deoarece rezolvarea este (aproape) liniară în numărul de elemente citite la intrare, iar intrarea poate avea circa 14MB este evident că va folosi dacă facem parsing.

Iată o implementare a ideilor de mai sus care calculează tabelul pe coloane, de la dreapta la stînga și de jos în sus, pentru a folosi mai puțină memorie (58 linii de cod efectiv, 38 de linii fără parsing):

#include <stdio.h>
#include <ctype.h>

#define MAXN 500000
#define BUFSIZE (128 * 1024)

char bile[MAXN + 3];
long long smax[4];
FILE *fin, *fout;
int rpos; char rbuf[BUFSIZE];

// initializare citire
static inline void initRead() {
  rpos = BUFSIZE - 1;
}

// citire caracter
static inline char readChar() {
  if ( !(rpos = (rpos + 1) & (BUFSIZE - 1)) )
    fread( rbuf, 1, BUFSIZE, fin );
  return rbuf[rpos];
}
 
// citire intreg
int readInt() { // citeste un intreg
  int ch, res = 0;

  while ( !isdigit( ch = readChar() ) );
  do
    res = 10 * res + ch - '0';
  while ( isdigit( ch = readChar() ) );

  return res;
}

int main() {
  int n, k, p, i, j, ki, jm;
  long long sm;

  fin = fopen( "joc6.in", "r" );
  initRead();
  n = readInt() + 2; // plus cele doua bile zero
  k = readInt();
  p = readInt();
  sm = jm = 0;
  for ( ki = 1; ki <= k; ki++ ) {
    for ( i = 0; i <= 3; i++ )
      smax[i] = 0;
    for ( i = 0; i <= n; i++ )
      bile[i] = 0;
    for ( j = 0; j < p; j++ )
      bile[readInt()]++; // incrementam pentru bilele zero

    // programare dinamica pentru determinarea secventei de lungime maxima
    // aflam lungimile/sumele maximale nefolosind nici un '0', apoi un '0',
    // apoi doi '0' daca ii avem la dispozitie
    // calculam matricea pe coloane pentru a folosi mai putina memorie
    bile[0]++;
    for ( i = n; i > 0; i-- )
      if ( bile[i] ) {
        for ( j = bile[0]; j > 0; j-- )
	  if ( (smax[j] += i) > sm ) {
	    sm = smax[j];
	    jm = ki;
	  }
      } else
        for ( j = bile[0]; j > 0; j-- )
          smax[j] = smax[j - 1];
  }
  fclose( fin );

  fout = fopen( "joc6.out", "w" );
  fprintf( fout, "%d %lld\n", jm, sm );
  fclose( fout );
  return 0;
}

Concurs - rezolvări

Noxa

Problema noxa a fost dată la timus.ru.

Soluție

Să observăm că:

  • Dacă nu am avea diagonale (parcuri) drumul minim ar fi exact M + N (distanța Manhattan).
  • O diagonală este totdeauna preferabilă și scurtează drumul cu o cantitate fixă.

De aici rezultă că dorim un drum cu număr maxim de diagonale.

De aici lucrurile încep să semene cu problema drept. O diagonală D2 poate urma altei diagonale D1 dacă D2 se află în dreptunghiul ce pornește din colțul D1 și se termină în destinație (jos-dreapta).

Astfel, vom sorta diagonalele după linii, iar în cadrul liniilor egale în ordine inversă a coloanelor. Apoi vom căuta subsecvența crescătoare de lungime maximă în cadrul coloanelor. Acela este numărul maxim de diagonale.

Mai departe avem un calcul matematic relativ simplu pentru a determina distanța: fiecare diagonală scade două laturi de pătrat elementar și adună lungimea ei, anume sqrt(20000).

Iată un program posibil (35 de linii de cod efectiv):

#include <stdio.h>
#include <math.h>

#define MAXK 1000

short diagl[MAXK + 1], diagc[MAXK + 1];

int main() {
  FILE *fin, *fout;
  int n, m, i, j, k, l, c, max;

  fin = fopen( "noxa.in", "r" );
  fscanf( fin, "%d%d%d", &m, &n, &k ); // x, y, numarul de diagonale
  // citire perechi (l, c) si sortare prin insertie cu santinela la poz 0
  // pentru linii egale sortam coloanele descrescator
  for ( i = 1; i <= k; i++ ) {
    fscanf( fin, "%d%d", &l, &c ); // x, y, numarul de diagonale
    j = i;
    while ( (diagl[j - 1] > l || (diagl[j - 1] == l && diagc[j - 1] < c)) ) {
      diagl[j] = diagl[j - 1];
      diagc[j] = diagc[j - 1];
      j--;
    }
    diagl[j] = l;
    diagc[j] = c;
  }
  fclose( fin );

  // cautam cea mai lunga secventa crescatoare in diagc[]
  // diagl[i] = lungimea celei mai lungi secvente care se termina la pozitia i
  max = 0;
  for ( i = 1; i <= k; i++ ) {
    l = 0;
    for ( j = 0; j < i; j++ )
      if ( diagc[j] < diagc[i] && diagl[j] > l )
        l = diagl[j];
    if ( (diagl[i] = l + 1) > max )
      max = l + 1;
  }

  fout = fopen( "noxa.out", "w" );
  fprintf( fout, "%d\n", 100 * (m + n - 2 * max) + (int)(max * sqrt(20000)) );
  fclose( fout );

  return 0;
}

Ce complexitate are acest algoritm?

Desigur el este O(K2) ca timp și O(K) memorie, mai exact circa 4KB.

Din acest motiv nu are sens să ne străduim să scriem o sortare mai bună de O(K2), drept care am folosit o sortare prin inserție chiar la citirea coordonatelor parcurilor.

Algoritmul poate fi redus la timp O(K log K), precum am mai menționat. În acest caz ar avea sens să folosim o sortare rapidă.

Soluții alternative

Ce s-ar întîmpla dacă K ar fi mare, gen 8 sau 10 milioane, dar M și N rămîn maxim 10000? Avem un algoritm mai rapid decît O(K log K)?

Vă las această întrebare ca temă de gîndire.

Secvență dominată

Problema secvență dominată a fost dată la codeforces.

Soluție

La prima vedere problema pare foarte grea. Încercările clasice de rezolvare nu par să funcționeze:

  • Forța brută, calculul tuturor subvectorilor, este ineficientă și depășește timpul, deoarece avem O(N2) subvectori distincți.
  • Încercările cu element majoritar nu funcționează, deoarece elementul dominant nu apare neapărat de jumătate plus unu ori.
  • Ideile de soluții bazate pe vectori de frecvență nu par, nici ele, să ducă nicăieri.

Este interesant că la această problemă dopajul (cunoștințe avansate căpătate fără a avea o înțelegere bună) nu pare să ajute. Aceasta o face o problemă bună de concurs.

Vom aplica principiile:

  • Cînd introducem o ordine lucrurile pot deveni mai ușoare.
  • Matematica ajută.

Să studiem cîteva secvențe dominate minimale:

  • Este [4 5 2 4 5 3 4 2] o secvență dominată? Da, ea este dominată de elementul 4.
  • Este secvența una minimală? Evident că nu, putem elimina ultimul element, care nu este 4.

Ce deducem de aici?

Observație: o secvență dominată minimală începe și se termină cu elementul dominant.

Mai departe, să eliminăm ultimul element și să studiem noua secvență:

  • Este [4 5 2 4 5 3 4] o secvență dominată minimală? Nu! Ea conține secvențe dominate mai mici: [4 5 2 4], [4 5 3 4] și [5 2 4 5].
  • De ce sînt ele posibile, în interiorul secvenței noastre? Pare că ele sînt posibile deoarece avem elemente egale în interior.
  • Oare o secvență dominată minimală nu conține decît elemente distincte în interiorul ei?

Aici intervine matematica. Nu voi detalia demonstrația. Ideea este așa: presupunem că avem o secvență dominată de lungime minimă. Primul și ultimul element sînt elementul dominat. Să presupunem că în interior nu ar avea elemente distincte. Atunci putem lua perechea de elementele identice cele mai apropiate. Secvența care începe și se termină cu elementele perechii va avea elemente distincte în interior, altfel înseamnă că nu le-am ales pe cele mai apropiate. Drept care această secvență este dominată și mai mică decît cea originală.

Avem și un caz în care în interior nu avem decît elementul dominat care se repetă. Și atunci este clar că putem alege o secvență mai mică folosind un capăt și elementul din interior.

Ce avem, deci, de calculat? Vom calcula secvența dominată de lungime minimă doar între acele secvențe care încep și se termină cu același element, iar în interior acel element nu apare.

Dar această problemă este banală dacă folosim un vector de frecvență în care memorăm pentru fiecare număr de la intrare indicele ultimei sale apariții. Cînd citim un număr la intrare vom ști indicele său și indicele apariției anterioare, deci vom putea calcula lungimea secvenței, pe care o vom compara cu minimul global.

Acest algoritm este O(N + MAXV) per test, circa 1.2 milioane operatii. Avînd 10 teste, totalul operațiilor va fi de 12 milioane, ce ar trebui să se încadreze lejer în timpul de 0.9s.

Cu toate acestea să nu uităm un lucru important: din nou avem situația în care prelucrarea este aproximativ O(1) per element, iar datele de intrare pot fi mari, circa 14MB. Se impune deci un parsing, preferabil cît mai eficient.

Iată o soluție bazată pe aceste idei (45 de linii de cod efectiv, din care 22 program fără partea de parsing):

#include <stdio.h>
#include <ctype.h>

#define BUFSIZE (128 * 1024)
#define MAXE 1000000

FILE *fin, *fout;
int ult[MAXE + 1];
int rpos; char rbuf[BUFSIZE];

// initializare citire
static inline void initRead() {
  rpos = BUFSIZE - 1;
}

// citire caracter
static inline char readChar() {
  if ( !(rpos = (rpos + 1) & (BUFSIZE - 1)) )
    fread( rbuf, 1, BUFSIZE, fin );
  return rbuf[rpos];
}
 
// citire intreg fara semn
int readInt() {
  int ch, res = 0;

  while ( !isdigit( ch = readChar() ) );
  do
    res = 10 * res + ch - '0';
  while ( isdigit( ch = readChar() ) );

  return res;
}

int main() {
  int n, t, i, e, min;

  fin = fopen( "secvdom.in", "r" );
  fout = fopen( "secvdom.out", "w" );
  initRead();

  t = readInt();
  while ( t-- ) {
    for ( e = 1; e <= MAXE; e++ ) // resetam vectorul de frecventa la zero
      ult[e] = 0;

    min = n = readInt();
    for ( i = 1; i <= n; i++ ) {
      e = readInt();
      if ( ult[e] != 0 && i - ult[e] < min )
        min = i - ult[e];
      ult[e] = i;
    }
    fprintf( fout, "%d\n", min == n ? -1 : min + 1 );
  }

  fclose( fin );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Precum am menționat, este O(T·(N + MAXV)) ca timp.

Memoria necesară este cea a vectorului de frecvență adică O(MAXV), mai exact circa 4MB.

Steaguri

Problema steaguri a fost dată la timus.ru. Este o problemă tipică de probleme suprapuse.

Soluție

În problemele de acest gen vom genera secvențe de subprobleme de ordinul K. Suma acestor subprobleme va fi, în general, răspunsul căutat.

De exemplu, aici putem defini următoarele subprobleme:

  • A(K) = numărul de benzi cu K dungi care se termină în alb.
  • R(K) = numărul de benzi cu K dungi care se termină în roșu.
  • AA(K) = numărul de benzi cu K dungi care se termină în alb și apoi albastru.
  • RA(K) = numărul de benzi cu K dungi care se termină în roșu și apoi albastru.

Avem următoarele reguli simple, ușor de dedus:

  • După alb putem pune roșu sau albastru, deci A(K) se va aduna la R(K+1) și la AA(K+1)
  • După roșu putem pune alb sau albastru, deci R(K) se va aduna la A(K+1) și la RA(K+1)
  • După alb-albastru putem pune roșu, deci AA(K) se va aduna la R(K+1).
  • După roșu-albastru putem pune alb, deci RA(K) se va aduna la A(K+1).

Rezultă ecuațiile:

  • A(K) = R(K-1) + RA(K-1)
  • R(K) = A(K-1) + AA(K-1)
  • AA(K) = A(K-1)
  • RA(K) = R(K-1)

Răspunsul problemei noastre este:

  • S(N) = A(N) + R(N)

Avem suficiente date să ne apucăm de implementare și programul nu va ieși prea complicat. În fapt, la multe din probleme ar fi în regulă ca la acest pas să implementăm.

Însă aici observăm o simetrie. Este clar că lucrurile se pot simplifica. Să încercăm să scăpăm de recurențele simple, cele fără adunări:

  • A(K) = R(K-1) + RA(K-1) = R(K-1) + R(K-2)
  • R(K) = A(K-1) + AA(K-1) = A(K-1) + A(K-2)

Răspunsul căutat este:

  • S(N) = A(N) + R(N)

Este destul de clar că, prin simetrie, A(K) = R(K). Deci putem scrie:

  • A(K) = A(K-1) + A(K-2)

Răspunsul căutat este:

  • S(N) = 2·A(N)

Unde A(N) = F(N) este al N-lea termen din șirul lui Fibonacci.

Acum, dacă ne apucăm de implementare, lucrurile stau mult mai simplu, nu? Da, dar să nu uităm că N este mare, maxim 10000. Drept care vom avea nevoie să lucrăm cu numere mari. Va trebui să implementăm o adunare și o înmulțire. Putem oare mai simplu?

Desigur. Dacă în loc să pornim cu primele numere din șir 1 și 1, pornim cu dublul lor, 2 și 2, vom calcula direct un șir al lui Fibonacci care este dublul originalului. Astfel vom scăpa de înmulțirea cu 2.

Iată un program posibil (36 de linii de cod efectiv):

#include <stdio.h>

#define MAXCF 10000

char fib[MAXCF][2] = { { 2, 2 } };
int ncf[2] = { 1, 1 };

// aduna fib[1-f] la fib[f]
void aduna( int f ) {
  int i, t = 0;

  for ( i = 0; i < ncf[1 - f]; i++ ) {
    fib[i][f] += t + fib[i][1 - f];
    t = 0;
    if ( fib[i][f] > 9 ) {
      fib[i][f] -= 10;
      t = 1;
    }
  }
  ncf[f] = i;
  if ( t > 0 ) {
    fib[i][f] = 1;
    ncf[f]++;
  }
}

int main() {
  FILE *fin, *fout;
  int n, i, f;

  fin = fopen( "steaguri.in", "r" );
  fscanf( fin, "%d", &n );
  fclose( fin );

  f = 0;
  for ( n -= 2; n > 0; n-- )
    aduna( f = 1 - f );
  
  fout = fopen( "steaguri.out", "w" );
  for ( i = ncf[f] - 1; i >= 0; i-- )
    fputc( fib[i][f] + '0', fout );
  fputc( '\n', fout );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Vom avea de efectuat N-1 adunări de numere mari. Precum poate ne aducem aminte, F(N) este O(aN) unde a este un număr irațional. Drept care numărul său de cifre este logaritm din acest număr, adică O(N). Vom efectua în total O(N2) calcule, acesta fiind și complexitatea în timp a algoritmului.

Memoria necesară este cea a stocării a două numere mari, deci O(N), sau, mai exact, circa 20000 octeti.

Rezolvări aici [1]

Tema 27 - rezolvări

Raze

Problema raze a fost dată la ONI 2010 clasa a 8a.

Problema are mai multe variante de abordare.

Soluție forță brută

O posibilitate ar fi să parcurgem matricea și, pentru fiecare element, să parcurgem cele patru diagonale pînă la primul obstacol sau pînă la margine. Numărul de margini atinse este numărul de obiective ce pot fi distruse din acel element. Desigur, vom calcula maximul dintre aceste valori.

Ce complexitate are această soluție?

Parcurgerea matricei este O(N·M). Pentru fiecare element parcurgem diagonalele sale, adică maxim O(min(N, M)) elemente. Timpul total va fi O(N·M·min(N, M)). Înlocuind, vom avea circa 1353 operații ce se înmulțesc cu doi (suma diagonalelor), adica circa 5 milioane de operații per test. Avînd maxim 80 de teste algoritmul forță brută efectuează 400 milioane de operații și nu se încadrează în timp (0.6s).

Memoria folosită este O(N·M) pentru stocarea matricei de la intrare.

Soluție cu parcurgere diagonale

Forța brută recalculează același lucru de multe ori: pînă unde pot ajunge dacă pornesc dintr-un punct. Putem modifica forța brută de mai sus să nu mai repete calcule: vom calcula invers, pînă unde putem ajunge pornind dintr-un punct de pe margine.

Astfel, pentru fiecare punct de pe margine (O(N + M) astfel de puncte) vom parcurge cele două diagonale pe care le poate "vedea". Vom aduna unu într-o matrice specială, de punctaj, pentru fiecare astfel de element. Desigur că ne vom opri la un obstacol.

La final vom căuta punctajele maxime.

Ce complexitate are această soluție?

Deoarece parcurgerea diagonalelor este O(min(N, M)) vom avea o complexitate totală de O((N + M)·min(N, M)). Înlocuind și ținînd cont de faptul că avem un factor de 2 atît la elementele de pe margine cît și la diagonale, obținem 135·4 puncte de margine înmulțit cu 135·2 puncte pe diagonale, circa 145800, ori 80 de teste circa 12 milioane de calcule, ce se vor încadra lejer în timp.

Dar memoria? Vom avea nevoie de matricea originală de obstacole și de o matrice de punctaj, în total O(N·M). Mai exact, deoarece ambele matrice sînt de tip caracter (întregi mici), vom avea nevoie de 135·135·2 = 36450 octeți.

Observații de implementare:

  • Această soluție este O(1) per element citit la intrare.
  • La intrare vom citi circa 135·135·80 elemente zero sau unu, a cîte două caractere fiecare (cu tot cu separator), în total aproape 3MB de date.
  • Este clar că se impune să facem parsing.

Soluție cu parcurgere matrice

Putem privi problema și invers: să calculăm patru matrice de vizibilitate. Una din matrice ne va spune pentru fiecare element dacă vede sau nu marginea din diagonala sus-stînga, altă matrice pentru diagonala sus-dreapta și tot așa.

Aceste matrice se pot calcula incremental printr-o simplă parcurgere, uitîndu-ne la elementul anterior pe diagonală. Fiecare element se calculează în timp constant.

La final vom calcula pentru fiecare element suma în cele patru matrice "suprapuse". Această sumă este numărul de obiective căutat. Vom căuta elementele de sumă maximă.

Complexitatea acestei soluții este aceeași ca timp și memorie. Ea folosește ceva mai multă memorie, deoarece are nevoie de patru matrice în loc de una singură, circa 90KB.

Iată un program bazat pe această idee (55 linii de cod efectiv):

#include <stdio.h>

#define MAXD 135

char harta[MAXD][MAXD];
char dir[4][MAXD][MAXD]; // dinspre nw, ne, sw, se

int main() {
  FILE *fin, *fout;
  int T, m, n, i, j, l, c, suma, max, nrap, aux;

  fin = fopen( "raze.in", "r" );
  fout = fopen( "raze.out", "w" );
  fscanf( fin, "%d", &T );
  for ( i = 0; i < T; i++ ) {
    fscanf( fin, "%d%d", &m, &n );
    for ( l = 0; l < m; l++ )
      for ( c = 0; c < n; c++ ) {
        fscanf( fin, "%d", &aux );
        harta[l][c] = aux;
      }

    // bordam matricele cu 1
    for ( j = 0; j < 4; j++ ) {
      for ( l = 0; l < m; l++ )
        dir[j][l][0] = dir[j][l][n-1] = 1;
      for ( c = 0; c < n; c++ )
        dir[j][0][c] = dir[j][m-1][c] = 1;
    }

    // scanam diagonalele de sus in jos
    for ( l = 1; l < m-1; l++ )
      for ( c = 1; c < n-1; c++ )
        if ( harta[l][c] ) // avem obstacol, punctele curente sint zero
          dir[0][l][c] = dir[1][l][c] = 0;
        else { // este liber, completam cu punctul din-nainte
          dir[0][l][c] = dir[0][l-1][c-1];
          dir[1][l][c] = dir[1][l-1][c+1];
        }

    // scanam diagonalele de jos in sus
    for ( l = m-2; l > 0; l-- )
      for ( c = n-2; c > 0; c-- )
        if ( harta[l][c] ) // avem obstacol, punctele curente sint zero
          dir[2][l][c] = dir[3][l][c] = 0;
        else { // este liber, completam cu punctul din-nainte
          dir[2][l][c] = dir[2][l+1][c-1];
          dir[3][l][c] = dir[3][l+1][c+1];
        }

    // insumam cele patru matrice si gasim maximul + de cite ori apare
    max = 0;
    for ( l = 1; l < m-1; l++ )
      for ( c = 1; c < n-1; c++ ) {
        suma = dir[0][l][c] + dir[1][l][c] + dir[2][l][c] + dir[3][l][c];
        if ( suma > max ) {
          max = suma;
          nrap = 1;
        } else if ( suma == max )
          nrap++;
      }

    fprintf( fout, "%d %d\n", max, nrap ); // tipareste maximul si nr lui de ap
  }
  fclose( fin );
  fclose( fout );

  return 0;
}

Soluție fără stocarea matricei

Soluția este optimă din punct de vedere timp, deoarece execută O(1) calcule per element citit la intrare. Este ea optimă și ca memorie? Putem, oare, să nu stocăm elementele de la intrare?

Suita

Problema suita a fost dată la codechef.

Soluție forță brută

Putem calcula pentru fiecare subvector de K elemente minimul și maximul. Deoarece știm că elementele sînt distincte pentru ca subvectorul să fie suită trebuie ca maxim - minim = K - 1.

Complexitatea acestei soluții este O(N·K). Ea nu se va încadra în timp deoarece efectuează maxim 400000·35000 de calcule, adică 14 miliarde.

Soluție optimă

Deoarece avem nevoie să calculăm minimul și maximul în fiecare subvector de K elemente este destul de ușor de observat că putem folosi optimul în fereastră glisantă. Vom calcula atît minimul cît și maximul și vom răspunde la întrebarea "este suită" în timp amortizat constant per subvector.

Deoarece efectuăm O(1) calcule per element citit și citim circa 3MB la intrare este clar că va ajuta să facem parsing.

Iată o soluție posibilă (62 de linii de cod efectiv, 34 fără parsing - doar main() și funcții aferente):

#include <stdio.h>
#include <ctype.h>

#define MAXK 35000
#define MAXDEQ 65536
#define BUFSIZE (128 * 1024)

int vh[MAXDEQ]; // vectorul de inaltimi
int deqmax[MAXDEQ]; // coada de maxime descrescatoare
int pmax, umax; // primul indice coada, respectiv primul indice in afara cozii
int deqmin[MAXDEQ]; // coada de minime descrescatoare
int pmin, umin; // primul indice coada, respectiv primul indice in afara cozii
FILE *fin, *fout;
int rpos; char rbuf[BUFSIZE];

// initializare citire
static inline void initRead() {
  rpos = BUFSIZE - 1;
}

// citire caracter
static inline char readChar() {
  if ( !(rpos = (rpos + 1) & (BUFSIZE - 1)) )
    fread( rbuf, 1, BUFSIZE, fin );
  return rbuf[rpos];
}
 
// citire intreg
int readInt() {
  int ch, res = 0;

  while ( !isdigit( ch = readChar() ) );
  do
    res = 10 * res + ch - '0';
  while ( isdigit( ch = readChar() ) );

  return res;
}

// procesare inaltime - adaugare in cele doua deq - maxime si minime
void enQ( int h ) {
  // eliminam din deqmin elementele mai mari
  while ( umin != pmin && deqmin[umin - 1] > h )
    umin = (umin - 1 + MAXDEQ) % MAXDEQ;
  // adaugam h in deqmin
  deqmin[umin] = h;
  umin = (umin + 1) % MAXDEQ;

  // eliminam din deqmax elementele mai mici
  while ( umax != pmax && deqmax[umax - 1] < h )
    umax = (umax - 1 + MAXDEQ) % MAXDEQ;
  // adaugam h in deqmax
  deqmax[umax] = h;
  umax = (umax + 1) % MAXDEQ;
}

int main() {
  int n, k, i, p;

  fin = fopen( "suita.in", "r" );
  initRead();
  n = readInt();
  k = readInt();
  
  for ( i = 0; i < k; i++ ) // umplem cozile duble cu primele k elemente
    enQ( vh[i] = readInt() );

  p = deqmax[pmax] - deqmin[pmin] == k - 1; // fereastra este buna de suita?

  // parcurgem inaltimile folosind o fereastra glisanta de k elemente
  for ( i = k; i < n; i++ ) {
    enQ ( vh[i % MAXDEQ] = readInt() );

    if ( vh[(i - k) % MAXDEQ] == deqmin[pmin] ) // maximul iese din fereastra?
      pmin = (pmin + 1) % MAXDEQ; // atunci il eliminam
    if ( vh[(i - k) % MAXDEQ] == deqmax[pmax] ) // maximul iese din fereastra?
      pmax = (pmax + 1) % MAXDEQ; // atunci il eliminam

    if ( deqmax[pmax] - deqmin[pmin] == k - 1 )
      p++;
  }
  fclose( fin );
  
  fout = fopen( "suita.out", "w" );
  fprintf( fout, "%d\n", p );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Ea este O(N) ca timp și O(K) memorie. Un program bine scris va folosi două cozi duble pentru minim și maxim și un vector circular, toate de dimensiune K (rotunjit la următoarea putere a lui 2). Total memorie: 768KB.

Soluție brută optimizată

La olimpiadă nu ne vine totdeauna ideea de soluție optimă. Ce facem în acest caz? Ne gîndim la soluții suboptimale, preferabil mai bune ca forța brută.

Aici avem o soluție care, pe cazuri medii, va fi foarte rapidă.

Idee: să folosim un vector de frecvență al subvectorului curent.

Observații:

  • Vectorul de frecvență se poate menține în O(1) per deplasare a ferestrei - deci gratis.
  • Minimul din fereastră este indicele primului 1 din vector.
  • Similar, maximul din fereastră este indicele ultimului 1 din vector.
  • Pe teste aleatoare minimul și maximul nu vor varia prea des.
  • Recalcularea minimului cînd apare un element mai mic este O(1) (similar pentru maxim)
  • Recalcularea minimului atunci cînd minimul iese din fereastră se poate face deplasîndu-ne în sus pînă la primul element 1 (similar pentru maxim, în jos).

Programul obținut cu aceste idei va trece foarte multe teste, dacă testele nu sînt făcute cu grijă, luînd în calcul o astfel de idee.

Rezolvări aici [2]

Lecție - discuții probleme OJI

Foto1

Problema foto1 a fost dată la OJI 2020 clasa a 7a. Este o problemă directă, relativ simplă, poate mai curînd de clasa a 6a.

Soluție forță brută

Vom discuta doar cerința doi, deoarece cerința unu este banală, de introducere în clasa a șasea.

Partea mai grea a problemei este înțelegerea enunțului. Anume:

  • Fulgerele sînt continue și merg de sus în jos.
  • Fulgerele sînt disjuncte. Ele nu se pot atinge nici măcar pe diagonală.
  • Fulgerele nu se pot despărți, ele sînt liniare.

Drept pentru care o soluție forță brută este următoarea:

Parcurgem matricea M pe linii și pe coloane, natural. Pentru fiecare element M[l][c]:

    Dacă M[l][c] este 1 și elementele de deasupra lui sînt 0 (M[l-1][c-1], M[l-1][c], M[l-1][c+1])

        Adaugă 1 la numărul de fulgere.

        Parcurge în jos acel fulger pentru a îi afla lungimea.

Nu detaliez parcurgerea fulgerului, ea se deplasează în jos pe acel element care este 1, adunînd 1 la lungime.

Ce complexitate are această soluție?

Parcurgerea matricei este O(N·M). Parcurgerea unui fulger este O(N) și putem avea O(M) fulgere. Rezultă o complexitate de totală de O(N·M) care este și optimă, deoarece trebuie să citim matricea.

Dar memoria folosită? Ea este evident O(N·M) deoarece vom memora matricea. Mai exact, dacă elementele matricei sînt de tip caracter, memoria necesară este 10000 octeți, adică foarte puțin.

Simplificare

Ca idee de simplificare a implementării forței brute, putem "reseta" elementele unui fulger, pe măsură ce îl parcurgem. Astfel, testul de început de fulger devine mai simplu, dacă elementul curent M[l][c] == 1.

Soluție cu (și) mai puțină memorie

Dacă dimensiunile matricei ar fi ceva mai mari ne-am putea pune problema unei soluții care să nu memoreze matricea. Putem memora doar o linie din matrice. Vom parcurge matricea și, pentru fiecare element 1, ne întrebăm dacă este un început de fulger verificînd elementele din linia de mai sus. Putem, de asemenea, memora lungimile în acea linie, nu doar 0 sau 1.

Iată un algoritm posibil:

Citim matricea M pe linii și pe coloane, natural. Pentru fiecare linie l:

    Citim linia. Pentru fiecare coloană c citim elementul E și:

    Dacă E este 1

        Daca elementele de deasupra lui sînt 0 (L[c-1], L[c], L[c+1] - dar atenție, la L[c-1], ne trebuie valoarea veche)

            Adaugă unu la numărul de fulgere.

            L[c] primește 1 (lungimea actuală a fulgerului.

        Altfel înseamnă că doar un element din cele trei este diferit de zero, un fulger se continuă:

            L[c] primește 1 + L[i] (unde i poate fi c-1, c sau c+1)

        Dacă L[c] depășește lungimea maximă a unui fulger, reține valoarea

     Altfel

        L[c] = 0

Acest algoritm are aceeași complexitate în timp ca cel anterior, dar folosește doar O(M) memorie, adică circa 100 octeti (deoarece elementele matricei pot fi de tip char, lungimile nedepășind 100).

Considerente de implementare

Algoritmul de mai sus se poate implementa mai ușor dacă observăm anumite lucruri:

  • Nu avem nevoie să menținem două linii din matrice. Putem să memorăm valoarea veche din L[c-1].
  • Valoarea de calculat L[c] nu are nevoie de teste (condiții). Ea este suma celor patru valori

(trei deasupra plus elementul citit) înmulțită cu elementul citit.

O implementare bună n-ar trebui să depășească 35 de linii efective de cod.

Wind

Problema wind a fost dată la OJI 2020 clasa a 7a. Este o problemă medie spre ușoară ca dificultate, partea cea mai grea fiind ordinea și disciplina în rezolvare, algoritmul nepunînd probleme (sper).

Comentariu: v-ați gîndit de ce problema se cheamă wind, un titlu în engleză?

Indiciu: gîndiți-vă care ar fi fost alternativa și de ce nu e preferabilă :)

Soluție

Vom discuta doar despre cerința 2, deoarece punctul unu cere găsirea numărului de divizori ai unui număr, problemă banală de clasa a cincea.

Problema cere găsirea unei împărțiri a unui vector de elemente pozitive și negative în subvectori adiacenți de lungime egală, care să minimizeze diferența între cea mai mare sumă a unui subvector și cea mai mică sumă.

Observații:

  • Putem calcula valoarea de minimizat într-o parcurgere a vectorului, deci în O(N).
  • Nu vom lua în calcul decît parcurgeri în care putem crea subvectori egali - deci pentru divizorii lui N.
  • N are maxim 5 cifre.
  • Numărul maxim de de divizori ai unui număr cu 5 cifre este 128, conform numărul maxim de divizori ai numerelor de n cifre.
  • Timpul este 0.3s

De aici rezultă că o forță brută, care pentru fiecare divizor calculează diferența, se va încadra în timp, ea efectuînd circa 128·100000 = 12.8 milioane de operații.

Problema constă, precum spuneam, în implementare, algoritmul fiind forță brută. La ce trebuie să fim atenți?

  • La enunț! Nu este imediat clar că trebuie să afișăm cel mai mare indice al primului element din subvectorul de sumă maximă.
  • Să nu creăm cazuri particulare.
  • Să scriem cît mai clar și mai simplu codul, deoarece avem multe detalii de care trebuie să ținem cont.
  • Să facem parsing! Vom citi 100000 de numere de 9 cifre, plus un separator, deci circa 1MB. Putem cîștiga 0.1s doar din o citire atentă. Atunci cînd avem 0.3s cu totul, devine semnificativ. La olimpiadă aș implementa parsing-ul simplu, cu fgetc(). Nu aș risca parsing-ul cel mai eficient, cu fread(), dar dacă vă simțiți confortabil, de ce nu?

O implementare eficientă, cu parsing simplu, nu ar trebui să depășească 70 de linii de cod efectiv.

Ce complexitate are această soluție?

Precum am discutat, timpul va fi O(d(N)·N), unde d(N) este numărul de divizori ai lui N, în cazul nostru maxim 128.

Memoria folosită este cea necesară pentru a stoca valorile din vector, adică O(N), sau, mai exact, 400KB, mult mai puțină decît cea acordată, de 16MB.

Discuție probleme propuse de voi

În măsura în care vom avea timp vom discuta despre problemele:

  • monede dată la ONI 2014 baraj gimnaziu
  • ssk dată la ONI 2014 baraj gimnaziu

Tema

Tema 28 clasa a 7a

  • foto1 dată la OJI 2020 clasa a 7a
  • wind dată la OJI 2020 clasa a 7a

Rezolvări aici [3]