Clasa a 7-a Lecția 29: Discutarea problemelor de la OJI 2024

Înregistrare video lecție

Load video

YouTube

YouTube might collect personal data. Privacy Policy

ContinueDismiss

Problema Parking

Problema Parking a fost dată la OJI 2024 Clasa a 7-a.

Când vedem o astfel de problemă primul gând trebuie să fie: oricât de simplă ar fi soluția, chiar și cea mai simplă soluție va fi delicat de implementat și nu va fi scurtă. Este genul de problemă care, la concurs, ia timp. Dacă avem o altă problemă mai simplu de implementat, este bine să lăsăm parking la urmă.

Deoarece enunțul este semi-încâlcit, să clarificăm anumite lucruri:

• O mașină iese într-o serie dacă și numai dacă în direcția aleasă de deplasare nu există nici o altă mașină, până la ieșire.
• Decizia de ieșire sau nu se face static: într-o configurație de mașini toate se uită către ieșire în același timp. Dacă o văd, adică nu este blocată de o altă mașină, atunci ies.
• Mașinile care pot ieși, ies. Nu ne punem probleme că se pot intersecta cu alte mașini pe drum. Din punctul nostru de vedere este ca și cum ele dispar din parcare subit.

Concluzie: în fiecare serie trebuie să decidem ce mașini văd o ieșire. Ele vor dispărea din parcare, apoi trecem la următoarea serie.

Soluție forță brută

Sper că o soluție rezonabilă, ce va lua multe puncte, este accesibilă. O idee imediată este să reprezentăm totul într-o matrice bordată, cu numere diferite pentru vid (nimic), mașină orizontală, mașină verticală sau zid. Apoi vedem ce putem rezolva parcurgând matricea. Pentru o mașină oarecare din matrice vrem să răspundem la întrebările:

• Există ieșire în vreun capăt al liniei/coloanei mele? Putem răspunde în O(1) la această întrebare, verificând valorile de pe bordură, în cele două capete.
• Există vreo altă mașină între mine și capetele de zid? Și la această întrebare putem răspunde în O(1), dacă în parcurgerea matricei memorăm numărul de mașini întâlnite pe drum pe acea direcție. Conceptual, cel mai simplu, ne putem imagina că facem patru parcurgeri, câte una pentru fiecare direcție.

Combinănd cele două întrebări putem răspunde la întrebarea dacă o mașină iese sau nu: o mașină iese dacă există ieșire și numărul de mașini din față este zero.

Bun, deci putem calcula mașinile ce ies într-o serie în O(n²). Le putem apoi șterge din matrice.

Deoarece avem maxim s = 10 000 serii rezultă un algoritm O(n²·s) care va efectua circa 10 miliarde de operații. E clar că va depăși timpul pentru teste mari, dar probabil va lua peste 40p dacă îl implementăm eficient. De exemplu observăm că matricea poate fi memorată cu elemente caracter, ceea ce reduce memoria necesară la 1MB, destul de puțin.

Soluție

Este clar că orice soluție care va parcurge matricea la fiecare serie nu este bună. Mai mult, nu putem nici să parcurgem toate mașinile la fiecare serie. Reducem complexitatea de zece ori, deoarece mașinile sunt de zece ori mai puține decât elementele matricei, dar și un miliard de operații este prea mult. Cu toate acestea, dacă nu ne vine altă idee, e clar că vom lua mai multe teste cu această optimizare.

Pentru o soluție mai bună să observăm următoarele:

• Pe orice ieșire din parcare va ieși cel mult o mașină pe serie.
• Numărul de ieșiri din parcare este O(n).
• Drept care numărul de mașini ce poate ieși într-o serie este O(n).

În lumina acestor observații pare foarte risipitor să parcurgem O(n²) mașini pentru a alege O(n) dintre ele. Oare nu putem să verificăm doar acele O(n) mașini care au șanse să iasă?

