infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Ianuarie 21, 2007, 23:51:09

Titlul: 299 Elimin
Scris de: Adrian Diaconu din Ianuarie 21, 2007, 23:51:09

Aici puteÅ£i discuta despre problema Elimin (http://infoarena.ro/problema/elimin).

Titlul: Raspuns: 300 Elimin
Scris de: Bondane Cosmin din Ianuarie 25, 2007, 22:31:40

Scuzati intrebare :

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

Ms.

Titlul: Raspuns: 300 Elimin
Scris de: Adrian Diaconu din Ianuarie 25, 2007, 23:05:16

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.

Titlul: Raspuns: 300 Elimin
Scris de: Marius Stroe din Ianuarie 26, 2007, 18:42:10

Citat din mesajul lui: Bondane Cosmin Cosi din Ianuarie 25, 2007, 22:31:40

Scuzati intrebare :

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

Ms.

Rezolva Flip.

Titlul: Raspuns: 300 Elimin
Scris de: Bondane Cosmin din Ianuarie 27, 2007, 19:41:31

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

le : Am reusit sa iau 100 pana la urma.

Titlul: RÄƒspuns: 299 Elimin
Scris de: Ionescu Vlad din Mai 12, 2007, 10:35:12

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 :'(

Titlul: RÄƒspuns: 299 Elimin
Scris de: Bondane Cosmin din Mai 12, 2007, 11:48:34

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

Titlul: RÄƒspuns: 299 Elimin
Scris de: Ionescu Vlad din Mai 12, 2007, 11:54:36

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 :/.

Titlul: RÄƒspuns: 299 Elimin
Scris de: Codrea Marcel din Mai 12, 2007, 12:20:50

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;

Titlul: RÄƒspuns: 299 Elimin
Scris de: Ionescu Vlad din Mai 12, 2007, 12:29:33

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...

Titlul: RÄƒspuns: 299 Elimin
Scris de: Codrea Marcel din Mai 12, 2007, 12:33:15

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

Pontul 3 !

Timpul de rulare scade cu 60% !

Titlul: RÄƒspuns: 299 Elimin
Scris de: Ionescu Vlad din Mai 12, 2007, 12:45:25

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 :).

Titlul: RÄƒspuns: 299 Elimin
Scris de: Florian Marcu din August 24, 2007, 10:56:58

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...

Titlul: RÄƒspuns: 299 Elimin
Scris de: Filip Cristian Buruiana din August 24, 2007, 12:49:10

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.

Titlul: RÄƒspuns: 299 Elimin
Scris de: Florian Marcu din August 24, 2007, 13:05:56

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

Titlul: RÄƒspuns: 299 Elimin
Scris de: Filip Cristian Buruiana din August 24, 2007, 13:19:35

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.

Titlul: RÄƒspuns: 299 Elimin
Scris de: Bogdan-Alexandru Stoica din August 24, 2007, 13:24:56

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. :)

Titlul: RÄƒspuns: 299 Elimin
Scris de: Florian Marcu din August 24, 2007, 20:01:23

Va multumesc pt ajutor.

Citat din mesajul lui: Filip Cristian Buruiana din August 24, 2007, 13:19:35

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? ](*,)

Titlul: RÄƒspuns: 299 Elimin
Scris de: Ionescu Vlad din August 24, 2007, 20:40:24

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

Titlul: RÄƒspuns: 299 Elimin
Scris de: Bondane Cosmin din August 24, 2007, 21:20:38

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.

Titlul: RÄƒspuns: 299 Elimin
Scris de: Filip Cristian Buruiana din August 24, 2007, 21:47:46

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. :peacefingers:

Titlul: RÄƒspuns: 299 Elimin
Scris de: Florian Marcu din August 25, 2007, 16:22:33

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

Titlul: RÄƒspuns: 299 Elimin
Scris de: Bogdan-Alexandru Stoica din Septembrie 21, 2007, 11:29:20

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)

Titlul: RÄƒspuns: 299 Elimin
Scris de: Airinei Adrian din Septembrie 21, 2007, 12:15:06

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

Titlul: Răspuns: 299 Elimin
Scris de: Ionescu Robert Marius din Decembrie 29, 2007, 15:32:59

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 :D

Titlul: RÄƒspuns: 299 Elimin
Scris de: Florian Marcu din Decembrie 29, 2007, 18:11:37

Faci back pe linii sau coloane, in functie de care din numarul lor (liniilor sau coloanelor) e mai mic. Daca nr de coloane > nr de linii faci back pe linii, altfel pe coloane. :)
Si e mai usor daca faci back-ul iterativ, folosindu`te de reprezentarea binara a nr din intervalul [1,2^n]. Astfel, pt fiecare nr din [1,2^n], dupa ce il reprezinti binar intr`un vector, daca st [ i ] ==1 atunci elimini linia i / coloana i (in fctie de ce spuneam mai sus), altfel nu. Si vezi care caz e cel optim. Sper ca am explicat destul de clar. Succes! :ok: