Clasa a VII-a lecția 25 - 27 feb 2020

From Algopedia
Revision as of 13:28, 22 October 2021 by Mihai (talk | contribs) (→‎Soluție)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Anunțuri

  • Voi organiza un concurs duminică 1 martie la ora 15:00. Concursul va avea trei probleme și va dura 4.5 ore. Succes!
  • Nu mi-am dat seama că problema maximumsum este vizibilă, ea nu trebuia să fie. Unii din voi ați pîndit submisiile mele și ați aflat din timp problema de concurs. Un nou mod de a trișa: pîndim ce trimite Frâncu înainte de concurs, poate reușim să cîștigăm un avantaj. Felicitări, ați reușit. Cine are punctaj mare la această problemă și zero la cub (la care a avut 3 ore) este în colimatorul meu (ce-o fi ăla) :-). Mi-aș fi dorit să investiți acel efort în învățare și rezolvarea mai multor probleme, nu în pîndirea monitorului de task-uri.

Fulgerică - rezolvare

Problema cere să memorați valori asociate cu numere și să afișați răspunsuri la întrebări de forma "ce valoare este asociată cu un număr?"

Comentarii fulgerică 4 - 6 feb 2020

  • Mulți dintre voi nu înțelegeți conceptul de limite ale întregilor, predate în clasa a cincea. Credeți că:
    • Putem fenta unsigned short int să stocheze o valoare în plus, recte 65536.
    • Putem fenta unsigned short int să stocheze -1.
    • Putem fenta short int să meargă totuși pînă la 65535.
    • Putem fenta un int să stocheze 100 000·65536 valori.
  • Mulți aveți calcule total greșite de necesar de memorie.
  • Mulți ați căutat binar valorile x, dar nu v-ați dat seama că inserarea este liniară. Nu înțelegeți căutarea binară.
  • Mulți ați uitat că vectorul trebuie resetat între teste. Ar fi fost fatal la olimpiadă.
  • Mulți ați ignorat faptul că resetarea unui vector de 50 milioane de elemente ia timp. Dacă o faceți pentru fiecare test o veți face de zece ori. Aceasta înseamnă 500 milioane de operații ce nu încap în 0.2s.

Clasament

Nr. Nume F1 F2 F3 F4 Total Punctaj
Concursuri
1 Rebengiuc 10 100 100 90 300 4
1 Tatomir 90 45 70 95 300 6
3 Petrescu 100 80 75 0 255 33
4 Ghica 85 95 50 motivat 230 17
5 Ipate 100 50 70 0 220 43
6 Mușat 0 95 95 0 190 5
6 Voicu M 100 15 75 0 190 8
8 Dobre 95 15 70 0 180 14
9 Iordache 100 10 50 13 173 25
10 Ilie 0 15 50 80 145 2
10 Rughiniș 15 20 100 10 145 20
10 Voicu T 0 80 65 0 145 3
13 Petcu 5 14 100 15 134 9
14 Mocanu 0 15 95 11 121 23
15 Asgari 0 10 100 0 110 1
16 Burac 0 0 95 5 100 21
17 Nicu 0 90 0 5 95 10
18 Badea 10 15 50 10 85 15
19 Cojocariu 0 absent 70 5 75 30
20 Nicola 0 50 0 13 63 27
21 Calotă 0 10 35 11 56 16
22 Aizic 0 10 35 10 55 32
22 Dimulescu 0 10 30 15 55 13
22 Fares 0 45 10 0 55 7
25 Ștefănescu 0 15 35 0 50 18
26 Benescu 0 5 35 9 40 31
27 Popescu 0 0 35 motivat 35 12
28 Marcu 5 10 5 motivat 20 24
28 Stancu 0 20 0 0 20 34
30 Grecu 0 18 0 motivat 18 19
31 Chivu 0 5 0 7 12 37
32 Cadîr 0 10 0 lipsă 10 35
32 Teodorescu 0 10 0 0 10 22
34 Hossu 0 motivat 0 0 0 36
34 Togan 0 0 0 0 0 11
  • Liniile verde deschis arată copii clasați semnificativ mai bine decît în clasamentul concursurilor.
  • Liniile verde închis arată copii clasați mult mai bine decît în clasamentul concursurilor.
  • Liniile roșu deschis arată copii clasați seminificativ mai rău decît în clasamentul concursurilor.
  • Liniile roșu închis arată copii clasați mult mai rău decît în clasamentul concursurilor.

