299 Elimin

[•DITzoneC]

Aici puteţi discuta despre problema Elimin.

[•cos_min]

Scuzati intrebare :

-> Cum pot genera toate posibilitati de de a elimina exact C coloane din numarul total de N in O(2^N) ?? 

Ms.

[•DITzoneC]

Parcurgi toate numerele din intervalul [ 0,2^N-1 ]. In descompunerea binara bitul i va fi 1 daca coloana i va fi eliminata, 0 in caz contrar. Pe parcurs ce generezi numerele retii cati de 1 ai adaugat.

De fapt nici nu o sa ai 2^N, o sa fie combinari de N luate cate C, ai grija ca la un anumit pas sa nu pui 1 daca deja ai pus C de 1, si nu pui 0 daca numarul de biti ramasi necompletati nu iti ajunge pentru a pune in total C de 1.

[•Marius]

Scuzati intrebare :

-> Cum pot genera toate posibilitati de de a elimina exact C coloane din numarul total de N in O(2^N) ?? 

Ms.

Rezolva Flip.

[•cos_min]

Multumesc pentru indicati, am ajuns la cota 70 sa speram ca o sa imi iasa de 100

le : Am reusit sa iau 100 pana la urma.

[•Dastas]

Eu iau 90, TLE pe ultimul test. A luat cineva 100 generand combinarile cu backtracking? La flip a intrat lejer asa... aici se pare ca nu vrea...

Pe biti nu prea ma prind cum se face. Pur si simplu ma folosesc de bitii numerelor din intervalul [0, 2^N], eliminand coloanele a caror biti corespunzatori sunt 1 (Daca acesti biti de 1 sunt C in total)? Nu prea inteleg ce vrea sa spuna Adrian Diaconu prin "si nu pui 0 daca numarul de biti ramasi necompletati nu iti ajunge pentru a pune in total C de 1.". Eu ma gandeam sa parcurg numerele din [0, 2^N], iar daca am C biti de 1, elimin acele coloane...

Putin ajutor va rog

[•cos_min]

Intra back si fara biti, adica back normal. Incearca sa faci backu' pentru Minim(nr_coloane,nr_linii).

[•Dastas]

Asemanator am facut... adica, daca linii < coloane, am citit matricea inversata, am interschimbat nr_linii cu nr_coloane si r cu c, iar apoi am facut back pe coloane (care sunt minime...). Inainte sa fac asta luam vreo 60... asa tle pe ultimul test :/.

[•marcelcodrea]

Nu stiu cum parcurgi tu matricea ,insa se pierde foarte mult timp daca spargi linia de cache foarte des (printr-o parcurgere pe coloane,de exemplu)!

 

Cod:

          for(j=1;j<m;j++)
           for(i=1;i<m;i++)
             a[i][j]=1; 

[•Dastas]

Intr-adevar, daca liniile sunt mai putine decat coloanele, matricea o citesc gata rotita (accesez elementele ceva de genul a[n-j+1][ i ], cu for-uri i=1..m, j =1..n), poate fi de la asta? O sa incerc sa scap de asta facand back-ul direct pe minimul dintre linii si coloane atunci...

[•marcelcodrea]

Exista un articol pe tema asta :
http://infoarena.ro/12-ponturi-pentru-programatorii-CC

Pontul 3 !

Timpul de rulare scade cu 60% !

[•Dastas]

Dar... ma ajuta asta cu ceva cand rotesc matricea? Ca atunci tot nu pot scapa de spargerea liniei de cache...

Edit: Am luat 100 folosind sort din STL. Ultimul test intra in ~250 ms... totusi, daca binevoieste cineva sa ma ajute cu o solutie de 100 fara stl, eventual pe biti, i-as fi recunoscator .

[•Florian]

Am o rezolvare aproximativ ca in exemplu: pt fiecare configuratie a nr de la 0 la 2^n-1, dak aceasta are un numar de biti de 1 egal cu R, atunci execut pasii din articol. cu toate acestea, am 2 TLE-uri. Nu inteleg ce ar putea sa optimizez. Pt sortarea vectorului de sume folosesc qsort, iar knd aflu bitii unui nr, am grija sa ma opresc dak cumva numarul de biti de 1 depaseste valoare R. Nu prea vad ce optimizare sa mai fac...

[•filipb]

Functia qsort implementata in Borland merge foarte incet si poate avea in unele cazuri complexitate patratica! Incearca sa folosesti functia sort din STL ( inlocuirea nu necesita mari schimbari, doar vreo doua linii de cod in plus ), sau poti implementa propria ta functie qsort care sigur va fi mai rapida. Asa sigur o sa obtii 100.

[•Florian]

Am folosit functia sort, si akum iau 90 de puncte.  Alte sugestii?

[•filipb]

