Clasa a VI-a lecția 13 - 13 dec 2018

From Algopedia
Jump to: navigation, search

Comentarii concurs 6 decembrie

Concursul de dimineață

  • Felicitări lui Remus Rughiniș pentru cel mai bun punctaj! Felicitări pentru implementările corecte și cu punctaj din prima submisie. TLE-ul de la matrice spirală sînt cauzate de algoritm, nu de implementăre. Bravo!
  • Felicitări lui Mircea Rebengiuc pentru rezolvarea perfectă la a doua problemă, matrice spirală!
  • Felicitări lui Victor Nicola pentru rezolvarea aproape perfectă la matrice spirală. Motivul pentru care nu a luat 100p sînt depășirile de int.
  • Felicitări lui Badea, Cojocariu, Petcu pentru obținerea unui rezultat bun de concurs! Cele 150p ale lor sînt ceea ce mă aștept, minimal, de la voi toți. Ar fi fost și Voicu printre voi, dacă nu concura de acasă.
  • Felicitări lui Calotă, Dragomir, Ștefănescu pentru punctajul bun și pentru luptă. Voi trei sînteți fie noi la cerc, fie mai mici cu un an, iar rezultatul este demn de voi, bravo! Țineți-o tot așa.

Concursul de după-amiază

  • Felicitări cu brio lui Luca Ilie pentru punctajul aproape perfect, cel mai bun din ambele concursuri! Bravo!
  • Felicitări lui Dobre, Nicu, Teodorescu pentru o rezolvare aproape perfectă la matrice zebră!

Tema - rezolvări

Problema sumL (suma pe L-uri)

Problema sumL pare, la prima vedere, o problemă de parcurgere în matrice. Este ușor să calculăm elementele matricei conform regulii din enunț. Apoi putem parcurge matricea urmărind L-urile și însumînd elementele. Codul ar arăta cam așa:

  for ( l = n - 1; l >= 0; l-- ) {
    s = 0;
    for ( c = 0; c < n - l; c++ )
      s += a[l][c];
    for ( c = l + 1; c < n; c++ )
      s += a[c][n - l - 1];
    fprintf( fout, "%d ", s );
  }
  fprintf( fout, "\n" );

Care este problema cu această soluție? Memoria! Să calculăm memoria necesară: deoarece N este maxim 1000 matricea va avea un milion de elemente. Fiind de tip întreg vom avea nevoie de 4MB. Enunțul ne oferă doar 3MB. Testele problemei sînt de așa natură încît veți obține 80p cu această soluție. La clase mai mari punctarea va fi mai dură, probabil ați obține 30-40p.

Cum reducem memoria? Printr-un artificiu foarte des întîlnit: ne vom folosi de faptul că numărul de sume de calculat este mic, avem N sume. Putem, deci, să calculăm în paralel toate aceste sume. Cum? Vom genera elementele matricei și le vom distribui sumei corecte.

Observăm că, date fiind elementele liniei l:

  • Primele n - l elemente aparțin sumei n - l
  • Următoarele l elemente aparțin unor sume diferite, anume elementul din coloana c aparține sumei c

Iată o soluție posibilă:

#include <stdio.h>

#define MAXN 1000
#define MOD 1000000

int suma[MAXN];

