Clasa a VI-a lecția 25 - 14 mar 2019

From Algopedia
Jump to: navigation, search

Anunțuri

Reluare concursuri de acasă

De duminica aceasta reluăm concursurile de acasă. Ca de obicei, ele vor începe la ora 15.

Concursul Infotehnium

Dacă doriți, puteți participa la concursul Infotehnium, ce se va desfășura sîmbătă 30 martie la școala 164. Cei ce doresc să participe dați-mi un email. Voi colecta numele voastre și le voi trimite către organizatori. Data limită de înscriere este 21 martie. Secțiunea care vi se potrivește este clasa a șasea avansați.

Tema - rezolvări

Comentarii

  • Din ce în ce mai mulți puneți comentarii în sursele voastre. Bravo! Vă mulțumesc, mă ajută foarte mult.

Problema accesibil

Comentarii

  • Majoritatea ați reușit să treceți toate testele, bravo.
  • Mulți dintre voi ați scris programe cam lungi pentru o problemă așa simplă.
  • Mulți dintre voi ați simțit nevoia să scrieți o funcție. Lăudabil, dar nu era cazul, precum veți vedea mai jos.
  • Unii ați folosit vectori pentru a stoca cifrele numerelor. Era chiar drăguț dacă ați fi și citit numerele caracter cu caracter, pentru a nu le mai procesa din nou pentru a separa cifrele, efecutînd împărțiri.

Rezolvare

Problema accesibil a fost dată la OJI 2017 clasa a 6a.

Ea este o problemă relativ simplă, a cărei dificultate constă în atenția la detaliu și execuția întocmai a celor patru cerințe.

Iată o soluție posibilă (66 linii de cod):

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, k, p, i, j, e, ce, u, naa, max[4];
  long long p10;

  fin = fopen( "accesibil.in", "r" );
  fout = fopen( "accesibil.out", "w" );
  fscanf( fin, "%d%d%d", &p, &k, &n );
  max[0] = max[1] = max[2] = max[3] = naa = 0;
  if ( p == 1 || p == 2 ) { // cerinta 1 sau 2, vom lucra cu sirul de numere
    for ( i = 0; i < n; i++ ) {
      fscanf( fin, "%d", &e );
      // testam daca e este accesibil, sau devine prin eliminarea unei cifre
      p10 = 1; // calculam prima putere a lui 10 strict mai mare ca numarul e
      while ( p10 <= e )
        p10 *= 10;
      do { // testam numerele ca accesibile, incepind chiar cu e
        ce = e % p10 + e / (p10 * 10) * p10; // eliminam cifra puterii p10
        p10 /= 10;
        // 'ce' a devenit accesibil?
        if ( ce > 11 ) { // trebuie sa aiba cel putin doua cifre
          u = ce % 10;
          while ( ce > 0 && ce % 10 == u ) {
            ce /= 10;
            u--;
          }
        } else
          ce = 1; // ca nu cumva sa devina zero prin eliminarea cifrei
      } while ( p10 > 0 && ce > 0 );

      if ( ce == 0 ) {        // e sau unul din transformate este accesibil?
        if ( p10 * 10 > e ) { // numarul e este accesibil
          // 1: cele mai mari trei numere accesibile
          u = 0;
          while ( e < max[u] )
            u++;
          if ( u < 3 ) {
            for ( j = 2; j > u; j-- )
              max[j] = max[j - 1];
            max[u] = e;
          }
        } else            // e devine accesibil prin eliminarea unei cifre
          naa++;
      }
    }
    if ( p == 1 )
      fprintf( fout, "%d %d %d\n", max[2], max[1], max[0] ); // cerinta 1
    else
      fprintf( fout, "%d\n", naa );                    // creinta 2
  } else if ( p == 3 ) { // 3: minimul si maximul accesibil de k cifre
    for ( i = 1; i <= k; i++ )
      fputc( i + '0', fout );
    if ( k < 9 ) {
      fputc( ' ', fout );
      for ( i = k; i > 0; i-- )
        fputc( 10 - i + '0', fout );
    }
  } else // 4: numarul de numere accesibile pare si impare de k cifre
    fprintf( fout, "%d %d\n", (10 - k) / 2, (11 - k) / 2 );
  fclose( fin );
  fclose( fout );

  return 0;
}

De remarcat:

  • Factorizarea codului de testare a accesibilității numărului, precum și a transformatelor lui. Pentru aceasta am eliminat o cifră zero din fața primei cifre a numărului, pornind cu puterea lui 10 ceva mai mare.
  • Folosirea unui vector pentru cele trei maxime, pentru un cod mai elegant și nerepetitiv.
  • Banalitatea ultimelor două cerințe, dacă tratați matematic problema.

Ce complexitate au cerințele? În mod evident ultimele două sînt O(1) (tehnic ele sînt O(log MAXX)). Prima cerință parcurge cifrele numerelor de la intrare, deci este O(n log MAXX). Ultima cerință parcurge cifrele numerelor pentru fiecare cifră eliminată, deci ea este O(n log2MAXX).

Deoarece nu folosim vectori, memoria este O(1).

Problema fermier1

