Enunțul problemei multimi, de clasa a 10-a, dată anul acesta la ONI, se găsește pe PbInfo și InfoArena.

Rezumat multimi

În această problemă ni se dau n mulțimi scrise sub forma A=x-y/z. Asta înseamnă că mulțimea A este o secvență a unei progresii aritmetice cu primul termen x și rația z, ultimul termen al ei cuprins în A fiind y. Trebuie să evaluăm o expresie care operează cu mulțimile date, ce poate conține operatori de reuniune (+) și de intersecție (*), cât și paranteze. Mai exact, trebuie să afișăm cardinalul și elementele mulțimii obținute.

Soluție multimi

Abordarea mea în timpul concursului a fost să evaluez expresia în mod obișnuit, folosind o două stive. Șmecheria era să rețin operanzii (mulțimile) cât mai eficient, încât să nu depășesc memoria în timpul rulării programului (ceea ce n-aș fi putut face cu vectori statici) și să pot insera și căuta elemente cât mai repede. Soluția era evident un treap, adică set-ul din STL. Această soluție mi-a adus 60 de puncte. Practic, asta e metoda brută, dar nu mulți de a 10-a știu să folosească STL. Și sigur cei care nu știu STL nu știu nici să implementeze un treap de la 0 😉

Soluția de 100 de puncte constă în a determina care dintre elementele reuniunii mulțimilor date se regăsesc și în mulțimea finală. Fiecărei mulțimi x îi putem asocia un bit 1 dacă elementul y îi aparține, respectiv 0 dacă nu. Având în vedere că mulțimile sunt de fapt secvențe de progresii aritmetice, putem determina în $O(1)$ dacă y ∈ x. Acum, pentru a afla dacă y îi aparține și mulțimii finale, adaptăm expresia dată astfel: Înlocuim numele mulțimilor cu biții respectivi și operatorii pentru mulțimi cu operatorii logici corespunzători (sau pentru reuniune, și pentru intersecție).

De exemplu, avem elementul 1 și mulțimile A = {1, 2, 3}, B = {3, 7}, C = {1}, D = {1, 5, 9}, iar expresia este A * C + B * (A + D). Vom calcula valoarea expresiei 1 && 1 || 0 && (1 || 1). Vom obține 1, și într-adevăr, elementul 1 îi aparține mulțimii {1, 3}.

Totuși, algoritmul nu este suficient de eficient, pentru că este posibil să parsăm expresia de prea multe ori. Datorită faptului că numărul maxim de mulțimi este de doar 16, putem precalcula valoarea expresiei pentru toate configurațiile de biți posibile, adică 216 – un număr decent.

În implementarea de mai jos am folosit operații pe biți pentru eleganță în construirea configurațiilor. Tot secretul problemei era să observăm că putem transforma operațiile pe mulțimi în operații logice la nivel de elemente.

Sursă C++ multimi

Dacă ai vreo nedumerire cu privire la problema multimi, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!