186 Banana

[ditzone]

Aici puteţi discuta despre problema Banana.

[•gogu]

Mi se pare mie sau e exemplul truchiat?
Zice ca sunt 10 bananieri si nu sunt decat 8.

[ditzone]

S-a rezolvat

[•gogu]

La problema asta se pare ca se poate obtine 100 de puncte cu un algoritm bazat pe niste bf-uri care are nevoie de O(MaxCoordonate^2) memorie daca se folosesc operatii pe biti.
Problema cred ca a fost propusa pentru o limita de memorie mai stricta si daca cineva are timp poate pune niste teste cu coordonate mai mari (poate chiar si cu N mai mare).

[•fireatmyself]

eu zic ca te complici, poti sa o rezolvi si mai simplu. si in plus mai este o problema asemanatoare tot pe Info Arena  

[•gogu]

Tu nu cred ca ai inteles ce am vrut sa spun. Eu am rezolvat problema cu memorie O(N) si am zis ca o solutie asa de ineficienta cu memoria nu ar trebui sa ia 100 de puncte.

[•alex_prg]

la problema asta consider bananierii varfuri intrun graf. Determin muchiile dupa ce sortez pozitiile lor si dupaia fac o parcurgere in latime sa determin componentele conexe, in final le iau pe cele mai mari k.  Complexitatea e O(n*log n). Primesc pe doua teste TLE ... cum sal mai imbunatatesc ?

[u-92]

ideea e s-o rezolvi cu multimi (disjoint data set)

[•alex_prg]

nu-mi spune nimic  ... poti sami dai un link calumea ? ce complexitate ar trebui sa scot ?

[andreit1]

alex_prg ideea ta este buna. Se poate lua 100 cu ea. Vezi sa nu ai nici un pas in O(N^2)... asta include si alegerea celor mai mari k multimi Se poate rezolva si cu multimi disjuncte dar nu este neaparat. Poti afla mai multe despre asta in cartea de probleme a doamnei Cerchez( eu de acolo am invatat) sau poti cauta pe google "disjoint data set" si sigur o sa gasesti.

[•alex_prg]

am gasit ceva pe net ... da nam rabdare sa incerc si asa ...
mam mai uitat peste program si aleg pe primele k componente o fac in O(k*numaru de componente) ... poate ca daca numaru de componente este f mare si k tot f mare tinde catre un O(n*n) si iese din timp nu ?

[andreit1]

Pai tu ce crezi?
Si cel mai rau caz trebuie tratat( n puncte care nu se invecineaza si n se apropie de k). Deci fa un qsort acolo si gata( sau cauta al k-lea element in O(N) ).

[•Marius]

Cu multimi disjuncte si count sort eu am rezolvat in O(N). Cu aceste multimi e mult mai usor decat te astepti, in plus cred ca scrii mai putin !

Poti sa gasesti la sectiunea download pe site-ul www.devnet.ro in arhiva Lot 2002 un articol usor de inteles !

[andreit1]

Teoretic nu este O(N) ci O(N*alfa(N,N)) unde alfa este inversa functiei lui Ackermann. Si se poate folosi count sort si la solutia cu df sau bf si atunci chiar obtii o rezolvare in O(N). Oricum articolul precizat este foarte bun pentru invatat multimi disjuncte.

[•alex_prg]

mersi  ma uit peste el

[•raica_cristi]

am si eu o intrebare ... maimuta porneste din (1,1) ? ...
ca nu imi dau seama din enunt si nu imi iese problema nicicum ... 

[•pauldb]

Nu. Maimuta poate porni de oriunde.

[•belginstirbu]

Dacă în matricea bananierilor exista o formațiune de 5 bananieri sub forma unui "+", aceasta este o singură zonă sau sunt două (una formată din cei trei bananieri aranjați pe orizontală si cealaltă de cei trei aranjați pe verticală)? În cazul din urmă, bananierul din mijloc cărei zonă îi aparține? În ambele cazuri, nu văd cum această problemă se poate rezolva eficient folosind mulțimi disjuncte.

[•maritim]

Cei 5 bananieri reprezinta o singura zona in forma de '+'. Multimile disjuncte sunt folosite pentru a calcula rapid aceste zone, impreuna cu numarul de bananieri asociat fiecareia.