Acest clasament arată foarte diferit de clasamentul concursurilor. De ce oare?

Tema - rezolvări

Rucsac1

Problema rucsac1 este o aplicație a ceea ce am învățat la curs.

Comentarii generale

  • Nu puteam stoca matricea, nu aveam spațiu. Cu toate acestea unii din voi au încercat și au obținut MLE. Buni matematicieni!
  • Putem stoca doar o linie din matrice. Unii din voi au stocat două. Nu este incorect, dar este și mai ineficient, iar codul se mărește.

Șiruri2

Problema șiruri2 este o aplicație a ceea ce am învățat la curs - distanța edit (Levenshtein).

Comentarii generale

  • Pescuitul cam mare pentru o problemă cu o implementare scurtă. Mușat, ești pescar campion, trimiți la arhivă să eviți penalizările! Bravo! Ți-ai cîștigat mărețul punctaj zero la problemă și un avertisment! Continuă așa și ne vedem mai rar un pic.
  • Nu era necesar să stocați matricea. Puteați calcula cîte o linie.
  • Nu era necesar să stocați două linii. Este deajuns să păstrați elementul anterior din linie înainte de modificare.
  • Avem nevoie de distanța de la șirul vid la alte șiruri, nevide. Pentru simplitate era bine să folosiți vectorii de caractere începînd cu poziția 1. Altfel trebuia să ajustați indici. Formula de recurență folosea indici începînd cu 1 (speram că este evident).
  • În general formula de recurență nu se implementează exact ca în definiție. Ea e un ghidaj matematic. Implementarea cere modificări pentru eficiență.
  • Nu denumiți matricea de costuri dp[][]. Am mai discutat despre asta. E ca și cum am denumi variabilele contor sau acumulator. Denumiți-o după rolul ei, în cazul nostru este o distanță, deci dist[][] sau d[][] era în regulă. Nu fiți olimpici, vă rog.
  • Unora din voi v-a dat de furcă conversia de la litere mari la litere mici (sau invers). Pare că ați uitat lucrul cu caractere, poate ar fi bine să îl revedeți înainte de olimpiada județeană.

Comentarii individuale

  • Dobre: ai avut probleme cu indicii, de la zero vs unu.
  • Mușat: ai pescuit pînă la moarte. Mai grav, ai trimis soluții la arhivă pentru a evita penalizările pescuitului sportiv. Avertisment și zero la problemă.
  • Nicu: ai confundat indicii din formulă. În formulă distanța de la șirul vid (lungime 0) la orice șir este lungimea acelui șir. Zero are sens de număr de elemente, vid. Tu folosești indicele zero pentru poziție, deci șirul nu este vid. De aceea ratezi teste.

Rucsac

Problema rucsac este o aplicație a numărării folosind subprobleme suprapuse.

Comentarii generale

  • Timpul este destul de strîns.
  • O implementare ce folosește operația '%' este riscantă. Se va încadra în timp dacă restul programului este scris eficient, altfel nu.
  • Modulo se poate evita observînd că adunarea poate depăși împărțitorul cu cel mult o valoare a sa, pe care o putem scădea.
  • Formula de recurență nu trebuie implementată literal. Sînt necesare modificări pentru eficiență, de exemplu santinele, sau valoarea inițială la începutul vectorului. Altfel vom face teste în plus la fiecare element calculat.
  • Nu aveați nevoie să memorați două linii din matrice. Completarea liniei de la coadă către cap ne asigură că nu vom avea nevoie de elemente din aceeași linie (zona deja calculată).

Comentarii individuale

  • Benescu: n-are sens să faci parsing.
  • Mocanu: nu ei nevoie de long long. Ai testat depășirea lui 999979, bun! Dar apoi faci tot modulo, cînd puteai să-l scazi.

Cifreco

Problema cifreco a fost dată la ONI 2012 baraj gimnaziu. Ea este una de numărare a soluțiilor pe baza problemelor suprapuse, confundată adeseori cu programarea dinamică.

Cub

