1090 Rk

[•wefgef]

Aici puteti discuta despre problema Rk.

[•SpiderMan]

Stie careva alta metoda decat cea cu trie ? Multumesc .

[•pauldb]

Hashing (+parsare?) ar fi o varianta. O alta varianta (copyright Dan Spatarel) ar fi:

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]

2. Sortezi vectorul obtinut anterior.
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.

[•freak93]

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

[•SpiderMan]

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

[•Teodor94]

si eu iau tot 60 puncte cu 4 tle.ce e de optimizat la program?

[•SpiderMan]

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 ) .

[•alexandru70]

Un lucru care nu îl înțeleg din soluție este cum reprezinți arborele binar în O(N*K)  memorie.

[•vendetta]

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.