Comentarii

  • Circa jumate din voi ați avut probleme în rezolvarea acestei probleme care este relativ simplă și cu o rezolvare foarte scurtă: 48 linii de cod scris aerisit, 41 de linii reale.
  • Motivul pentru care ratați teste este faptul că nu luați în considerare toate cazurile particulare.
  • Ratați cazuri particulare pentru că gîndirea voastră este încîlcită, iar codul decurge din ea. Stați la masă și desenați pe hîrtie. Creați teste și rulațile de mînă. Astfel veți vedea ce se repetă și vă veți structura mai bine soluția.
  • Majoritatea soluțiilor corecte nu folosesc bucla de simulare învățată la curs. Mai exact, acele soluții două bucle imbricate, ambele mutînd mașina. Acest lucru complică codul. Trebuia să folosiți o singură buclă în care mutați mașina corespunzător. Încercați să respectați cele învățate, vă vor ajuta (bănuiesc că de aceea veniți la IQ Academy, nu? :-)

Rezolvare

Problema fermier1 a fost dată la OJI 2017 clasa a 6a.

Este o problemă de simulare. Nu este o problemă de algoritm, ci de tratare cu atenție a cazurilor particulare. Deoarece avem multe metode de rezolvare, este bine să căutăm una care să minimizeze cazurile particulare.

O abordare simplă este să observăm că la fiecare deplasare mașina nu poate avea decît două destinații:

  • Către depozit, atunci cînd cargoul este zero.
  • Către plantație, atunci cînd cargoul este non-zero.

Astfel, în bucla de simulare, la fiecare iterație vom deplasa mașina la noua ei destinație, în funcție de cît cargo are. Vom avea grijă ca atunci cînd alimentăm complet o plantație să avansăm plantația dorită.

Pentru o implementare eficientă avem nevoie să calculăm rapid:

  • Distanța de la o plantație la depozit.
  • Distanța minimă între o plantație și depozit, sau între două plantații consecutive.

Pentru a calcula rapid distanța de la o plantație la depozit vom folosi un vector de sume parțiale, să-l numim dtot[], de la distanța totală. dtot[i] va fi suma distanțelor pînă la parcela i.

Pentru a calcula rapid distanța minimă între două puncte vom calcula suma tuturor distanțelor s. Astfel, avem distanța directă între două puncte, să-i spunem d. Distanța inversă, di, va fi egală cu s - d.

Pentru a nu repeta cod atunci cînd revenim la depozit, după alimentarea ultimei plantații, vom simula deplasarea pînă la o plantație fictivă, numărul n + 1, care se află suprapusă peste depozit și are un necesar de alimentare zero. Distanța de la depozit la această plantație fictivă va fi suma tuturor distanțelor, de care oricum avem nevoie în calcule.

Iată o soluție posibilă, destul de scurtă (48 linii de cod):

#include <stdio.h>

int q[102], dtot[102]; // depozitul n + 1 este santinela, pt. revenire

int main() {
  FILE *fin, *fout;
  int n, c, t, i, d, plant, posm, dist;

  fin = fopen( "fermier1.in", "r" );
  fscanf( fin, "%d%d", &n, &c );
  for ( i = 0; i <= n; i++ ) {
    fscanf( fin, "%d", &d );   // distantele dintre plantatii
    dtot[i + 1] = dtot[i] + d; // distantele de la dep la plantatia i
  }
  for ( i = 1; i <= n; i++ )   // cantitatile necesare la plantatii
    fscanf( fin, "%d", &q[i] );
  fclose( fin );

  dist = 0;  // initial am parcurs o distanta zero cu masina
  t = c;     // initial masina este umpluta cu c
  posm = 0;  // initial masina se afla la pozitia zero, depozitul
  plant = 1; // plantatia de aprovizionat
  while ( plant <= n + 1 ) { // mergem o plantatie in plus suprapusa pe depozit
    // parcurgem distanta de la posm la destinatie (plantatie sau depozit)
    if ( t == 0 ) { // sint in plant cu masina pe zero, mergi la depozit
      d = dtot[posm];    // distanta pina la depozit
      posm = 0;           // revenim la depozit
      t = c;              // reincarcam
    } else { // mergi la plantatie sa alimentezi
      d = dtot[plant] - dtot[posm]; // distanta la urmatoarea plantatie
      posm = plant;       // mergem la plant, nu neaparat umplem plantatia
      if ( t < q[plant] ) { // vom goli masina
        q[plant] -= t;    // aprovizionam cu t
        t = 0;            // masina e goala
      } else { // poate va ramine ceva in masina dupa descarcare
        t -= q[plant];    // descarcam din masina
        plant++;          // plantatie complet aprovizionata, avansam
      }
    }
    dist += d < dtot[n + 1] - d ? d : dtot[n + 1] - d; // minimul distantei
  }
  
  fout = fopen( "fermier1.out", "w" );
  fprintf( fout, "%d\n", dist );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Nu este chiar banal de analizat. Deoarece o iterație se execută în O(1), trebuie să calculăm numărul de iterații. Pentru aceasta trebuie să ne întrebăm cîte drumuri poate face mașina. Este clar că ea va face cu atît mai multe drumuri cu cît cantitatea transportată de ea este mai mică și cu cît plantațiile necesită cantități mai mari. Aprovizionarea unei plantații va necesita O(q/c) drumuri. Avînd n plantații complexitatea totală va fi O(n·q/c).

Se va încadra în timp? Făcînd înlocuirile cele mai defavorabile, cu c minim, adică 1, n maxim, adică 100 și qi maxim, adică 1000 obținem 100000 de operații, care se vor încadra lejer în cele 0.2s

Memoria ocupată este, evident, O(n).

Problema șoricel

Comentarii

  • Problema a fost grea. S-a văzut și după rezultate.
  • Mulți ați dat soluții bune ca algoritm și foarte diferite ca implementare.
  • Dacă o implementați ca simulare ce urmează întocmai enunțul codul ieșea destul de lung și complicat (a.k.a. tractor). Probabil că depășea și timpul.
  • La unii din voi nu am înțeles mai nimic din soluție. Poate nu era nimic de înțeles? :-)
  • Unii din voi ați făcut o simulare brută la punctul doi și ați depășit timpul. Ar fi interesant de văzut cîte puncte ia brutul implementat cu grijă.
  • A fost interesant să văd cum v-ați descurcat cu parcurgerea matricei în "șarpe" de sus în jos.
    • Unii din voi ați folosit bordare în diverse feluri. Interesant!
    • Alții ați folosit paritatea liniei ca indice într-un vector de două elemente ce conținea -1 și 1. Interesant, deși aveam formulă de conversie foarte ușoară, de la [0, 1] la [-1, 1].
    • Alții ați depus elementele într-un vector, în ordinea parcurgerii, după reguli matematice, sau duplicînd citirea unei linii.
    • Alții ați duplicat codul de parcurgere a unei linii. Urît!