int main() {
  FILE *fin, *fout;
  int n, p, l, c;

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

  for ( l = n - 1; l >= 0; l-- ) {
    for ( c = 0; c < l; c++ ) {
      suma[l] += p;
      p = (p * (long long)p + 1) % MOD;
    }
    for ( c = l; c < n; c++ ) {
      suma[c] += p;
      p = (p * (long long)p + 1) % MOD;
    }
  }

  fout = fopen( "suml.out", "w" );
  fprintf( fout, "%d", suma[0] );
  for ( l = 1; l < n; l++ )
    fprintf( fout, " %d", suma[l] );
  fprintf( fout, "\n" );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Este ușor de calculat că timpul este O(n2), iar memoria ocupată este O(n), adică aproximativ 4000 octeți.

Problema sumD (suma pe diagonale)

Problema sumD pare, la prima vedere, o problemă de parcurgere în matrice. Este ușor să calculăm elementele matricei conform regulii din enunț. Apoi putem parcurge matricea urmărind diagonalele și însumînd elementele. Codul ar arăta cam așa:

  for ( l = n - 1; l >= 0; l-- ) {
    s = 0;
    for ( c = 0; c < n - l; c++ )
      s += a[l + c][c];
    fprintf( fout, "%d ", s );
  }
  for ( c = 1; c < n; c++ ) {
    s = 0;
    for ( l = 0; l < n - c; l++ )
      s += a[l][c + l];
    fprintf( fout, "%d ", s );
  }
  fprintf( fout, "\n" );

Care este problema cu această soluție? Memoria! Să calculăm memoria necesară: deoarece N este maxim 1000 matricea va avea un milion de elemente. Fiind de tip întreg vom avea nevoie de 4MB. Enunțul ne oferă doar 3MB. Testele problemei sînt de așa natură încît veți obține 80p cu această soluție. La clase mai mari punctarea va fi mai dură, probabil ați obține 30-40p.

Cum reducem memoria? Printr-un artificiu foarte des întîlnit: ne vom folosi de faptul că numărul de sume de calculat este mic, avem 2·N-1 sume. Putem, deci, să calculăm în paralel toate aceste sume. Cum? Vom genera elementele matricei și le vom distribui sumei corecte.

Mai ținem minte de la curs că fiecare diagonală are ceva constant: diferența c-l este aceeași de-a lungul unei diagonale paralele cu diagonala principală. Mai mult, acea diferență este unică pentru fiecare diagonală. Ce valori putem avea? Înlocuind cu minimele și maximele lui l și c obținem ca valoare minimă -(n-1), iar ca valoare maximă n-1. Putem folosi aceste valori ca indici în vectorul de sume, cu condiția de a-i renumerota de la zero. Pentru aceasta vom aduna n-1.

În concluzie, elementul aflat pe linia l și coloana c va aparține sumei n-1 + c - l.

Iată o soluție posibilă:

#include <stdio.h>

#define MAXN 1000
#define MOD 1000000

int suma[2 * MAXN - 1];

int main() {
  FILE *fin, *fout;
  int n, p, l, c;

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

  for ( l = 0; l < n; l++ )
    for ( c = 0; c < n; c++ ) {
      suma[n - 1 + c - l] += p;
      p = (p * (long long)p + 1) % MOD;
    }

  fout = fopen( "sumd.out", "w" );
  fprintf( fout, "%d", suma[0] );
  for ( l = 1; l < 2 * n - 1; l++ )
    fprintf( fout, " %d", suma[l] );
  fprintf( fout, "\n" );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Este ușor de calculat că timpul este O(n2), iar memoria ocupată este O(n). Deoarece avem 2·N-1 elemente în vectorul de sume vom folosi aproximativ 8000 octeți.

Problema matsp (matrice spirală)

Problema matsp pare, la prima vedere, o problemă de parcurgere în matrice. Putem parcurge matricea în spirală, înscriind numerele de la 1 la n2 în căsuțele parcurse. Apoi, pentru prima cerință vom afișa matricea, iar pentru cea de-a doua cerință vom afișa elementul cerut, de la linia și coloana citite la intrare.

Codul ar arăta cam așa (similar cu problema medalion, punctul a):

  l = c = n / 2;
  a[l][c] = e = 1;
  for ( i = 1; i <= n / 2; i++ ) {
    l++;
    c++; // pornim de la (l+1, c+1)
    // latura din dreapta
    for ( j = 0; j < 2 * i; j++ ) {
      l--;
      e++;
      a[l][c] = e;
    }
    // latura de sus
    for ( j = 0; j < 2 * i; j++ ) {
      c--;
      e++;
      a[l][c] = e;
    }
    // latura din dreapta
    for ( j = 0; j < 2 * i; j++ ) {
      l++;
      e++;
      a[l][c] = e;
    }
    // latura de jos
    for ( j = 0; j < 2 * i; j++ ) {
      c++;
      e++;
      a[l][c] = e;
    }
  }

Să observăm un lucru: cele patru bucle for, care parcurg cele patru segmente ale unei spire, sînt aproape identice, diferind doar incrementarea sau decrementarea liniei sau coloanei. Pentru aceasta putem folosi același truc ca la problema medalion punctul a, pentru a factoriza codul. Vom obține:

  l = c = n / 2;
  a[l][c] = e = 1;
  for ( i = 1; i <= n / 2; i++ ) {
    l++;
    c++; // pornim de la (l+1, c+1)
    for ( dir = 0; dir < 4; dir++ )
      for ( j = 0; j < 2 * i; j++ ) {
        l = l + (dir + 1) % 2 * (dir - 1);
        c = c + dir % 2 * (dir - 2);
        e++;
        a[l][c] = e;
      }
  }

Această soluție funcționează bine pentru prima cerință. Care este problema cu această soluție la cerința doi? Memoria! Să calculăm memoria necesară: deoarece N este maxim un miliard matricea va avea un un miliard de miliarde de elemente, ceea ce este exclus să ne încapă în memorie. Chiar și dacă ar încăpea în memorie, timpul de calcul ar fi prea mare. Testele problemei sînt de așa natură încît veți obține 65p cu această soluție, 50p pentru prima cerință și 15p (din cele 50p) pentru a doua cerință. La clase mai mari punctarea va fi mai dură, probabil ați obține 30p cu această soluție, deoarece prima cerință s-ar puncta 20p, iar a la a doua ați lua 10p din 80p.

Care este soluția, atunci? Din nou, matematica ne sare în ajutor. Date o linie și o coloană putem oare să calculăm elementul care se află la acea poziție? Este o problemă asemănătoare cu problema medalion, deci răspunsul este da.

Exemplu de matrice spirală

Date N, L și C ne propunem să aflăm valoarea elementului din matrice de la linia L și coloana C.

Observație 1: numerele fiind dispuse în pătrate concentrice, începînd din centrul matricei, elementul de la poziția (L C) va fi situat pe un astfel de pătrat. Pentru a afla ușor pe al cîtelea pătrat de la centru ne aflăm este mai ușor să numerotăm liniile și coloanele de la centrul matricei. Astfel, elementul din centru va avea coordonate (0 0), cel de sub el (1 0), cel din dreapta lui (0 1). Ce se întîmplă cu elementele de deasupra, sau la stînga? Ele vor avea coordonate negative! Nimic care să ne sperie, nu-i așa? :-)

Date L și C avem nevoie să le convertim la noile coordonate. Pentru aceasta vom scădea coordonatele centrului, care sînt (N/2 N/2), deoarece N este impar. De exemplu, coordonatele elementului 47 (galben) sînt (3 1), ale elementului 37 (roșu) sînt (-3 -3), ale lui 36 (verde) sînt (-3 -2) și ale lui 27 (albastru) sînt (1 3).

Observație 2: dat un element la coordonate (L C) față de centru, el se află pe pătratul cu numărul

max(|L|, |C|)

unde |X| este valoarea absolută a lui X, care ignoră semnul lui X. În această notație numerotăm pătratele de la zero, ca niște buni informaticieni :-)

