|
Titlul: 1090 Rk Scris de: Andrei Grigorean din Decembrie 13, 2010, 00:36:14 Aici puteti discuta despre problema Rk (http://infoarena.ro/problema/rk).
Titlul: Răspuns: 1090 Rk Scris de: Simoiu Robert din Decembrie 14, 2010, 15:47:04 Stie careva alta metoda decat cea cu trie ? Multumesc .
Titlul: Răspuns: 1090 Rk Scris de: Paul-Dan Baltescu din Decembrie 14, 2010, 19:13:12
1. Consideri toti cei 32 de biti ai unui numar din sirul dat si il oglindesti in baza 2. De exemplu: 110 => 0110...0[/li] 3. Pentru un query (r k), il consideri pe r in baza 2 si il oglidesti normal. Adaugi 0 la finalul numarului pana cand acesta are k biti. Cauti folosind o cautare binara cate valori exista intre numarul obtinut anterior completat cu 0 pana 32 de biti si numarul obtinut anterior completat cu 1 pana la 32 de biti. Exemplu pentru r = 10 si k = 6. Scriem pe r in baza 2: (1010). Il oglindim si obtinem 0101. Completam cu 2 de 0 astfel incat sa avem 6 biti: 010100. Cautam cate numere avem in vector intre 0101000...0 si 0101001..1. Daca analizezi putin operatiile descrise, vei intelege de ce solutia este corecta. Titlul: Răspuns: 1090 Rk Scris de: Adrian Budau din Decembrie 14, 2010, 20:46:39 In concurs am bagat radix sort(pentru fiecare bit) si dupa fiecare pas al soratarii o parcurgere cu 2 indici, ca sa determin raspunsul pentru fiecare query. Sper sa-i foloseasca cuiva
Titlul: Răspuns: 1090 Rk Scris de: Simoiu Robert din Decembrie 14, 2010, 21:00:57 As avea o intrebare : pentru cautarea binara pot sa fac doar o cautare, sau trebuie doua ( daca merge cu una ai putea sa mi-o arati ? ) . Merci.
[LE] : Am facut cum mi-ai zis, am tinut intr-o matrice char *A[..] numerele, am facut doua cautari binare, dar iau 60 puncte, cu 4 TLE. Ce as putea optimiza? Merci. [LLE] : Mi-am dat seama , merci oricum :) Titlul: Răspuns: 1090 Rk Scris de: Teodor Plop din Decembrie 19, 2010, 20:11:33 si eu iau tot 60 puncte cu 4 tle.ce e de optimizat la program?
Titlul: Răspuns: 1090 Rk Scris de: Simoiu Robert din Decembrie 19, 2010, 22:20:47 Tine numerele ca si unsigned int, nu ca si char, deoarece sortarea si cumparatiile merg mai repede ( <, > sau = merge mai repede decat strcmp sau memcmp ) .
Titlul: Răspuns: 1090 Rk Scris de: Ungurianu Alexandru din Septembrie 26, 2013, 11:32:15 Un lucru care nu îl înțeleg din soluție este cum reprezinți arborele binar în O(N*K) memorie.
Titlul: Răspuns: 1090 Rk Scris de: Salajan Razvan din Septembrie 26, 2013, 12:32:11 Acel arbore binar e defapt un trie; dar avand in vedere ca sigma = 2 => o sa fie binar. Intr-un trie memoria folosita e lungTot*sigma, unde lungTot = suma lungimilor cuvintelor bagate in trie si sigma = 2(numarul caracterelor distincte folosite) => memoria folosita N * K * 2. => O(N*K) memorie. Trie-ul se contruieste similar cu cel din arhiva educationala. (http://www.infoarena.ro/problema/trie)
|