Rezolvare

Problema șoricel a fost dată la ONI 2017 clasa a 6a.

Este o problemă de simulare, dar una ceva mai complicată. Forța brută nu pare a se încadra în timp.

Pentru prima parte a problemei vom aplica regula:

  • Matematica duce la soluții eficiente

Să ne gîndim la una din camerele labirintului. Fie C cantitatea de cașcaval din acea cameră. Atunci:

  • Cantitatea de cașcaval va scădea zilnic cu 1.
  • Cantitatea de cașcaval va scădea brusc la zero atunci cînd ea devine pătrat perfect.

Putem să găsim o formulă matematică să ne calculeze numărul de zile în care cantitatea din cameră ajunge la zero? Să vedem:

  • Fie P cel mai mare număr astfel încît P este pătrat perfect și P < C.
  • Atunci numărul de zile în care se va goli camera este Z = C - P.

Rămîne să calculăm acest P. Cum calculăm cel mai mare pătrat perfect mai mic decît C. Ei bine:

  • P = sqrt(C) - unde sqrt este radicalul parte întreagă.

Prima cerință

Putem acum rezolva ușor prima cerință:

  • Numărul de zile în care se golește depozitul este maximul numărului de zile calculat conform formulei, pentru fiecare cameră.
  • În ziua K John va goli acele camere pentru care Z == K.

Cerința doi

O soluție forță brută calcula pentru fiecare cameră numărul de zile în care aceasta va fi golită, conform formulei de la prima cerință. Apoi va parcurge matricea în sensul șerpuit, dorit, căutînd numărul de apariții al zilei minime Z și calculînd numărul maxim de apariții consecutive al acelei zile minime Z. Apoi va reseta toate aparițiile acelei zile Z și va căuta următorul minim, reluînd algoritmul.

Această soluție face atîtea parcurgeri cîte numere de zile distincte avem în matrice. Maximul fiind mare, circa 20000, probabil vom depăși timpul pe teste mari. Putem rezolva problema și altfel?

După ce calculăm toate numerele de zile în care se golește depozitul am putea să facem o singură parcurgere, în care să căutăm numere de zile identice consecutive. Este o soluție similară cu forța brută, în care însă putem face toate parcurgerile într-una singură.

Iată o soluție bazată pe aceste idei (63 de linii de cod):

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

#define MAXN 200

int dep[MAXN][MAXN];  // cantitatile initiale de cascaval
short zi[MAXN][MAXN]; // peste cite zile devine cantitatea patrat perfect