Observație 3: pătratul numărul X are latură X + 1. Destul de evident, nu?

Observație 4: pătratul de latură lat conține numerele de la (lat-1)2+1 la lat2. Iarăși, destul de clar.

Cum vom proceda? Vom calcula pătratul P pe care se află elementul, latura acelui pătrat lat, precum și ultimul număr din acel pătrat, U. Apoi:

  • Dacă numărul se află pe linia de jos a pătratului (L = P) atunci elementul căutat este U - (P - C). De exemplu, elementul galben este 49 - (3 - 1) = 47.
  • Dacă numărul se află pe linia din stînga a pătratului (C = -P) atunci elementul căutat este U - (lat-1) - (P - L). De exemplu, elementul roșu este 49 - 6 - (3 - -3) = 37.
  • Dacă numărul se află pe linia de sus a pătratului (L = -P) atunci elementul căutat este U - 2·(lat-1) - (P + C). De exemplu elementul verde este 49 - 2·6 - (3 + -2) = 36.
  • Dacă numărul se află pe linia de sus a pătratului (C = P) atunci elementul căutat este U - 3·(lat-1) - (P + L). De exemplu elementul albastru este 49 - 3·6 - (3 + 1) = 27.

Aceasta este procedura completă de calcul pentru elementul aflat la poziția (L C), pe care o veți regăsi, ușor modificată, în programul de mai jos.