Hm... m-am uitat un pic pe sursa ta sa vad de ce inca merge incet. Sugestiile mele: incearca sa renunti atat la struct care e complet inutil ( retine doar informatiile pentru un long. in plus foloseste int, nu long, pentru ca sub linux ambele tipuri sunt pe 4 bytes ), cat si la functia stiva. Pentru a numara bitii de 1 dintr-un numar poti folosi preprocesare:

Cod:

for (i = 1; i < (1<<N); i++)
{
     if (2 * i <= (1<<N)) nr_biti[2*i] = nr_biti[i];
     if (2 * i + 1 <= (1<<N)) nr_biti[2*i+1] = nr_biti[i]+1;
}

2¹⁵ intra pe tipul de date int, nu e nevoie de long long.

Mare atentie la aceste aparent mici detalii, sunt mari consumatoare de timp. O programare ingrijita reduce semnificativ timpul de executie al programului.

[•fireatmyself]

daca ai urmarit articolul (in totalitate), inseamna ca ideea este buna.
ai grija la detaliile de implementare
  1. algoritm interativ de generare a submultimilor (merge mai repede decat cel recursiv)
  2. la instructiunile repetitive, incearca sa ai limite ce se calculeaza o singura data in cadrul acestora  (ex: for (i = 0; i < V[ x ]; i++) => for (i = 0, n = V[ x ]; i < n; i++), deci V[ x ] va fi accesat o singura data)
  3. folosestete de operatiile pe biti (in loc de if ( a==0 ), if (!a), in loc de 2*x, (x<<1), etc...)

sunt chestii mici, pe care probabil le stii deja, dar care pot optimiza un algoritm care se incadreaza in timp 'la limita'.

Spor si numai de bine. 

[•Florian]

Va multumesc pt ajutor.

Sugestiile mele: incearca sa renunti atat la struct care e complet inutil ( retine doar informatiile pentru un long.

Am folosit structura asta, intrucat fiind prima data knd folosesc sort din std, primesc o eroare. Uite:

Dak am asa:
*o structura numita "interval" si codu`:

Cod:

bool operator <(const interval &x, const interval &y)
        {
        return x.x<y.x;
        }

merge fara nicio problema. [ fiind motivul pt care am folosit structura ].

Insa dak am asa:

Cod:

bool operator <(const int &x, const int &y)
        {
        return x<y;
        }

Primesc eroarea:

Cod:

 bool operator ... must have an argument a class or enumerated type

Cum ar trebui sa arate codu` corect pt a sorta un vector de tip int? 

[•Dastas]

Pentru tipurile de date existente deja exista operatorul <, deci nu ai nevoie de o astfel de functie...

[•cos_min]

Daca ai :

int A[dim];
......
sort(A+0,A+N); // ceva de genu asta, ai grija ca s'ar putea sa nu fie A+0 si A+N, ai grija cum le sorteaza.

[•filipb]

Tot din codul tau am remarcat ca folosesti destul de incalcit STL ( de exemplu std::sort(s+1,s+m+1) ).

Uite un program mult mai simplu care foloseste sort si sorteaza descrescator ( functia sort primeste in plus un parametru cmp - functie de comparare - ca la qsort ):

Cod:

#include <stdio.h>
#include <algorithm>
using namespace std; // spatiul de nume pentru STL - obligatoriu

int N, a[100001];

int cmp(const int& a, const int& b)
{ return a>b; }

int main()
{
    int i;
 
    scanf("%d", &N);
    for (i = 1; i <= N; i++) scanf("%d", &a[i]);

    sort(a+1, a+N+1, cmp);  // acum vectorul e sortat conform functiei cmp - descrescator 
   
    return 0; 
}

Cu sort folosit asa si cu micile optimizari de cod pe care ti le-am zis ( eliminat long long, structuri si introdus preprocesarea pentru numarul de biti ) ar fi dubios sa nu iei 100.

[•Florian]

Dapz. A mers!  Va multumesc mult pt ajutor [ in special lui filipb ]. Am avut ce invata din problema asta.

[•fireatmyself]

am trimis azi aceasta sursa (care la vremea concursului a luat punctaj maxim) si iau 0 puncte (SigSecv). s-a schimbat ceva de-atunci la problema? 

http://infoarena.ro/job_detail/85380 (now)
http://infoarena.ro/job_detail/16209 (then)

[•astronomy]

Depasesti limita de memorie.. Poate atunci nu se tinea cont de memoria declarata, doar de cea folosita.

[•Robytzza]

daca am inteles eu bine pb se face ceva in genu:
  Daca numarul liniile eliminate este mai mare decat cel al colonalelor care trebe eliminate elimin cele mai mici L linii  ca suma,si dupia genereaz cu back p-entru colone si iau cel mai avantajos caz;
daca nu,daca nr coloanelor e mai mare ca nr liniilor ce trebe eliminate intorc matricea si fac exact acelasi licru numai ca nr linnilor se schimba cu nr coloanelor
e bine asa??
?
ms anticipat