int main() {
  FILE *fin, *fout;
  int p, n, m, k, l, c, nrz, r, zimax, ncubmax, ncub, nconsmax, ncons, uz, dc, camk;
  
  fin = fopen( "soricel.in", "r" );
  fscanf( fin, "%d%d%d%d", &p, &n, &m, &k );
  camk = nrz = 0;
  for ( l = 0; l < n; l++ )
    for ( c = 0; c < m; c++ ) {
      fscanf( fin, "%d", &dep[l][c] );
      if ( dep[l][c] > 1 ) {
        r = sqrt( dep[l][c] - 1 );
        zi[l][c] = dep[l][c] - r * r; // peste cite zile devine patrat perfect

        // pentru cerinta 1
        if ( zi[l][c] > nrz ) // retinem cel mai mare numar de zile
          nrz = zi[l][c];
        if ( zi[l][c] == k )  // retinem cite camere goleste John in ziua k
          camk++;
      }
    }
  fclose( fin );

  // cerinta 2: parcurgem camerele in ordinea lui john
  uz = zimax = ncubmax = ncub = nconsmax = ncons = 0;
  c = 0;
  dc = 1;
  for ( l = 0; l < n; l++ ) {
    while ( c >= 0 &&  c < m ) {
      if ( zi[l][c] != uz ) // avem zile diferite in matrice
        ncons = ncub = 0;   // resetam nr cam consecutive si cuburile mincate in ele
      if ( zi[l][c] > 0 ) { // dupa acest nr zile camera va fi golita de john
        ncons++;            // inca o camera consecutiva in care putem minca
        ncub += dep[l][c] - zi[l][c]; // mincam inca atitea cuburi in acea camera
        uz = zi[l][c];      // ultima zi vazuta in matrice
        if ( (ncons > nconsmax) || // retinem noua secventa daca este mai buna
             (ncons == nconsmax && ncub > ncubmax) ||
             (ncons == nconsmax && ncub == ncubmax && zi[l][c] > zimax) ) {
          nconsmax = ncons;
          zimax = zi[l][c];
          ncubmax = ncub;
        }
      }
      c += dc; // avansam coloana
    }
    c -= dc;  // la capat de rind ne intoarcem inapoi in matrice
    dc = -dc; // si schimbam directia
  }

  fout = fopen( "soricel.out", "w" );
  fprintf( fout, "%d\n%d\n", p == 1 ? nrz : nconsmax, p == 1 ? camk : zimax );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

La punctul 1 vom procesa fiecare element al matricei în O(1), deci complexitatea va fi O(N·M). Memoria folosită va fi O(1).

La punctul 2 vom traversa matricea procesînd fiecare element al matricei în O(1), deci complexitatea va fi O(N·M). Memoria folosită va fi O(N·M) deoarece trebuie să reținem elementele matricei pentru a o parcurge în altă ordine decît cea dată. Atenție! Dacă memoria ar fi fost o problemă am fi putut să o reducem la O(M), memorînd cîte o linie a matricei și procesînd-o, apoi aruncînd-o.

Rezolvări aici: [1]

Lecție

Comentarii olimpiada de informatică, faza județeană

Iată un tabel interesant, cu rezultatele curioșilor la olimpiadă, combinate cu statistici varena:

OJI IQA Nume Instructori în afara IQ Academy P1 P2 Tot Med IQA
1 22 BENESCU ALEXANDRU 90 100 190 86.16
2 10 IPATE ELISA 85 100 185 121.5
2 1 VOICU TUDOR KNOPF ANCA 90 95 185 156.83
4 2 PETCU ANA MARIA KNOPF ANCA 90 90 180 146.66
5 14 TEODORESCU NICOLAS ALEXANDRU 70 100 170 109.5
6 21 MARCU ILINCA IOANA KNOPF ANCA 95 70 165 91.83
6 18 IORDACHE RARES MIHAI MANZ VICTOR 100 65 165 96.33
6 8 DOBRE RADU FABIAN KNOPF ANCA 85 80 165 131.33
6 25 MOCANU MIHAI-ADRIAN KNOPF ANCA, MANZ VICTOR 90 75 165 78.33
10 12 MUSAT TUDOR STEFAN 60 100 160 115
10 6 TATOMIR TEODOR ADONIS TATOMIR 60 100 160 136.33
10 11 NICU ALEXANDRU CRISTIAN MARIANA KISCH 85 75 160 118.33
13 16 STEFANESCU ECATERINA 85 70 155 102.33
13 13 BURAC VLAD-ALEXANDRU 90 65 155 110.83
13 5 RUGHINIS REMUS 90 65 155 137.33
16 4 BADEA LUCIAN-ANDREI 75 75 150 140
17 19 CALOTA ANDREI-PATRICK KNOPF ANCA 60 75 135 93.33
18 24 NICOLA VICTOR-TEODOR 50 75 125 80.33
18 27 STANCU DAVID 50 75 125 57.16
20 7 ASGARI ARMIN MARIANA KISCH, CASIAN PATRASCANU 50 60 110 133.33
21 15 CHIVU ANDREEA ANA 55 50 105 106
21 28 CADIR TIMUR MANZ VICTOR 55 50 105 55
21 3 ILIE LUCA MIHAI 65 40 105 144.5
24 17 COJOCARIU IOAN DRAGOS NICOLAE 50 50 100 98.83
24 26 HOSSU ALEXANDRU MANZ VICTOR 50 50 100 75.16
26 9 TOGAN TEODOR-BOGDAN 50 45 95 128.66
27 20 FARES YUSUF MARIANA KISCH, FARES MOHAMAD,

CHIRIAC ANDREI, MIRICA MATEI

60 10 70 92.66
28 23 STOIAN DARIA-ALEXANDRA KNOPF ANCA, VICTOR MANZ 50 10 60 83.5

Observații:

  • Felicitări lui Alex Benescu, ce a obținut punctajul maxim pe țară, 190p!
  • Felicitări lui Ipate (185p), Voicu (185p) și Petcu (180p) ce au obținut punctaj aproape de maxim (echivalentul notei 9).
  • În primele zece locuri avem 6 curioși inversiune: Benescu, Ipate, Teodorescu, Marcu, Iordache, Mocanu. Ei se află mult mai jos în clasamentul concursurilor varena, obținînd peste așteptări la olimpiadă. Pare că ei se concentrează mai mult pe rezolvat probleme decît pe trișat.
  • Nu pare că a vă lua instructori extra ajută: dacă ar fi ajutat ar fi trebuit ca majoritatea celor de la vîrf să aibă instructori din afara IQ Academy. În loc de aceasta, se observă că elevii cu instructori sînt destul de uniform distribuiți. Oare dacă nu aveați instructori suplimentari ați fi obținut un rezultat mai bun la olimpiadă? Posibil, deoarece căpătați năravuri proaste (cum ar fi programarea aproximativă).
  • Cu cît aveți mai mulți profesori este mai rău, conform acestui clasament :-)

Problema album

Problema album a fost dată la OJI 2019 clasa a 6a.

Ea are o rezolvare destul de simplă, cu forță brută și diverse variante optimizate. Să discutăm o parte din ele.

Soluție forță brută

În această soluție simulăm enunțul. Fiecare copil ia primul sticker rămas pe masă, apoi culege stickerele care se potrivesc cu el. Pentru această soluție:

  • Vom memora stickerele într-un vector.
  • Vom parcurge vectorul, în ordine, căutînd elemente nenule.
  • Cînd găsim un element nenul îi calculăm cifrele maxime.
  • Apoi parcurgem restul vectorului, căutînd acele două cifre în alte numere nenule.
  • Cînd găsim astfel de numere, le adăugăm la copilul curent și apoi le setăm la zero, pentru a nu mai fi luate în calcul la o parcurgere următoare.