Problema cub a fost dată la Olimpiada locala 2010, clasele 11-12. Este o problemă clasică, extinsă de la două dimensiuni la trei dimensiuni. Mare parte din dificultatea acestei probleme constă în implementarea ei.

Maximumsum

Problema maximumsum este problema clasică a subvectorului de sumă maximă extinsă la două dimensiuni.

Rezolvări aici [1]

Lecție - programare dinamică, continuare

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2020-02-27-clasa-7-lectie-info-25-720p.mp4</html5media> Să vedem exemple de probleme de programre dinamică și probleme suprapuse date la olimpiadă.

Faleza

Problema faleza a fost dată la ONI 2017 clasa a 6a. Ea este o problemă de un anumit gen, care se întîlnește din cînd în cînd la olimpiadă: probleme mascate, care au o soluție medie sau chiar grea, fără programare dinamică, dar care admit o soluție banală cu programare dinamică.

Atîta vreme cît programarea dinamică nu este în programa de olimpiadă de clasa a șasea, după părerea mea genul acesta de probleme nu sînt bune de concurs, deoarece încurajează dopajul, nu gîndirea algoritmică și aprofundarea cunoștințelor. În cazul problemei faleza cine știe programare dinamică o poate termina în 15 minute. Cine nu, va trebui să găsească un algoritm care nu e deloc evident (mai ales la casa a 6a), petrecînd, probabil, peste o oră.

Soluția comisiei

Iată soluția comisiei:

"Construim două tablouri pe care le notăm A și B, cu numerele din fișier, în A cele de pe o parte a falezei și în B cele de pe cealaltă. Pentru simplificarea implementării, dacă avem poziții i în care A[i] = 1 și B[i] = 1 putem să analizăm doar ce se întîmplă între două astfel de poziții consecutive.

Parcurgem element cu element și păstrăm mereu ultima poziție pe care se află o dală bună pentru șirul A respectiv pentru șirul B, alegănd, în funcție de acestea, modul de a completa dalele deteriorate.

Timpul de executare este liniar."

După părerea mea este puțin vagă. În mod cert e nevoie de o analiză care nu pare simplă.

Soluție cu programare dinamică

Să simplificăm puțin enunțul: se cere să reparăm cît mai puține dale pentru a se putea ajunge de la un capăt la celălalt. Cu alte cuvinte se cere un drum care să treacă prin cît mai puține dale rupte. Dacă vom schimba codarea dalelor, cele rupte cu 1 și cele întregi cu 0, rezultă că trebuie să găsim un drum de sumă minimă.

O observație simplă, dar esențială, este că drumul minim nu se va întoarce de la dreapta la stînga. Într-adevăr, este clar că nu are de ce. Putem, deci, calcula drumurile de la stînga la dreapta.

Drept care o definiție evidentă a problemei de programare dinamică este:

S[l][c] = suma unui drum de sumă minimă pentru a ajunge în punctul (l, c).

Demonstrație de optimalitate a subprobemelor o las în seama voastră, fiind simplă.

Formula de recurență este iarăși simplă:

  • Într-o dală de sus putem ajunge fie dinspre stînga, fie din jos în sus.
  • Într-o dală de jos putem ajunge fie dinspre stînga, fie din sus în jos.

Vom lua în considerare minimul dintre cele două variante.

Formula de recurență este:

Am considerat că D[l][c] este codificarea dalei din linia l și coloana c. Liniile și coloanele sînt numerotate de la 0.

Răspunsul cerut este minimul dintre S[0][n-1] și S[1][n-1].

Ce complexitate are această soluție?

Timpul este evident O(n).

Memoria ar putea fi O(1) dacă dalele ar fi date pe linii, nu pe coloane. Așa cum este enunțul sîntem obligați să le stocăm, ceea ce duce la memorie O(1). Putem însă refolosi matricea de dale pentru a calcula sumele minime. Drept care memoria va fi de 2n întregi, adică 800KB.

Exemplu

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

Dalele originale (0 = întreagă, 1 = ruptă):

1 1 0 0 0 1 1 1
1 1 1 1 1 1 1 0

Calculul drumurilor minime pe coloane, de la stînga la dreapta:

1 2 2 2 2 3 4 5
1 2 3 3 3 4 5 5

Poteci

Problema poteci a fost dată la ONI 2011 baraj gimnaziu.

Soluția comisiei