Ba da, dacă procedăm invers: în loc să ne uităm din mașină către ieșire, ne vom uita dinspre ieșire spre mașini. Mai exact, pentru a determina ce mașini ies într-o serie, folosind matricea anterioară, procedăm astfel: pentru fiecare ieșire posibilă vom parcurge linia sau coloana ei până ce dăm de o mașină sau de un zid.

Ce complexitate are acest algoritm? Din păcate costul unei serii este tot O(n²). Pare că nu am avansat. Sau poate da?

Ce observăm? Că de la o serie la alta, când ne "uităm" dinspre ieșire, vom vedea fie aceeași mașină ca în seria trecută, fie o mașină mai departe, în spate. Deci nu are sens să repetăm căutarea pornind de la ieșire, din nou. Vom porni de unde am rămas la seria anterioară! Pentru aceasta avem nevoie de patru vectori de indici în linia sau coloana respectivă. Astfel, fiecare ieșire va genera O(n) calcule pe tot parcursul simulării (analiză amortizată).

Detalii importante de implementare:

• Nu putem șterge mașinile din matrice imediat ce constatăm că pot ieși. De ce? Deoarece s-ar putea să deschidem drumul unei mașini care nu ar fi ieșit în acea serie.
• Nu putem nici să le numărăm pur și simplu. Aceeași mașină poate ieși atât prin stânga cât și prin dreapta. Mașinile trebuie marcate cumva pentru a nu le contoriza de două ori.
• La final de serie ele trebuie cumva șterse din matrice.

O soluție rezonabilă este ca, atunci când dăm peste o mașină ce poate ieși, să o memorăm într-un vector de perechi linie/coloană și să o marcăm în matrice ca zid. La final de serie numărul de elemente din vector este numărul de mașini care iese. Parcurgem acel vector și zeroizăm elementele de la acea linie și coloană.

Pentru fiecare serie vom avea obligatoriu O(n) calcule, pentru parcurgerea ieșirilor, în total O(n·s) operații. La aceste calcule se adaugă cele O(n²) generate de jocul indicilor (analiza amortizată). Complexitatea totală este, deci, O(n·s + n²), circa 40 milioane de operații deoarece vom parcurge 4000 de elemente pe bordură. Partea frumoasă este că memoria nu se mărește semnificativ, avem nevoie doar de patru vectori de câte o mie de elemente de tip short, circa 8KB și de un vector de 4000 de perechi de elemente de tip short, circa 16KB.

O soluție posibilă în timp de concurs, nefactorizată tocmai pentru simplitatea codului, va avea circa 75 de linii de cod efectiv.

Problema Ron

Problema Ron a fost dată la OJI 2024 Clasa a 7-a.

Este o problemă două în una, cele două cerințe neavând nici o legătură una cu alta. Să le enunțăm cât mai simplu:

Dându-se n maxim 50 000 de intervale cu capete numere până în două miliarde să se determine:

1. Numărul maxim de pătrate de numere prime ce se află în interiorul unui interval.
2. Numărul de intervale contigue formate de intervale.

Ambele probleme sunt de manual. Nu prea avem ce gândi la ele, implementăm soluția studiată la curs.

Soluție cerința 1

O primă idee ar fi să calculăm un ciur al elementelor pătrate de numere prime. Dar acest ciur este prea mare, până în două miliarde.

A doua idee este să calculăm doar ciurul numerelor prime pâna la radical din două miliarde, apoi să extragem numerele prime și să stocăm într-un alt vector pătratele lor. Vom avea circa 45000 de astfel de numere. Apoi, pentru un interval dat, vom căuta binar capetele lui în acest vector. Este clar că această soluție se va încadra în timp, iar memoria necesară este mică.

La acest moment majoritatea se vor apuca de lucru, pe principiul n-am gândit aproape deloc, deci e bine. Și poate au și dreptate, la un concurs. Însă în viața reală ar fi bine să ne întrebăm: oare se poate mai bine?

