Clasa VI/VII/VIII lecția 26 - 19 mar 2013

Anunț 1

Aţi început iar să nu vă mai faceţi temele. După olimpiada pe ţară voi restructura cercul de informatică. Voi primi noi elevi şi voi da afară pe unii existenţi. Voi ţine cont şi de activitatea voastră la cerc, incluzînd temele. Dacă vreţi să rămîneţi la acest cerc, faceţi-vă temele. Dacă şarmul meu nu v-a convins, poate acest argument vă convinge. Aţi fost preveniţi.

Anunț 2

Atenţie! Ora concursului s-a schimbat! Concursul va incepe la 10:30 dimineata, mulţumită instructajului pentru olimpiada de matematică programat în ultima clipă peste acest concurs.

Pentru cei ce v-ați calificat la olimpiadă și nu numai, voi încerca să organizez un concurs săptămîna aceasta, vineri la ora 10:30. Dacă nu sînteți de la liceul Tudor Vianu, București, dar sînteți clasa 6/7/8 și vreți să vă măsurați forțele față de voi înșivă sau față de cei de la Vianu, vă propun să vă înscrieți. O mică competiție colegială nu are cum să dăuneze, nu? Vă puteți înscrie la concursuri aici:

• Concurs vineri 22 martie, ora 10:30 clasele 6/7/8 înscrie-te aici

Toate clasele

Rezolvare problema extraterestri

Problema extraterestri poate părea foarte complicată, dar, în realitate, ea are o rezolvare foarte simplă, de cîteva linii. Soluție aici [1]

Precalculare

La problema extratereştri se remarcă folosirea unui vector special, în care am precalculat anumite valori pe baza cărora am calculat vectorul final. Această tehnică se aplică în multe alte probleme. Să luăm nişte exemple.

Ciurul lui Eratostene

V-aţi gîndit vreodată că ciurul lui Eratostene este de fapt o precalculare a unui vector de frecvenţă, care, pentru fiecare număr p, v[p] ne spune dacă p este prim? Complexitatea este O(n log log n).

Suma între i şi j

În multe probleme apare următoarea subproblemă: avem un vector de n elemente întregi, să se răspundă la multe întrebări de forma care este suma elementelor vectorului între poziţiile i şi j?. În acest caz vom precalcula o structură de date auxiliară, şi anume un vector s, astfel încît s[i] este suma elementelor de la 0 pînă la i. El se mai numeşte şi vectorul sumei prefixelor lui v. Construcția acestui vector se poate face liniar deoarece avem relaţia s[i] = s[i+1] + v[i].

Odată calculat acest vector putem răspunde în timp constant la întrebări. Suma elementelor între i şi j este s[j] - s[i-1].

Suma între (i, j) şi (ii, jj)

Este problema anterioară extinsă la matrice: avem o matrice de numere întregi şi întrebări de forma: care este suma elementelor matricei în dreptunghiul care are drept colţuri opuse (i1, j1) şi (i2, j2)?. Această problemă apare în problema puncte5 dată la barajul de gimnaziu în 2012. Am discutat despre ea în lecţia 6. În mod similar vom precalcula o matrice auxiliară cu suma elementelor matricei originale între (0, 0) şi (i, j). Ea poate fi calculată în timp constant per element, astfel:

Calcul matrice sume parțiale în dreptunghiuri care pornesc în origine

s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + m[i][j]

Odată calculată matricea s putem răspunde în timp constant la întrebări. Suma elementelor între (i, j) şi (ii, jj) este:

S = s[ii][jj] - s[ii][j-1] - s[i-1][jj] + s[i-1][j-1]

Calcul suma numerelor în orice dreptunghi

Numărul de biţi 1 într-un întreg

Cum putem calcula numărul de cifre 1 din reprezentarea în baza 2 a unui număr?

• Direct: shift and mask.
• Folosind expresia x & (x - 1).
• Cu precalculare: ţinem un vector în care elementul v[x] este numărul de biţi 1 din reprezentarea în baza 2 a lui x.
• Gîndiţi-vă la un algoritm fără vectori, dar mai rapid decît O(nr. biţi).

Exemple de probleme cu precalculare

• puncte5: necesită precalcularea sumelor parţiale ale unei matrice.
• paisprezece: necesită precalcularea unui vector al primelor 17 numere prime, precum şi a ciurului lui Eratostene.
• intervale: necesită precalcularea ciurului lui Eratostene precum şi a sumelor parţiale ale numărului de divizori primi.

Concluzii

• Precalcularea foloseşte atunci cînd avem de răspuns la mai multe întrebări costisitoare. Aceste întrebări pot fi explicite, cerute de enunţ, sau implicite, decurgînd din metoda de rezolvare, ca la problema puncte5.
• Precalcularea poate folosi şi atunci cînd numărul de întrebări este mult mai mare decît numărul de răspunsuri posibile, caz în care putem precalcula toate răspunsurile într-un tabel înainte de a răspunde la întrebări.
• Precalcularea foloseşte o structură de date adiţională şi memorie suplimentară. Uneori putem economisi memorie folosindu-ne chiar de structura de date iniţială.

Problema reginald

Discuţie despre rezolvarea problemei reginald.

Clasa a şasea

Lucraţi la problema minute la vianuarena.

Clasa a şaptea şi a opta

Despre structura de date heap.

Aplicaţii:

• Heapsort.
• Selecţie în O(n + k log n).
• Selecţie în O(n log k).
• Interclasarea a k vectori de lungime n.
• Intervale colorate pe o dreaptă.

Teme

Teme clasa a șasea

• Concuraţi la concursul de vineri.
• Terminați problemele de la concursul de vineri.
• Terminaţi problema extraterestri.
• Opţional: problema reginald.

Teme clasa a șaptea

• Concuraţi la concursul de vineri.
• Terminați problemele de la concursul de vineri.
• Terminaţi problema extraterestri.
• Terminaţi problema reginald.
• Probleme date la baraj în anii trecuţi.

Teme clasa a opta

• Concuraţi la concursul de vineri.
• Terminați problemele de la concursul de vineri.
• Terminaţi problema extraterestri.
• Terminaţi problema reginald.
• Probleme date la baraj în anii trecuţi.
• Opțional**(foarte grea): teren.