Să observăm un lucru evident: putem folosi soluția cerinței doi pentru a rezolva cerința unu în mod banal: vom parcurge matricea în mod obișnuit, pe linii și pe coloane, calculînd fiecare element și afișîndu-l. În acest fel nu mai avem nevoie de matrice!

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int t, n, i, j, l, c, la, ca, max, lat, dif, e;
  long long latl, difl, el;

  fin = fopen( "matsp.in", "r" );
  fout = fopen( "matsp.out", "w" );
  fscanf( fin, "%d%d", &t, &n );
  if ( t == 1 ) { // punctul 1 - matricea spirala
    for ( i = 0; i < n; i++ ) {
      for ( j = 0; j < n; j++ ) {
        l = i - n / 2; // coordonate relative la centrul matricei
        c = j - n / 2;
        la = l < 0 ? -l : l; // valoarea absoluta a lui l
        ca = c < 0 ? -c : c; // valoarea absoluta a lui c
        max = la > ca ? la : ca; // maximul coordonatelor (l c)
        lat = 2 * max;       // latura patratului spira din care face parte (l c) minus 1
        if ( l == max ) // latura de jos a patratului
          dif = max - c;
        else if ( c == -max ) // latura din stinga a patratului
          dif = lat + max - l;
        else if ( l == -max ) // latura de sus a patratului
          dif = 2 * lat + c + max;
        else
          dif = 3 * lat + l + max;
        e = (lat + 1) * (lat + 1) - dif; // numarul la (l c)
        fprintf( fout, "%d ", e );
      }
      fprintf( fout, "\n" );
    }
  } else { // punctul 2 - ce nr se afla la pozitia (l c) in matricea spirala
    fscanf( fin, "%d%d", &l, &c );
    l -= (n + 1) / 2; // coordonate relative la centrul matricei
    c -= (n + 1) / 2;
    la = l < 0 ? -l : l; // valoarea absoluta a lui l
    ca = c < 0 ? -c : c; // valoarea absoluta a lui c
    max = la > ca ? la : ca; // maximul coordonatelor (l c)
    latl = 2 * max;       // latura patratului spira din care face parte (l c) minus 1
    if ( l == max ) // latura de jos a patratului
      difl = max - c;
    else if ( c == -max ) // latura din stinga a patratului
      difl = latl + max - l;
    else if ( l == -max ) // latura de sus a patratului
      difl = 2 * latl + c + max;
    else
      difl = 3 * latl + l + max;
    el = (latl + 1) * (latl + 1) - difl;
    fprintf( fout, "%lld\n", el );
  }
  fclose( fin );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Este destul de clar că prima cerință necesită O(n2) timp, iar a doua O(1). Memoria este, pentru ambele cerințe, O(1).

Problema matzeb (matrice zebră)

Problema matzeb pare, la prima vedere, o problemă de parcurgere în matrice. Putem parcurge matricea în L-uri, înscriind numerele de la 1 la n2 în căsuțele parcurse. Apoi, pentru prima cerință vom afișa matricea, iar pentru cea de-a doua cerință vom afișa elementul cerut, de la linia și coloana citite la intrare.

Codul ar arăta cam așa:

  l = c = -1;
  e = 1;
  for ( i = 0; i < n; i++ ) {
    l++;
    c++;
    for ( j = 0; j < i; j++ ) {
      a[l][c] = e;
      e++;
      l += i % 2;
      c += 1 - i % 2;
    }
    for ( j = 0; j <= i; j++ ) {
      a[l][c] = e;
      e++;
      l -= 1 - i % 2;
      c -= i % 2;
    }
  }

