987 Binar

[•Prostu]

Aici puteţi discuta despre problema Binar.

[•miculprogramator]

Problema asta m-a innebunit  ! Am retinut input-ul sub forma de matrice char si transform fiecare coloana in numar in baza 10. Sortez vectorul de numere si pe cel de indici. Pe testele mele da perfect, intra in timp la evaluator dar ia Incorect peste tot. Ma puteti ajuta ?

Teste :

Cod:

4 8
11101111
00010010
01111101
10101010

raspuns : 4 1 2 6 8 3 5 7 


4 4
1010
1101
1101
1001

raspuns : 2 4 3 1 

[•andrei-alpha]

Incearca un test mai mare.

Cod:

21 21
000110001001101100111
100000011101110100110
000110101101011000101
010010101000100110101
100101001000010001000
001000111111010111111
110001001111110101000
100000001111011110111
111111011101101101001
110100100100010110101
000101010111011110000
010111010001111010001
110111100101000010101
000001010100000011101
010110010111001101111
101001000010001010101
001000000011101100100
110000010010100010100
101111101000110010100
010111111100100101010
101110010100100100111

Ok:
3 11 6 18 2 17 7 8 1 10 14 15 4 5 21 20 13 16 12 19 9 

[•miculprogramator]

Da perfect.
Si timpul e bun. Nu inteleg ce are evaluatorul cu el. 

[•mathboy]

Daca tu transformi fiecare coloana intr-un numar din baza 10 cum crezi ca vei putea sa retii un numar de 2000 de biti pe long long (64 de biti)?

[•Bogdan_tmm]

Poti eventual sa transformi in baza 10 blocuri de cate 30 de biti si complexitatea n*m*logn devine n*m*logn/30,sau sa folosesti long long si sa pastrezi blocuri de cate 60 de biti, dar creste constanta si nu te prea ajuta.Cu blocuri de 30 obti 50 puncte.

[•SpiderMan]

Am facut cu sortul din STL, adica am facut o functie de comparare si am aplicat sotrul, am facut pe cel mai mare test nu depaseste 60ms, dar pe inforena iau 30 pct. doar. De ce oare  ?

[•mathboy]

In primul rand pentru ca e ineficient ceea ce faci tu.
In al doilea rand : Uiti cumva ca sistemul sub care se evalueaza are un procesor de 2.0 GHZ ? ca nu imi vine sa cred cum ai obtinut tu timpi mai mici de 60ms pe un test maxim.

[•DraStiK]

In primul rand pentru ca e ineficient.

Sort din STL e foarte eficient. De fapt, dacă îl aplici cum trebuie la problema asta, poți lua 100p. 

[•wefgef]

Cred ca mathboy se referea la faptul ca pentru aceasta problema sa aplici sort-ul din STL este ineficient. Iar tu ai luat 100 pentru ca ai citit cu fgets, nu pentru ca merge sortul bine .

[•mathboy]

Multumesc wef pentru completare .
Cred ca la problema asta se evidentiaza foarte bine ideea de cache. Sa ma corecteze cineva daca nu am dreptate .

[•blasterz]

Pe teste random sort-ul cred ca merge foarte bine...dar daca dai cel mai defavorabil test, de exemplu , o matrice plina doar cu 0... nu cred ca iti mai intra la fel de bine in timp pt ca o sa ai O(n^2 logn)

[•Mishu91]

Sort din STL e foarte eficient. De fapt, dacă îl aplici cum trebuie la problema asta, poți lua 100p. 

Ai luat 100 sortând stringurile așa cum erau date cu sort? Că mie numa de 80 mi-a mers, pentru 100 a trebuit sa mai optimizez oleacă.

[•wefgef]

Pentru a impiedica sortul sa intre in timp, am pus limita la 0.1 secunde si am reevaluat (doar sursele trimise in arhiva, punctajele din concurs raman la fel).

Poate ca ar fi mai bine sa va ganditi cum se rezolva corect problema, nu sa va chinuiti sa optimizati o solutie cu o complexitate proasta

[•vladtarniceru]

Am nevoie de putin ajutor, iau 80 de puncte cu WA pe ultimele 2 teste rezolvand cu ideea din solutia oficiala, si nu-mi dau seama de la ce poate sa fie. Dau teste de vreo 2 ore si imi merg toate inclusiv cele de pe forum.
Daca stie cineva structura acestor teste il rog sa puna unul asemanator pe forum sa-mi dau si eu seama la ce am gresit .
Uite cum fac functia recursiva (matricea a este una pe biti cu linii de la 0 la n-1 si coloane de la 0 la m-1):

Cod:

