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

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.

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? :-)

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!

Rezolvări aici: [1]

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2018-2019/2019-03-14-clasa-6-lectie-info-25-720p.mp4</html5media>

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 6^a.

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(Σ²) 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·Σ²·log MAXS).

Se încadrează în timp? Să facem înlocuirile: știm că Σ² 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·Σ²·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(Σ²). 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(log²MAXS). Soluția va avea complexitatea O(n·log²MAXS). 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 6^a.

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 6^a

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

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

Rezolvări aici: [2]