Ce complexitate are această soluție?

Ea depinde foarte mult de numărul de parcurgeri ale vectorului. Cîte parcurgeri putem avea? Să observăm următoarele:

  • La fiecare parcurgere vom căuta două cifre, cf1 și cf2, pereche neordonată.
  • Toate acele numere vor fi eliminate din șir, prin setarea lor la zero.
  • Atunci, la următoarele parcurgeri nu vom mai putea căuta aceeași pereche de cifre.

Rezultă că numărul de parcurgeri este numărul posibil de perechi de cifre neordonate distincte. Acest număr este Gauss(Σ+1), unde Σ este mărimea alfabetului, adică 10, în cazul nostru, deoarece avem zece cifre. Cu alte cuvinte vom avea O(Σ2) parcurgeri. Vom parcurge O(n) elemente. Pentru fiecare element vom separa cifrele sale, deci vom face O(log MAXS) împărțiri. Rezultă o complexitate totală de O(n·Σ2·log MAXS).

Se încadrează în timp? Să facem înlocuirile: știm că Σ2 este, în fapt, circa 54, iar log MAXS este, în fapt, 6. Numărul de operații va fi 800000·54·6 ≈ 260 milioane. Deoarece vorbim de împărțiri înmulțim cu 30, obținînd circa 7.8 miliarde operații. Deci această soluție nu ar trebui să se încadreze în timp pentru teste mari. Am generat un test maximal pe care această soluție a durat 4.3s, iar soluția oficială a autoarei a durat 6.8s.

Cu toate acestea, surpriza emisiunii este că soluția forță brută, scrisă îngrijit, lua 100p la ONI. Cum este posibil acest lucru? Deoarece testele oficiale sînt departe de a fi maximale. Cel mai mare test este de circa cinci ori mai mic decît cel maximal, în termen de număr de operații.

Să recapitulăm: una dintre soluțiile oficiale ale autoarei, doamna Violeta Grecea, nu trece testul maximal, promis de enunț! Dar acest lucru este mascat de faptul că testele nu sînt maximale.

De ce a decis comisia să nu folosească teste maximale? Nu putem ști. Cel mai adesea motivele lor sînt bune, la origine:

  • Să nu chinuim bieții copilași.
  • Să se încadreze în timp și soluții mai puțin bine scrise.
  • Este totuși OJI, să nu le dăm probleme ca la ONI.

Toate aceste motive sînt OK, dar comisia uită un lucru esențial:

Inversiunea valorilor: o problemă care promite un nivel elevat și nu îl respectă va defavoriza elevii buni și îi va favoriza pe cei slabi.

Acest lucru se întîmplă deoarece un elev bun își va da seama că forța brută nu se încadrează în timp și va căuta un algoritm mai bun, reușind sau nu și pierzînd puncte și timp. Un elev mai slab nu va ști să scrie decît forța brută, cu care va lua 100p, cîștigînd timp pentru a se gîndi la celelalte probleme din set.

Cuvînt deschis pentru comisia științifică: dragi profesori! Sînteți cei mai buni dintre cei buni, reprezentînd profesorii din țară la cel mai înalt nivel posibil. Nu puteți, nu aveți voie să faceți astfel de greșeli! Sînteți închiși în turnul vostru de fildeș, nimeni nu poate ajunge la voi pentru o discuție sau pentru a contesta validitatea problemelor și a testelor. Gîndiți-vă la elevii pe care este de presupus să îi îndrumați pe calea deloc ușoară a informaticii. Ei vor constata că această problemă este incorectă și se vor îndrepta către alte domenii, unde olimpiada este corectă. Olimpiada de informatică trebuie să fie meritorie! În momentul cînd elevii iau puncte nemeritat, distrugeți însuși motorul, însăși baza, însăși fundația acestei olimpiade!

Soluție semi-forță brută

Putem aduce forța brută să se încadreze în timp, cu o modificare minimală?

Motivul principal pentru care forța brută nu se încadrează în timp este faptul că face multe împărțiri. Putem să păstrăm complexitatea algoritmului, dar să reducem numărul de împărțiri? Desigur că da. Să observăm că noi nu folosim acele numere drept cantități, ci doar ca înșiruiri de cifre. Mai mult, aceste cifre ni se dau la intrare! Deci de ce să le citim ca numere, numai ca pentru apoi să ne dăm singuri de lucru să extragem cifrele lor?

O soluție care nu face nici o împărțire va citi numerele la intrare caracter cu caracter și va memora pentru fiecare număr cifrele sale. Vom avea, astfel, o matrice de n × 6 caractere. Restul algoritmului rămîne la fel. Soluția devine imediat de 30 de ori mai rapidă, plus că citirea va fi și ea de circa 4 ori mai rapidă. Cele circa 260 milioane de operații se vor încadra chiar și în 0.5s cam pe orice calculator.

Soluții elegante

Se poate mai bine? Desigur!

O primă idee ar fi să tratăm problema puțin invers: să facem o singură parcurgere, iar pentru fiecare număr să ne întrebăm dacă a fost cules și de cine. Pentru aceasta trebuie să memorăm într-un vector șirul de numere alese de copii, cele originale, pe baza cărora le alegem pe următoarele. În fapt, e deajuns să ținem minte doar cele două cifre maximale. Apoi, pentru fiecare număr citit, parcurgem vectorul de cifre maximale și vedem dacă la vreuna din poziții conține ambele cifre. Dacă da, el este luat de acea poziție. Dacă poziția este pară, este unul din copii, altfel este celălalt.