void make (short v[], int lvl)
{
    if (lvl == n)
    {
        for (int i = 1; i <= v[0]; ++i)
            g << v[i] << ' ';
    }
    else
    {
        short nv[2003];
        nv[0] = 0;
        int dv = v[0];
        v[0] = 0;
        for (int i = 1; i <= dv; ++i)
            if (!(a[lvl][v[i] >> 3] & (1 << (v[i] & 7)))) // daca a[lvl][v[i]] == 1
                nv[++nv[0]] = v[i];
            else
                v[++v[0]] = v[i];
        if (nv[0]) make (nv, lvl + 1);
        if (v[0]) make (v, lvl + 1);
    }
}

Multumesc!

[•ctlin04]

Am incercat si eu sa fac o procedura recursiva la problema asta, dar am TLE pe 6 teste , imi poate sugera cineva vreo optimizare?

Cod:

procedure sort(st,dr,lev:integer);
 var i,k1,k2,nr1,nr0,j:integer;
begin
nr1:=0; nr0:=0;
for i:=st to dr do
  if a[lev,b[i]]=false then inc(nr0)
                 else inc(nr1);
 k1:=st; k2:=dr-nr1+1;
 for i:=st to dr do
  if a[lev,b[i]]=false then begin c[k1]:=b[i]; inc(k1); end
                 else begin c[k2]:=b[i]; inc(k2); end;
 for i:=st to dr do b[i]:=c[i];
if lev<n then begin
 if nr0>1 then sort(st,dr-nr1,lev+1);
 if nr1>1 then sort(dr-nr1+1,dr,lev+1);
               end;
end;

Ideea este ca eu la fiecare nivel numar citi de unu si citi de 0 sunt, apoi pun in zona cu 0 coloanele cu 0 in ordine consecutiva cum apar, la fel procedez si pentru zona cu 1, apoi daca zona cu 1 sau zona cu 0 are mai mult de 1 element, apelez procedura pentru zona respectiva, variabilele st si dr reprezinta limita zonei apelate, iar lev- nivelul la care ma aflu, adica linia curenta. Astept idei de optimizare sau poate imi sugerati o alta abordare, pls 

[•PlayLikeNeverB4]

Poti incerca urmatoarele:

• Retii matricea ca si o matrice de caractere (si o citesti linie cu linie).
• Cand desparti multimea, poti sa pornesti cu coloanele cu valoarea 0 de la inceputul intervalului si cu coloanele cu valoarea 1 de la capat si atunci formezi direct acel vector c. Dar ca sa fie in ordinea corecta mai trebuie sa inversezi coloanele cu valoarea 1 in caz ca unele coloane sunt egale.

[•ctlin04]

Ms mult pentru hint, interesant este faptul ca anume prima idee m-a ajutat sa iau 100, deoarece cind faceam citirea caracter cu caracter si formam deodata vectorul c tot 40 luam dar cind am citit deodata intreaga linie a mers mult mai repede, chiar nu am stiut ca o astfel de abordare a citirii poate micsora atit de mult timpul de executie.   
Apropo faza cu inversarea nu e necesara am facut un pic altfel, tin mai intii k1=st si k2=dr apoi daca intilnesc 0 incrimentez k1 si inscriu in b, iar daca intilnesc 1 atunci decrementez k2 si la fel inscriu in b si astfel la formarea lui c, pina pe pozitia lui k2 care la urma este k1-1 il formez pe c intocmai cum e b, iar de la k1 pina la m incep sa-i atribui lui c elemente din b incepind cu dr in ordine invarsa 

[•PlayLikeNeverB4]

Da, se poate si asa. Ceea ce voiam sa spun e ca nu e necesar sa afli prima data pana unde sunt coloane cu 0 si doar apoi sa construiesti c-ul (cum ai facut in sursa postata).

[•Steve]

Am facut un algoritm nerecursiv care se comporta exact ca cel recursiv, insa folosind un vector de "bariere" care spune pana unde se extinde o anumita multime. Complexitatea este O(N * M), insa chiar si cu parsare cu getline / gets / fgets nu ia mai mult de 70-80 de puncte, a little help please.

[•danalex97]

Nu te stresa , cred ca e o problema cu timpul. Solutia O(N*M) ar trebui sa ia 80p in conditiile actuale.  

[•Steve]

Am adaugat problema asta pe http://infoarena.ro/calibrare-limite-de-timp. Poate se rezolva

[•SebiSebi]

Eu inca mai iau 100 de puncte cu aceeasi sursa. Incercati sa optimizati programul, desi eu nu am cine stie ce optimizari.

[•Steve]

Am reusit si eu in final sa scot 100, dar a fost nevoie sa rescriu tot codul...

Basically, am renuntat la matrice, si am redus operatiile la jumatate...Totusi, ar trebui marita limita de timp cu vreo 10-20 ms.

[•PaulStighi]

De ce o sursa identica ia acum 2 saptamani 100 de puncte si astazi doar 50? 

https://www.infoarena.ro/job_detail/2148332
https://www.infoarena.ro/job_detail/2171926