Link către problema Colecție

O primă metodă de rezolvare ar fi să stocăm aparițiile fiecărui număr într-un vector clasic de frecvență, însă realizăm că folosirea acestuia ar depăși limita de memorie impusă de problemă, fiind o soluție ineficientă.

O optimizare adusă soluției de mai sus constă în utilizarea a doi vectori caracteristici, în schimbul vectorului de frecvență. Știind că o vedere unică are un singur număr atribuit, e de ajuns stocarea a două apariții. Dacă o vedere apare de două sau mai multe ori, aceasta nu mai respectă condiția pentru a fi în colecție. Chiar și cu această optimizare, obținem tot 0 puncte fiindcă am consumat toată memoria.

Secretul este să folosim bitset în schimbul vectorului clasic caracteristic. Bitset este un vector cu elemente de tip bool, doar că fiecare element din acesta nu va ocupa un octet ci un bit, astfel consumându-se mult mai puțină memorie.

Pentru utilizarea acestuia este necesară includerea librăriei bitset #include <bitset>. Declararea se va face astfel:

bitset <N> nume; //N reprezentand numarul de elemente

Fiecare element al acestuia se accesează asemănător vectorilor și pot lua doar valorile de 0 sau 1, asemănător tipului de data bool.

#include <iostream>
#include <bitset> //Pentru folosirea bitset-ului este necesara includerea librariei bitset

using namespace std;

int main()
{
    //Declaram un bitset cu 100 de elemente
    bitset <100> E;

    //Elementele pot lua doar valorile de 1 sau 0 (la fel ca tipul de data bool)
    E[0]=1;
    E[3]=0;

    //Afisam valoarea
    cout<<E[0];

    return 0;
}

O implementare în C++:

#include <fstream>
#include <iostream>
#include <bitset>
#define NMAX 9000001

using namespace std;

ifstream in("colectie.in");
ofstream out("colectie.out");

bitset <NMAX> f1;
bitset <NMAX> f2;
int i,n,input,ap;

void Citire()
{
    in>>n;
    for(i=1; i<=n; i++)
    {
        in>>input;
        if(f1[input]==0)
            f1[input]=1;
        else
        {
            f2[input]=1;
        }
    }
}

void Afisare()
{
    for(i=1; i<=n; i++)
    {
        if(f1[i]==1 && f2[i]==0)
            ap++;
    }
    out<<ap;
}

int main()
{
    Citire();
    Afisare();
    return 0;
}

O altă variantă a soluției descrisă mai sus este implementarea hard-code a bitset-ului. Utilizăm doi vectori de tip unsigned int cu numele f1 și f2, fiecare având lungimea de n/32+1 elemente. Știm că fiecare element al vectorului are 32 de biți (un octet are 8 biți, iar știind că o variabilă de tip unsigned int ocupă 4 octeți, vom avea disponibili 8*4=32 biți per element). Astfel, un element din unul dintre cei doi vectori ia rolul de „vector caracteristic” cu 32 de elemente.

Ca exemplu, apariția numărului 3 se va afla în elementul f1[0], pe al 3-lea bit al acestuia. (3/32=0 – elementul în care se află bit-ul, 3%32=3 – al câtelea bit va fi marcat din acel element). Apariția numărului 33 se va afla în elementul f1[1], pe bit-ul 1 al acestuia. Deci formula generală pentru a determina atât poziția bit-ului în vector, cât și ce bit va trebui să schimbâm va fi:

X/32 – elementul vectorului în care se află bit-ul ce trebuie schimbat

X%32 – bit-ul ce va trebui să îl schimbăm

unde X reprezintă numărul vederii din colecție.

Pentru a verifica și a seta biții, ne vom folosi de propietățile operațiilor pe biți:

• Pentru a seta valoarea bit-ului i, vom folosi următoarea operație: n | (1<<i)
• Pentru a afisa bit-ul i, vom folosi următoarea operație: ( (n>>i) & 1))

Instrucțiunea (1<<i) se echivalează cu \({2}^{i}\).

Pentru ușurința realizării operațiilor de mai sus, vom stoca valorile puterilor lui 2 într-un vector cu 32 de elemente (după cum am menționat, fiecare element al vectorului de tip unsigned int are 32 de biți)

Împărțim fiecare element al vectorului de tip unsigned int într-un „vector caracteristic” fiecare având 32 de elemente.

Implementare în C++:

#include <fstream>
#define NMAX 313002

using namespace std;


ifstream in("colectie.in");
ofstream out("colectie.out");


//Stocam pozitia in vectorii caracteristici programati intr-un struct
struct {
    int vec;
    int bit;
}poz;

//Variabilele declarate global sunt initializate intotdeauna cu 0.

unsigned int op[33],n,input,rez, f1[NMAX],f2[NMAX];

void Power()
{
    //op se va folosi pentru operatii pe biti
    op[0]=1;
    for(short int i=1; i<=32; i++)
        op[i]=op[i-1]<<1; //SHL pentru viteza
}

void Citire()
{
    in>>n;
    for(int i=0; i<n; i++)
    {
        in>>input;
        //Calculam pozitiile in vector
        poz.vec=input/32;
        poz.bit=input%32;
        if(((f1[poz.vec]>>poz.bit) & 1)==0) //Verificam bit-ul
            f1[poz.vec] |= op[poz.bit];
            //echivalent cu:  f1[poz.vec] = (f1[poz.vec] | (1<<poz.bit));
        else
            f2[poz.vec] |= op[poz.bit];
    }
}

void Verif_Afisare()
{
    for(int i=0; i<=n/32; i++) //Parcurgem elementele vectorilor de tip unsigned int
    {
        for(int j=0; j<32; j++) //Parcurgem fiecare bit
        {
            //Verificam daca a aparut doar in primul vector caracteristic utilizand op. pe biti.
            if((((f1[i]>>j)& 1) == 1) && (((f2[i]>>j)& 1) == 0))
                rez++;
        }
    }

    out<<rez; //Afisam rezultatul
}

int main()
{
    Power();
    Citire();
    Verif_Afisare();
    return 0;
}