Ce complexitate are această soluție? Deoarece putem avea maxim 54 de numere în șirul de numere alese, vom avea aceeași complexitate, O(n·Σ2·log MAXS). De ce funcționa mai bine? Deoarece vom folosi mult mai puțină memorie, pentru cei doi vectori de cifre maximale, respectiv O(Σ2). Este vorba de acel cache, despre care am mai vorbit. Pentru o implementare eficientă vom construi pentru fiecare număr vectorul de frecvență al cifrelor sale. Astfel vom putea testa dacă două cifre fac parte din acel număr în O(1).

O a doua idee ar fi să mergem și mai departe: oare nu putem să scăpăm de o căutare liniară într-un vector de 54 de elemente? Am putea să facem două modificări:

  • Să creăm un vector de frecvență al cifrelor maximale. În loc să avem un vector cu acele cifre, putem să procedăm altfel: date cifrele maximale cf1 și cf2, cu cf1 ≤ cf2, vom marca în tur[cf1 * 10 + cf2] numărul turului în care au fost selectate acele cifre maximale.
  • Pentru fiecare număr din șir vom crea toate grupele de două cifre și pentru fiecare grupă vom căuta în vectorul de frecvență dacă există un tur, luînd turul minimal.

Ce complexitate are această soluție? Pentru fiecare număr vom face atîtea calcule cîte perechi putem forma, adică O(log2MAXS). Soluția va avea complexitatea O(n·log2MAXS). Făcînd înlocuirile, avem acel log drept perechile formate din 6 cifre, deci 15 posibilități, pe care le vom înmulți cu 800000, obținînd 12 milioane de operații, un număr și mai mic, care cred că este și optim. Memoria folosită va fi un vector de 100 de elemente.

Vă sugerez ca la temă să implementați această soluție, deoarece vă va solicita la maxim, pregătindu-vă astfel pentru ONI.

Constatări în urma analizei problemei album

Constatări grave:

  • Problema induce elevii în eroare: enunțul ne spune că este necesară o soluție rapidă (deci complexă), dar testele permit și soluții simple, forță brută.
  • Chiar și setînd timpul problemei la o treime din timpul acordat în concurs, cu o soluție simplă, forță brută se luau 90p. Dar acest lucru nu se putea deduce din enunț! În fapt nu merita să găsești un algoritm bun, ci doar cel mai simplu posibil. Testele favorizau, astfel, elevii slabi și defavorizau elevii buni.
  • Nu există teste cu limitele din enunțul problemei, ceea ce este foarte grav. Cele mai mari teste sînt la o cincime ca număr de operații față de testele maximale, ceea ce, împreună cu timpul foarte mare, permite unei soluții simple, forță brută să ia punctaj maxim.
  • Problema inversează astfel valorile între elevii buni și cei medii, avantajînd un elev mediu, care nu caută o soluție superioară, ci una simplă, mult mai greu de greșit, în același timp cîștigînd timp de lucru pentru cealaltă problemă.
  • Acest lucru se vede și din clasamentul de la OJI: șase dintre elevii clasați în primele zece locuri la faza națională de anul trecut au luat scor slab la această problemă: Ilie, Asgari, Ghica, Slănină, Nicola, Tatomir.
  • Una din soluțiile oficiale, chiar cea a autoarei, pică teste maximale la timpul de executare, deci este incorectă.

Alte constatări îngrijorătoare:

  • O soluție elegantă este de mai mult de zece ori mai rapidă, dar nu se poate diferenția de cea simplă, brută, ea luînd tot punctaj maxim, 100p.
  • Între sursele oficiale nu se află nici una optimă atît ca timp cît și ca memorie. Ce exemplu dăm elevilor?
  • Unele soluții ale comisiei sînt mai lente decît forța brută scrisă îngrijit, cum ar fi una din soluțiile autoarei, prof. Violeta Grecea, care pică teste maximale.
  • Cu o soluție simplă, forță brută scrisă îngrijit, se putea lua punctaj maxim, 100p. Mult prea mult! Trebuia ca măcar 10p să fie păstrate pentru o soluție elegantă, pentru care elevul bun s-a chinuit.
  • Testele aveau nereguli, atît în .in cît și în .ok:
    • Spații la final de șir de numere
    • Linii goale în plus
    • Lipsă \n la finalul ultimei linii
  • Nici una din nereguli nu era gravă, cum ar fi fost dacă între două numere din șir am fi avut mai mult de un spațiu.

