Clasa VII/VIII lecția 16 - 20 ian 2015

Tema - rezolvări

Rezolvări aici [1]

Clasa a 8^a: discuţii despre rezolvările la zona şi bizar.

Lecţie

Mulţimea maximă de intervale neintersectante pe o axă

Enunţ

Problemă: dată o submulţime de N intervale [a_i, b_i] să se găsească o submulţime maximală a acestei mulţimi care conţine doar intervale disjuncte (neintersectante).

Idei de soluţie

Această problemă apare destul de des la olimpiade, deghizată într-o formă sau alta. Deşi pare o problemă grea, în realitate ea se rezolvă uşor. O primă idee ar fi să încercăm să ordonăm intervalele după punctul de început, apoi să le luăm în ordine, unul cîte unul. Pentru fiecare interval ne întrebăm dacă îl intersectează pe cel anterior. Dacă da, îl aruncăm şi mergem mai departe. Dacă nu, îl adăugăm la submulţime şi îl reţinem ca interval ultim. Această soluţie nu funcţionează şi e destul de evident de ce: am putea avea un prim interval foarte lung, care acoperă toate celelalte intervale.

Cu toate acestea rezolvarea nu e total greşită. În fapt, ea aproape funcţionează! Are nevoie doar de o modificare ce se impune, analizînd contraexemplul anterior: de ce nu este bun acel prim interval foarte lung? Deoarece el se termină după celelalte. Şi atunci ne putem întreba, în mod natural, ce s-ar întîmpla dacă am alege intervalul care se închide primul, nu care începe primul? Desigur că acest algoritm funcţionează. Vă las vouă să vă luptaţi cu demonstraţia, care decurge cam aşa: să presupunem că soluţia generată de acest algoritm nu e optimă. Înseamnă că există o altă soluţie cu mai multe intervale. Acea soluţie trebuie să difere undeva faţă de cea găsită de noi. Mergeţi pe această cale şi trebuie să ajungeţi la o contradicţie cum că soluţia optimă nu poate avea mai multe segmente.

Soluţie

Care este algoritmul, în mare?

1. Iniţial mulţimea M este vidă.
2. Ordonează crescător intervalele după punctul de închidere.
3. Consideră ultima închidere la minus infinit.
4. Pentru fiecare interval, în ordine:
   1. Dacă el conţine ultima închidere
      1. Ignoră-l.
   2. Altfel
      1. Selectează intervalul curent şi adaugă-l la mulţimea M.
      2. Setează ultima închidere pe închiderea intervalului selectat
5. Afişează mulţimea M.

Ce se întîmplă dacă avem mai multe intervale care se termină în acelaşi punct? Atunci putem reţine intervalul cel mai mic. De ce? Deoarece este cel mai convenabil. Să presupunem că soluţia maximală conţinea un alt interval care se termina în acel punct. Atunci putem înlocui acel interval cu intervalul cel mai mic, obţinînd o altă soluţie maximală.

Considerente de implementare

Implementarea directă: memorăm intervalele ca perechi, prin capetele lor. Sortăm perechile după capătul din dreapta. Apoi facem o parcurgere a perechilor. Această implementare necesită O(N log N) timp şi O(N) memorie.

Implementare relaxată: atunci cînd coordonatele sînt suficient de mici astfel încît să putem folosi un vector care să memoreze un întreg pentru fiecare coordonată, putem încerca o abordare mai simplă: Nu memorăm intervalele. Ci, pentru fiecare interval [a_i, b_i], vom seta inceput[b_i] = a_i. Cu alte cuvinte vom memora capetele stînga la poziţia capetelor dreapta. Apoi parcurgem vectorul în ordine, acoperind segmentul de coordonate care acoperă toate intervalele, testînd dacă elementul de la poziţia curentă în vector este mai mic decît ultima închidere memorată. Dacă nu, atunci selectăm intervalul şi mutăm ultima închidere la poziţia curentă în vector. Trebuie să avem grijă la următoarele:

• Să iniţializăm vectorul de coordonate cu o valoare distinctă de capete de interval. Matematic am putea să le iniţializăm cu minus infinit, astfel încît să nu fie selectate niciodată.
• Atunci cînd "aşezăm" intervalele pe vector să avem grijă ca dacă găsim deja o valoare în vector să o înlocuim numai dacă cea curentă este mai mare (intervalul este mai mic).

Această soluţie necesită O(N + CMAX) timp şi memorie, CMAX fiind coordonata maximă. De aici rezultă cînd o putem folosi: atunci cînd CMAX este suficient de mic.

Generalizare

Putem generaliza această problemă: să se calculeze mulţimea maximală de dreptunghiuri neintersectante. Sau de paralelipipede. Sau de paralelipipede n-dimensionale. Cum se rezolvă aceste probleme? Din nefericire aceste probleme fac parte dintr-o clasă de probleme numite NP-hard, pentru care nu se cunoaşte o soluţie bună.

Temă

Clasa a 7-a

• Tema 16 clasa a 7^a
  • char dată la ONI 2010 clasa a 7^a
  • baloane dată la Olimpiada pe şcoală 2012, Clasele 11-12
  • macheta dată la ONI 2011 clasa a 8^a
• Opţional: tema clasei a 8^a, care constă din două probleme date la barajul de gimnaziu.

Clasa a 8-a

Tema 16 clasa a 8^a

• dartz dată la ONI 2010 baraj gimnaziu
• flori 2 dată la ONI 2010 baraj gimnaziu

Rezolvări aici [2]