352 Oite

[•bogdan2412]

Aici puteţi discuta despre problema Oite.

[•cos_min]

Cat va da pentru :

Cod:

8 10
1 1 2 2 3 3 4 4

[•Binary_Fire]

Cu o solutie de 100 :

Cod:

18

[•cos_min]

Ce complexitate este necesara pentru 80 de pcte si pentru 100 de pcte ?

[•wefgef]

O(N^2 log N) - 80
O(N^2) - 100

[•arenakadaff]

Cazuri particulare ceva? K imi iau wrong answer pe 2 teste. Si nush ce as putea greshi....

[•cos_min]

Un hint pentru o rezolvare optima ? Nu ma prind nicicum 

[•stef2n]

Hashing

[•cos_min]

Merci. Atunci un bun motiv sa invat hashing

[•Marius]

Am folosit map din C++ si am luat 2 TLE ... Cum ati implementat hashul ?

[•amadaeus]

Am folosit map din C++ si am luat 2 TLE ... Cum ati implementat hashul ?

Map din STL este de fapt un arbore rosu-negru, deci update si query logaritmic. Foloseste un hash "home-brewed"

[•Marius]

O(N^2 log N) - 80
O(N^2) - 100

O(N² log N) cu constanta 2 merge de 100.

[•DITzoneC]

Mda, calculatorul pe care se face evaluarea la infoarena este mai rapid decat cel care s-a folosit la Stele si aici nu prea se mai poate face diferenta intre N²*log N si N².

[•peanutz]

Cum tre sa faci hashing-ul? L-am facut cu modulo si am folosit vector din stl, si nu prea merge mai mult de 50. Ce fel de hash tre sa fac pentru 100? Sau sa schimb vector cu liste?

[•mika17]

Tot 90pct iau si ma gandesc la prob asta de ceva timp

Ideea mea e ca la inceput sa inserez toate perechile de sume (i,j) cu i = 3 .. n - 1 si j = i + 1 .. n

Apoi

Cod:

int cnt = 0;
        for(int j=2;j<=N-2;++j)
        {
         for(int i=1; i<j; ++i)
          cnt += count(S - c[i] - c[j]);

         for(int i=j+2;i<=N;++i)
          erase(c[j+1] + c[i]);
        }

Astfel scot per total scot un numar minim de comparatii intre elemente ... corectatima daca gresesc
Ca hash am incercat tot ce se putea ... Open Addressing cu 2 hash, hash dublu, acum folosesc un hash simplu cu metoda inmultirii

Trebuie alta abordare totusi?  Eu pt hash folosesc un vector<int> de 3033 elemente  (la prob hashuri a intrat lejer in timp)
.  Trebuie facut hashul altfel ?  . Am incercat si dimensiuni mai mari ( < 660013) dar merge mult mai greoi 
Deci mai mult de atat nu vad ce as mai putea optimiza la rezolvarea cu hash-uri vorbind , cea cu cautarea binara n-am incercato


edit : am bagat un sort() si am luat 100   Ms Andrei

[•Mishu91]

Sorteaza elementele
Si eu luam 90 cu un TLE, si dupa sortare -> 100

[•APOCALYPTO]

Imi poate spune si mie cineva cum sa rezolv problema coliziunilor daca fac problema  cu map(sau cu hash_map)?
Pentru ca voi avea mai multe sume egale care sunt obtinute din elelmente diferite (de examplu pe testul lui cos_min).
Multumesc anticipat!

[•Mishu91]

Cu un multimap sau hash_multimap. Dar limita de timp pare destul de strânsă, nu am reușit mai mult de 80 cu hash_multimap.

[•pauldb]

Eu am luat 100 cu unordered_map.

Nu prea inteleg ce coliziuni trebuie sa tratezi. Pur si simplu numeri de cate ori apare o suma.

[•APOCALYPTO]

Eu am luat 100 cu unordered_map.

Nu prea inteleg ce coliziuni trebuie sa tratezi. Pur si simplu numeri de cate ori apare o suma.

8 10
1 1 2 2 3 3 4 4
Pai daca avem testul asta
1+4=5(primul si penultimul)
1+4=5(al doilea si ultimul)
1+4=5(primul si ultimul)
2+3=5
2+3=5
1+3=4
1+3=4
Iar eu trebuie sa bag sumele astea intr-un hash.
Eu am folosit sumele ca Key si o sa am mai multe perechi de numere cu aceiasi suma si la unele perechi nu voi putea ajunge ca sa le pot numara daca folosesc map.

[•pauldb]

Nu inteleg ce te impiedica sa ajungi la ele. Probabil nu stii sa utilizezi un map prea bine. Merge sa faci in felul urmator:

Cod:

(unordered_)map <int, int> m;

...

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

In m[ s ] retii de cate ori apare suma s, daca a fost introdusa in (unordered_)map.

[•blasterz]

cred ca el vrea sa afle cum verifici daca cei 4 indici sunt distincti

[•Mishu91]

Pentru a fi sigur că cei patru indici sunt distincți baleiezi prin șir și fixezi pe rând câte un element. Vei alege doi indici din dreapta elementului și doi din stânga elementului.

[•SebiSebi]

Nu am reusit sa trec de 90( nici cu double hashing macar ). Am incercat sa sortez fiecare lista cu sort(), si am luat TLE pe 8 teste. Ma poate lamurii cineva. Multumesc anticipat!

[•scipianus]

Sigur se mai poate lua 100pct cu hashing? Se poate uita cineva pe sursa mea ( http://infoarena.ro/job_detail/730542?action=view-source ) sa-mi dea vreun sfat pentru 100pct?