Update:

  • Pe data de 18 martie 2019 am trimis o sesizare doamnei ministru al educației, Ecaterina Andronescu: Solicitare de atenție Olimpiada Națională de Informatică - etapa județeană martie 2019.
  • Pe data de 23 aprilie am primit un răspuns de la Direcția Generală de Educație, în cadrul Ministerului Educației Naționale: răspuns.
  • Răspunsul Direcției Generale de Educație se referă la procedura desfășurării olimpiadei. În două pagini ei repetă ceea ce știm cu toții, regulamentul olimpiadei. Nu răspund la cererea de modificare a regulamentul pentru a permite contestarea unei probleme (și nu contestarea corecturii unei soluții în particular). Cu alte cuvinte, eu le-am spus procedura permite abuzuri de care nu ne putem apăra, iar doamna director Gabriela Drăgan mi-a răspuns comisia a acționat corect și conform procedurii. Foarte inteligent! :-)
  • Pe data de 24 mai 2019 am primit un răspuns de la Centrul Național de Evaluare și Examinare al Ministerului Educației Naționale: răspuns
  • Răspunsul Centrului Național de Evaluare și Examinare se referă la corectitudinea și meritul problemelor de la OJI. Este un răspuns în bătaie de joc care ocolește problema, anume faptul că testele erau de cinci ori mai mici decît restricțiile menționate în enunțul problemelor, ceea ce permitea unor soluții ciocan să ia 100p fără probleme, în vreme ce "fraierii" care își dădeau seama că soluția ciocan nu va lua 100p pierdeau timpul încercînd să găsească o soluție care să ia 100p. Cu alte cuvinte eu le-am spus soluția dumneavoastră, cea oficială, pică teste maximale care corespund enunțului (dar nu ați dat astfel de teste) iar doamna consilier Livia Țoca mi-a răspuns comisia a dat probleme conform practicii uzuale la olimpiada de informatică. Doamna consilier Livia Țoca și domnii profesori și profesoare din comisia științifică se ascund în spatele tehnicalităților, fără a da cu adevărat un răspuns. Desigur, acest lucru era de așteptat, cînd răspunsul vine de la acuzați prin intermediul unui politician.

Concluzie: atunci cînd de plîngi de activitatea comisiei științifice, este anormal ca ei să dea răspunsul. Ar fi trebuit ca cineva neimplicat să ia în considerare ambele argumente, acel cineva trebuind să fie la cel mai înalt nivel tehnic presupus de olimpiadă.

Mențiune: deși membrii comisiilor științifice nu se publică, am adunat numele unora din membri din autorii problemelor și de la închiderea ONI, la care am participat. Îi listez mai jos, pentru a ști cine stă în spatele acestor probleme și al răspunsurilor de mai sus, care ne insultă inteligența.

Comisia științifică clasa a șasea (listă parțială):

  • Rodica Pintea, liceul teoretic Radu Vlădescu, Pătârlagele, Buzău, șef comisie clasa a 6-a
  • Violeta Grecea, Colegiul Național de Informatică “Matei Basarab” Râmnicu Vâlcea
  • Adrian Niță, Colegiul Național “Emanuil Gojdu”, Oradea
  • Flavius Boian, Colegiul Național “Spiru Haret” Târgu Jiu
  • Liviu-Vasile Pînzaru, Palatul Copiilor Suceava & Clubul Copiilor Fălticeni

Problema maxim2

Problema maxim2 a fost dată la OJI 2019 clasa a 6a.

Ea are o rezolvare relativ simplă, cu forță brută și diverse variante optimizate. Să discutăm o parte din ele. Vom discuta doar cerința 2, prima fiind banală, de nivel clasa a cincea.

Soluția forță brută

În această soluție simulăm enunțul. Vom memora cele n cifre într-un vector de caractere. Apoi vom lua, pe rînd, toate ferestrele de m cifre consecutive și vom forma numerele maxime. Fiecare număr maxim va fi comparat cu un maxim global.

Să detaliem puțin forța brută:

  • Cum formăm cel mai mare număr posibil din m cifre? Problema este de clasa a cincea, vom lua cifrele în ordine descrescătoare. Pentru aceasta formăm un vector de frecvență al cifrelor.
  • Cum comparăm numărul din fereastra curentă de m cifre cu maximul global? Am putea să formăm ambele numere maximale, din vectorii de frecvență, și să îi comparăm. Dar este risipitor. Este mult mai rapid să comparăm direct vectorii de frecvență. Zece comparații în loc de 1000.
  • Ce facem la egalitate? Acele condiții complicate din enunț se rezumă la ceva simplu: se dorește ultima poziție a maximului. Nu este ușor de demonstrat acest lucru. Dar, în condiții de concurs, ce puteam face? Desigur să afișăm întotdeauna ultima poziție, cum cerea a treia posibilitate din enunț. Deci, cumva, enunțul ne ghidează către soluția corectă din motivul incorect (nu știm cum să îndeplinim condiția 2).

Ce complexitate are această soluție?

Vom analiza n - m + 1 ferestre de lungime m. Pentru fiecare fereastră vom avea m operații pentru calculul vectorului de frecvență, și încă Σ operații pentru comparația vectorilor, unde Σ este mărimea alfabetului, în cazul nostru 10. Soluția este, deci, O((n - m + 1)·(m + Σ)). Dacă desfacem parantezele și ignorăm termenii nenecesari vom obține O(n·(m + Σ)). În cazul nostru, deoarece Σ este mult mai mic decît m, complexitatea finală este O(n·m).

Se încadrează în timp? Făcînd înlocuirile obținem 500000·1000, adică 500 milioane. Pare cam la limită și așa și este. Din nou, am generat un test maximal pe care această soluție a durat circa 1s, iar soluția oficială a autoarei a durat 3s, depășind timpul permis.

Cu toate acestea, din nou, surpriza emisiunii este că soluția forță brută, scrisă îngrijit, lua 100p la ONI. Cum este posibil acest lucru? Deoarece, din nou, testele oficiale sînt departe de a fi maximale. Cel mai mare test este de circa cinci ori mai mic decît cel maximal, în termen de număr de operații.

Nu are sens să mai repet cele spuse la problema album. Este evident că problema generează inversiuni de valori.

Observație importantă: dacă nu ne prindeam cum să comparăm două numere maximale de 1000 de cifre folosind vectori de frecvență puteam să folosim o metodă greșită: formam numerele efectiv, folosind tipul long long. Această soluție, greșită, ia în mod incredibl 80p, adică două treimi din punctajul acordat cerinței 2. Înțeleg ideea de a da punctaje rezonabile pentru soluții rezonabile, dar 80p este prea mult, chiar și jumate este mult. O treime ar fi normal, poate, caz în care ar fi trebuit ca punctajul pentru această soluție să fie 60p.

