|
Titlul: 186 Banana Scris de: ditzone din Martie 03, 2006, 18:22:50 Aici puteţi discuta despre problema Banana (http://infoarena.ro/problema/banana).
Titlul: 186 Banana Scris de: Gogu Marian din Martie 03, 2006, 20:57:24 Mi se pare mie sau e exemplul truchiat?
Zice ca sunt 10 bananieri si nu sunt decat 8. Titlul: 186 Banana Scris de: ditzone din Martie 03, 2006, 21:43:01 S-a rezolvat
Titlul: 186 Banana Scris de: Gogu Marian din Martie 06, 2006, 19:10:53 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). Titlul: 186 Banana Scris de: Bogdan-Alexandru Stoica din Martie 21, 2006, 10:51:27 eu zic ca te complici, poti sa o rezolvi si mai simplu. si in plus mai este o problema asemanatoare tot pe Info Arena :D
Titlul: 186 Banana Scris de: Gogu Marian din Martie 21, 2006, 13:37:47 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.
Titlul: Raspuns: 186 Banana Scris de: Prigoana Alexandru din Aprilie 11, 2006, 23:01:18 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 ?
Titlul: Raspuns: 186 Banana Scris de: u-92 din Aprilie 12, 2006, 06:55:56 ideea e s-o rezolvi cu multimi (disjoint data set)
Titlul: Raspuns: 186 Banana Scris de: Prigoana Alexandru din Aprilie 12, 2006, 19:36:37 nu-mi spune nimic :) ... poti sami dai un link calumea ? ce complexitate ar trebui sa scot ?
Titlul: Raspuns: 186 Banana Scris de: andreit1 din Aprilie 12, 2006, 19:58:29 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.
Titlul: Raspuns: 186 Banana Scris de: Prigoana Alexandru din Aprilie 12, 2006, 20:23:22 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 ? Titlul: Raspuns: 186 Banana Scris de: andreit1 din Aprilie 12, 2006, 21:10:00 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) ). Titlul: Raspuns: 186 Banana Scris de: Marius Stroe din Aprilie 13, 2006, 10:55:37 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 ! Titlul: Raspuns: 186 Banana Scris de: andreit1 din Aprilie 13, 2006, 11:19:41 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.
Titlul: Raspuns: 186 Banana Scris de: Prigoana Alexandru din Aprilie 13, 2006, 14:19:55 mersi :) ma uit peste el
Titlul: Răspuns: 186 Banana Scris de: raica dumitru cristian din Aprilie 15, 2011, 13:49:29 am si eu o intrebare ... maimuta porneste din (1,1) ? ...
ca nu imi dau seama din enunt si nu imi iese problema nicicum ... ](*,) Titlul: Răspuns: 186 Banana Scris de: Paul-Dan Baltescu din Aprilie 15, 2011, 16:33:43 Nu. Maimuta poate porni de oriunde.
Titlul: Întrebare Scris de: asdf asdf din Iunie 16, 2012, 22:54:59 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.
Titlul: Răspuns: 186 Banana Scris de: Cristian Lambru din Iunie 16, 2012, 23:09:24 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.
|