Desigur, iar implementarea va fi și mult mai lejeră. Ce-ar fi să studiem capetele de interval, folosind bruma de matematică necesară? Oare ce se întâmplă dacă extragem radical din capete? Nu cumva noul interval va acoperi exact aceleași numere prime al căror pătrate sunt acoperite de vechiul interval? Matematica grea este ușoară! Doar ce ușoară este grea 🙂.

Soluția simplă: după calculul ciurului vom calcula sume parțiale pe acel ciur, pentru a putea răspunde repede la întrebări de forma câte numere prime se află într-un interval. Apoi, pentru fiecare interval de la intrare, vom întreba câte numere prime se află între radicalii capetelor.

Ce complexitate are această soluție? $O({\sqrt {x}}\log \log {\sqrt {x}})$ pentru ciur, unde x este coordonata maximă, 2 miliarde și O(n) pentru răspunsuri, total $(O({\sqrt {x}}\log \log {\sqrt {x}}+n)$. Vom avea circa 180 000 de operații pentru ciur și circa 2 milioane pentru întrebări (am considerat că radicalul se calculează în 200 de operații elementare). Deoarece citim circa 1MB de date, este clar că citirea va fi o mare parte din timpul de execuție.

Memoria necesară? Cea pentru sume parțiale pe ciur, $O({\sqrt {x}})$, mai exact 90KB.

Soluție cerința 2

Am văzut aici soluții nenecesar de complicate. Printre ele se află și soluția comisiei.

Să considerăm capetele de intervale ca fiind paranteze deschise sau închise. Dacă le vom plasa pe o axă la coordonata corectă, ce vom vedea? Că un interval contiguu va avea tot atâtea paranteze deschise cât și închise. Un interval neacoperit are proprietatea că numărul de parateze deschise de la stânga lui este egal cu cele închise.

Problema este echivalentă cu cea a parantezelor imbricate, făcută prin clasa a cincea, cred: câtă vreme numărul parantezelor deschise și încă neînchise este strict mai mare ca zero, suntem în interiorul unui interval contiguu. În momentul când cele două numere devin egale, se închide un interval contiguu și trebuie să adăugăm unu la soluție.

Avem, deci, un algoritm banal:

1. Sortăm capetele de intervale, memorând cumva tipul de capăt, închis sau deschis.
2. Pornim cu un contor de paranteze neînchise inițializat cu zero.
3. Parcurgem capetele în ordine crescătoare și pentru fiecare paranteză deschisă adunăm 1, pentru fiecare paranteză închisă scădem 1.
4. De fiecare dată când contorul devine zero adunăm 1 la rezultat.

Se pune întrebarea ce facem atunci când la aceeași poziție avem și paranteze deschise și închise. Dacă urmărim enunțul, capetele stânga sunt inclusive, cele dreapta exclusive. Ceea ce înseamnă că dacă un interval se termină la poziția x și altul începe la poziția x, ele vor fi unul în continuarea altuia și segmentul curent se continuă. Pentru a nu trece prin zero cu contorul nostru este necesar să tratăm capetele deschise înaintea celor închise.

Ca detaliu de implementare, pentru a nu sorta perechi, având nevoie de o valoare 0 sau 1, o putem adăuga la capătul de interval: îl înmulțim cu 2 și adunăm valoarea 0/1. Atenție, aceasta înseamnă că putem ajunge la valori de patru miliarde, depășind întregul. unsigned int to the rescue! 🙂

Ce complexitate are această soluție? E clar că timpul cel mai mare este cel de sortare: O(n log n). Din nou, numărul de operații fiind de circa 1.7 milioane operații, citirea va fi parte majoră din timpul de execuție.

Iar memoria? Stocăm 2n capete de interval, deci O(n), mai exact 400KB.

O soluție implementabilă în timp de concurs va avea circa 65 de linii de cod efectiv, din care circa 20 de linii pentru quick sort.

Tema 29

Să se rezolve următoarele probleme (program C trimis la NerdArena):

• Parking dată la OJI 2024 clasa a 7-a
• Ron dată la OJI 2024 clasa a 7-a

Accesează rezolvarea problemelor de la lecția 29