Fiind vorba de baraj, soluția este una bazată pe programare dinamică:

  • Pentru fiecare element din matrice vom calcula drumurile optime pînă la cele patru colțuri ale matricei.
  • Parcurgem matricea și determinăm acel element pentru care suma celor patru drumuri este maximă.

Pentru primul pas vom folosi programarea dinamică, o procedură apelată de patru ori. În fapt, vom calcula drumurile optime de la fiecare colț către toate elementele matricei. De exemplu, pentru distanța de la colțul (1, 1) la elementul (i, j) vom avea formula de recurență:

În final vom alege punctul din matrice (l, c) cu proprietatea:

Ce complexitate are această soluție?

Ea calculează patru matrice, deci atît timpul cît și memoria vor fi O(L·C). Mai exact, vom avea nevoie de patru matrice de elemente întregi de 1000 x 1000 elemente, circa 16MB, plus matricea originală de frumuseți, elemente short int, deci încă 2MB, total 18MB.

Soluție alternativă

O soluție care face mai puține calcule și folosește mai puțină memorie este următoarea.

Observație: perechea optimă de poteci va fi alcătuită din două poteci optime.

Într-adevăr, dacă una din poteci nu ar fi optimă, am putea alege o potecă mai bună care ar duce la o pereche mai bună.

De aici vine și ideea soluției: să calculăm potecile optime pentru cei doi și să alegem punctul de intersecție a lor. Pentru aceasta va trebui să calculăm nu doar frumusețile potecilor, ci și potecile în sine. La final vom calcula intersecția potecilor.

Ce complexitate are această soluție? Ea este, desigur, tot O(L·C) atît ca timp cît și ca memorie. Însă vom calcula doar două matrice, deci timpul se reduce aproximativ la jumate. Iar memoria necesară este de o matrice pentru frumusețile originale (2MB) și o matrice de drumuri (1MB). Pentru a calcula intersecția putem refolosi matricea de drumuri. Necesarul de memorie este, deci, de numai 3MB, comparat cu cei 18MB ai soluției anterioare. Putem reduce și mai mult memoria dacă folosim pentru stocarea drumurilor matrice de biți, caz în care în loc de 1MB vom folosi 125KB, iar memoria totală folosită va fi 2.12MB. Iar folosind algoritmul lui Hirschberg putem elimina complet matricea de drumuri, ceea ce duce la 2MB memorie necesară.

Concluzii:

  • Timpul se reduce la jumate.
  • Memoria se reduce la o șesime

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

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.

Zmax

Problema zmax a fost dată la ONI 2013 baraj gimnaziu.

Soluție cu programare dinamică

Singura soluție de 100p a comisiei este cu programare dinamică.

Vom defini următoarele subprobleme:

S[l][c] = cea mai mare sumă de elemente contigue aflate pe linia l, care se termină la coloana c
D[l][c] = cea mai mare sumă de elemente contigue aflate pe linia l, care încep la coloana c
N7[l][c] = cea mai mare sumă de elemente aflate în matrice în formă de cifra '7' care se termină la (l, c).
Z[l][c] = cea mai mare sumă de elemente aflate în matrice în formă de 'Z' a cărei linie de sus se termină la (l, c).
  • Primele două subprobleme se pot calcula folosind algoritmul clasic al lui Kadane.
  • Subproblema N7 se calculează pe baza subproblemelor S și N7, similar cu Kadane: putem continua 7-le existent, sau să începem unul nou.
  • Subproblema Z se calculează pe baza subproblemelor D și N7, similar cu Kadane: putem continua Z-ul existent, sau să începem unul nou.

Maximul din subproblema Z este răspunsul la cerință.

Alte probleme

Problema flori2 a fost dată la ONI 2010 baraj gimnaziu. Nu este o problemă foarte grea, dar are multe detalii.

Puteți găsi alte probleme căutînd pe varena după tagul "programare dinamică".

Tema

  • Tema 25 clasa a 7a
    • optim dată la ONI 2012 clasa a 8a
    • joc6 dată la ONI 2011 baraj gimnaziu
  • Cele trei probleme de la concurs se vor adăuga la temă
  • Opţional: problemele menționate în această lecție:
  • Opţional: alte probleme de programare dinamică sau probleme suprapuse.

Rezolvări aici [2]