Să observăm un lucru: cele două bucle for, care parcurg cele patru segmente ale unei spire, sînt aproape identice, diferind doar incrementarea sau decrementarea liniei sau coloanei. Pentru aceasta putem folosi același truc ca la problema matrice spirala (matsp), pentru a factoriza codul. Vom obține:

  l = c = 0;
  e = 1;
  for ( i = 0; i < n; i++ ) {
    for ( dir = 0; dir < 2; dir++ )
      for ( j = 0; j < i; j++ ) {
        a[l][c] = e;
        e++;
        l += i % 2 - dir;
        c -= i % 2 - 1 + dir;
      }
    a[l][c] = e;
    e++;
    l += i % 2;
    c -= i % 2 - 1;
  }

Această soluție funcționează bine pentru prima cerință. Care este problema cu această soluție la cerința doi? Memoria! Să calculăm memoria necesară: deoarece N este maxim un miliard matricea va avea un un miliard de miliarde de elemente, ceea ce este exclus să ne încapă în memorie. Chiar și dacă ar încăpea în memorie, timpul de calcul ar fi prea mare. Testele problemei sînt de așa natură încît veți obține 65p cu această soluție, 50p pentru prima cerință și 15p (din cele 50p) pentru a doua cerință. La clase mai mari punctarea va fi mai dură, probabil ați obține 30p cu această soluție, deoarece prima cerință s-ar puncta 20p, iar a la a doua ați lua 10p din 80p.

Care este soluția, atunci? Din nou, matematica ne sare în ajutor. Date o linie și o coloană putem oare să calculăm elementul care se află la acea poziție? Este o problemă asemănătoare cu problema medalion, deci răspunsul este da.

Să observăm un lucru evident: putem folosi soluția cerinței doi pentru a rezolva cerința unu în mod banal: vom parcurge matricea în mod obișnuit, pe linii și pe coloane, calculînd fiecare element și afișîndu-l. În acest fel nu mai avem nevoie de matrice!

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int t, n, l, c, r, e;
  long long el;

  fin = fopen( "matzeb.in", "r" );
  fout = fopen( "matzeb.out", "w" );
  fscanf( fin, "%d", &t );
  if ( t == 1 ) { // punctul 1 - matricea zebra
    fscanf( fin, "%d", &n );
    for ( l = 0; l < n; l++ ) {
      for ( c = 0; c < n; c++ ) {
        if ( l > c ) {
          r = l % 2;
          e = (1 - r) + (r + l) * (r + l) + (1 - 2 * r) * c;
        } else {
          r = (c + 1) % 2;
          e = (1 - r) + (r + c) * (r + c) + (1 - 2 * r) * l;
        }
        fprintf( fout, "%d ", e );
      }
      fprintf( fout, "\n" );
    }
  } else { // punctul 2 - ce nr se afla la pozitia (l c) in matricea zebra
    fscanf( fin, "%d%d", &l, &c );
    l--; // coordonate de la 0
    c--;
    if ( l > c ) {
      r = l % 2;
      el = (1 - r) + (r + (long long)l) * (r + l) + (1 - 2 * r) * c;
    } else {
      r = (c + 1) % 2;
      el = (1 - r) + (r + (long long)c) * (r + c) + (1 - 2 * r) * l;
    }
    fprintf( fout, "%lld\n", el );
  }
  fclose( fin );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție? Este destul de clar că prima cerință necesită O(n2) timp, iar a doua O(1). Memoria este, pentru ambele cerințe, O(1).

Rezolvări aici [1]

Lecție

Discuții probleme din urmă. Am vorbit despre problemele:

Tema

Tema 13 clasa a 6a

  • figura dată la ONI 2010 clasa a 6a
  • suprapuneri1 dată la OJI 2007 clasa a 9a
  • Opțional (dar în cadrul concursului temă): leduri dată la .campion 2003

Rezolvări aici [2]