Soluție forță brută optimizată

O primă optimizare evidentă este de a citi cifrele drept caractere, cu fgetc(). Vom obține o viteză de citire mărită de patru ori. Deoarece citim circa un megaoctet de date, nu putem neglija cîștigul de timp.

Dar optimizarea cea mai importantă vine din altă parte. Mare parte din timpul petrecut în forța brută este recalculînd vectorii de frecvență. În fapt, ei se pot recalcula incremental, în O(1). Cum?

Cînd "deplasăm" fereastra de m elemente:

  • Adunăm la vectorul de frecvență cifra care intră în fereastră.
  • Scădem din vectorul de frecvență cifra care iese din fereastră.

Recalcularea vectorului de frecvență este, astfel, O(1). Rămîne însă comparația lor, acel factor de Σ care nu se mai poate ignora. Complexitatea rezultată este O(n·Σ). Numărul de operații este 500000·10, adică 5 milioane. Este clar că această soluție se va încadra lejer în timp.

Soluție optimă

Cîtă memorie folosim în soluția anterioară?

Desigur O(n). Putem mai bine? Da. Nu avem nevoie să memorăm toate cifrele, ci doar o fereastră de m cifre. În ea putem depune pe rînd cifrele de la intrare. Odată ce ajungem la finalul ferestrei o vom lua din nou de la început, suprascriind cifrele care nu mai sînt acum necesare.

Această structură de date se numește coadă și vom învăța despre ea anul următor.

Această soluție folosește atît de puțină memorie, circa 1000 de caractere, încît este substanțial mai rapidă ca forța brută optimizată (de circa două-trei ori), deoarece acel vector de caractere încape complet în cache-ul L1, memoria cea mai rapidă a procesorului. Pe lîngă aceasta, o soluție care nu risipește memorie este întotdeauna mai bună, nu? :-)

Vă sugerez ca la temă să implementați această soluție, deoarece vă va solicita la maxim, pregătindu-vă astfel pentru ONI.

Atenție la optimizări simple ce vă pot aduce mari îmbunătățiri la această soluție:

  • Citire cu caractere
  • Comparație vectori folosind o santinelă (un test per element în loc de două)
  • Copiere vector în vectorul maxim doar de la poziția care diferă, pe care o știm de la comparația anterioară

Constatări în urma analizei problemei maxim2

Constatări grave:

  • Problema induce elevii în eroare: enunțul ne spune că este necesară o soluție rapidă (deci complexă), dar testele permit și soluții simple, forță brută.
  • Chiar și setînd timpul problemei la o treime din timpul acordat în concurs, cu soluția simplă, forță brută, se lua punctaj maxim, 100p. Dar acest lucru nu se putea deduce din enunț! În fapt nu merita să găsești un algoritm bun, ci doar cel mai simplu posibil. Testele favorizau, astfel, elevii slabi și defavorizau elevii buni.
  • Nu există teste cu limitele din enunțul problemei, ceea ce este foarte grav. Cele mai mari teste sînt la o cincime ca număr de operații față de testele maximale, ceea ce, împreună cu timpul foarte mare, permite unei soluții simple, forță brută să ia punctaj maxim.
  • Problema inversează astfel valorile între elevii buni și cei medii, avantajînd un elev mediu, care nu caută o soluție superioară, ci una simplă, mult mai greu de greșit, în același timp cîștigînd timp de lucru pentru cealaltă problemă.
  • Acest lucru se vede și din clasamentul de la OJI: patru dintre elevii clasați în primele zece locuri la faza națională de anul trecut au luat scor slab la această problemă: Ilie, Asgari, Nicola, Nicu.
  • Una din soluțiile oficiale, chiar cea a autoarei, pică teste maximale la timpul de executare, deci este incorectă.

Alte constatări îngrijorătoare:

  • O soluție elegantă este de peste o sută de ori mai rapidă, dar nu se poate diferenția de cea simplă, brută, ea luînd tot punctaj maxim, 100p.
  • Între sursele oficiale nu se află nici una optimă, nici ca timp și nici ca memorie. Ce exemplu dăm elevilor?
  • Unele soluții ale comisiei sînt mai lente decît forța brută scrisă îngrijit, cum ar fi una din soluțiile autoarei, prof. Rodica Pintea, care pică teste maximale.
  • Cu o soluție simplă, forță brută scrisă îngrijit, se putea lua punctaj maxim, 100p. Mult prea mult! Trebuia ca măcar 10p să fie păstrate pentru o soluție elegantă, pentru care elevul bun s-a chinuit.
  • Un test maximal ar fi necesitat 500 milioane de operații. Testul maxim al problemei necesită doar 100 milioane de operații, de cinci ori mai puțin.
  • Testele aveau nereguli, atît în .in cît și în .ok:
    • Linii goale în plus
    • Lipsă \n la finalul ultimei linii
  • Nici una din nereguli nu era gravă, cum ar fi fost dacă între două cifre din șir am fi avut mai mult de un spațiu.

Temă

Tema 25 clasa a 6a

  • album dată la OJI 2019 clasa a 6a
  • maxim2 dată la OJI 2019 clasa a 6a
  • cutii1 dată la ONI 2003 clasa a 8a
  • pește dată la ONI 2017 clasa a 6a

Atenție! La această temă se vor adăuga problemele de la concursul ce va urma duminică.

Rezolvări aici: [2]