|
•anna_bozianu
|
|
« Răspunde #1 : Aprilie 08, 2008, 19:44:06 » |
|
HELP pls. Am doua implementari http://infoarena.ro/job_detail/174357 de 50 p in care incerc sa fac operatia de tip 2 in O(log n) si a doua http://infoarena.ro/job_detail/174387 de 100 p in care la operatia de tip 2 gasesc indicele prin cautare binara. Nu reusesc cu nici un chip sa descopar ce gresesc la prima implementare. E sigur ca de la operatia de tip 2 vine greseala cat timp sursele sunt identice in rest. Poate reuseste cineva sa vada unde e greseala. Mii de multumiri.
|
|
|
Memorat
|
|
|
|
•Dorin
Client obisnuit
Karma: 7
Deconectat
Mesaje: 73
|
|
« Răspunde #2 : Aprilie 08, 2008, 19:50:22 » |
|
Vezi ce afisezi cand cauti pozitia minima k astfel incat suma valorilor primilor k termeni sa fie exact 0.
|
|
|
Memorat
|
Smile ! ... tomorow will be worse
|
|
|
•filipb
|
|
« Răspunde #3 : Aprilie 08, 2008, 20:06:53 » |
|
Da, de la asta e. Daca k = 0 trebuie afisat -1.
|
|
|
Memorat
|
|
|
|
•anna_bozianu
|
|
« Răspunde #4 : Aprilie 08, 2008, 20:25:33 » |
|
Intr-adevar, asa era. Am facut modificarea si a mers. Inca odata multumesc.
|
|
|
Memorat
|
|
|
|
•test_b
Strain
Karma: -2
Deconectat
Mesaje: 4
|
|
« Răspunde #5 : Aprilie 10, 2008, 16:18:47 » |
|
In explicatia de pe ginfo despre aib zice ca pentru suma (a,b) se scad (1,b), si (1,a-1). Dar asta nu merge de exemplu pentru minim ... pentru minim cum se face ?
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #6 : Aprilie 10, 2008, 16:22:12 » |
|
Nu poti folosi arbori indexati binar pentru astfel de query-uri. Trebuie sa folosesti alte structuri de date, cum ar fi arborii de intervale.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Marius
|
|
« Răspunde #7 : Aprilie 10, 2008, 17:35:46 » |
|
Se poate si cu arbori indexati binar, insa in O(log2 n). Cu arbori de intervale ai O(log n).
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•toni2007
|
|
« Răspunde #8 : Decembrie 21, 2008, 01:19:40 » |
|
O problema draguta cu aib-uri 2d e Mobiles de la IOI 2001, alta fiind si cutii de pe infoarena.
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #9 : Februarie 02, 2009, 00:01:04 » |
|
O chestie tare pe care tocmai am descoperit-o: LSB(x) = x & -x
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•Marius
|
|
« Răspunde #10 : Februarie 02, 2009, 01:30:12 » |
|
O chestie tare pe care tocmai am descoperit-o: LSB(x) = x & -x E veche.
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•Mishu91
|
|
« Răspunde #11 : Februarie 05, 2009, 10:38:50 » |
|
Imi poate recomanda cineva un articol despre AIB in 2D si cum se implementeaza, ca din ce am cautat nu am gasit cine stie ce
|
|
|
Memorat
|
|
|
|
•toni2007
|
|
« Răspunde #12 : Februarie 05, 2009, 11:55:19 » |
|
Aib-urile 2d se implementeaza la fel ca cele 1 d doar ca ai doua foruri: void Update(int a, int b, int val){ int i, j; for (i = a; i <= n; i += lsb(i)) for (j = b; j <= n; j += lsb(j)) aib[i][j] += val; }
Uite inca o problema pe ideea asta: http://www.spoj.pl/problems/MATSUM/. De asemenea, vazusem cateva pe z-trening tot asa. Spor
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #13 : Februarie 05, 2009, 12:11:58 » |
|
Mersi fain
|
|
|
Memorat
|
|
|
|
•Marius
|
|
« Răspunde #14 : Februarie 05, 2009, 12:25:05 » |
|
Imi poate recomanda cineva un articol despre AIB in 2D si cum se implementeaza, ca din ce am cautat nu am gasit cine stie ce Mobiles, IOI 2001
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
|
•philip
Strain
Karma: 5
Deconectat
Mesaje: 39
|
|
« Răspunde #16 : Noiembrie 21, 2009, 16:45:33 » |
|
O chestie tare pe care tocmai am descoperit-o: LSB(x) = x & -x E veche. In tutorialul de pe topcoder se explica cum s-a ajuns la relatia asta. Dar nu inteleg egalitatea de la care s-a pornit: Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. De ce opusul unui numar este egal cu "negatia" + 1?
|
|
|
Memorat
|
|
|
|
•Prostu
|
|
« Răspunde #17 : Noiembrie 21, 2009, 22:15:20 » |
|
In tutorialul de pe topcoder se explica cum s-a ajuns la relatia asta. Dar nu inteleg egalitatea de la care s-a pornit: Integer -num is equal to (a1b)¯ + 1 = a¯0b¯ + 1. De ce opusul unui numar este egal cu "negatia" + 1?
Trebuie sa privesti problema din punctul de vedere al masinii, unde x este un sir binar. Asa sunt reprezentate de calculatoare numerele negative, se numeste reprezentare complementara si are importanta proprietate ca nu trebuie examinati bitii de semn la adunarea sau scaderea a doua numere. http://cs.ubbcluj.ro/~rlupsa/edu/ac/doc/repr-intr.htmlhttp://en.wikipedia.org/wiki/Two%27s_complement
|
|
|
Memorat
|
|
|
|
|
•sima_cotizo
|
|
« Răspunde #19 : Decembrie 01, 2009, 14:27:17 » |
|
Ce spui tu este cunoscut, insa arborii indexati binar au avantajul spatiului: folosesti doar N elemente (in loc de 4N cat e la arborii de intervale). In plus, mi se pare ca sunt ceva mai rapizi pe operatiile pe care le implementeaza, dar se poate sa fie doar o parere
|
|
|
Memorat
|
|
|
|
•stocarul
|
|
« Răspunde #20 : Decembrie 01, 2009, 18:10:13 » |
|
Ce spui tu este cunoscut, insa arborii indexati binar au avantajul spatiului: folosesti doar N elemente (in loc de 4N cat e la arborii de intervale). In plus, mi se pare ca sunt ceva mai rapizi pe operatiile pe care le implementeaza, dar se poate sa fie doar o parere Știam că este cunoscut, numai că în "descrierea soluției" nu am văzut nimic legat de acest lucru. Iar referitor la memorie, cred că sunt necesari doar 2N la arborii de intervale.
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #21 : Decembrie 01, 2009, 21:00:17 » |
|
Arborii indexati binar sunt mult mai rapizi decat arborii de intervale, asa ca va recomand sa ii folositi de fiecare data cand puteti.
Legat de memoria folosita de un aint, daca N = 33 cat se aloca?
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•nash
|
|
« Răspunde #22 : Iunie 14, 2010, 23:52:28 » |
|
O problema ciudata... la problema asta daca pun "inline" in fata functiei "search" .. iau 0 puncte cu raspuns incorect , daca scot inline de la cautarea binara... iau 100 ... , probleme cu compilatorul ? http://infoarena.ro/job_detail/463335http://infoarena.ro/job_detail/463334
|
|
« Ultima modificare: Iunie 15, 2010, 08:36:36 de către nash mit »
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #23 : Iunie 15, 2010, 00:39:10 » |
|
Daca schimbi denumirea functiei iti merge? Cred ca e un name clashing cu o functie din algorithm.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•nash
|
|
« Răspunde #24 : Iunie 15, 2010, 07:50:40 » |
|
Am schimbat ... dar daca pun inline ... aceasi problema http://infoarena.ro/job_detail/463342Oricum... daca erau doua functii cu aceasi signiatura ar fi trebuit sa dea o eroare ( ambiguitate .... ) Mie imi compileaza fara nici o eroare . + "inline" nu schimba signiatura functiei ...
|
|
« Ultima modificare: Iunie 15, 2010, 08:17:17 de către nash mit »
|
Memorat
|
|
|
|
|