|
Titlul: structuri de date? Scris de: Ciocan Andrei din Noiembrie 06, 2009, 22:23:25 Exista vreo structura de date care sa suporte un querry gen : a, b, x ? (cate elemente de pe un interval (a,b) sunt mai mici decat un x? nu este acelasi x pt toate intrebarile, am m intrebari, si pt fiecare,x-ul e diferit ) ???
Ms fain :) Titlul: Răspuns: structuri de date? Scris de: Andrei Misarca din Noiembrie 06, 2009, 23:19:18 Cred că se poate rezolva cu AIB în 2 dimensiuni. O dimensiune o consider valoarea și una poziția, iar când fac un query fac o interogare pe intervalul (a, 1), (b, x). Dezanatajul este că ai O(N * Valoarea_maxima) memorie, ceea ce în general este cam mult. :)
Titlul: Răspuns: structuri de date? Scris de: Savin Tiberiu din Noiembrie 07, 2009, 00:50:49 Poti sa faci offline. Citesti toate query-urile inainte si le sortezi dupa valoarea X. Acuma tii un AIB in care initial toate valorile sunt 0 si cum parcurgi query-urile iei toate elementele mai mici decat x si le faci 1. In felu asta un query pe intervalul [a...b] iti va da numarul de numere mai mici decat x. Complexitatea finala ar fi O(N + M log N). Singurul dezavantaj e ca trebuie sa citesti query-urile inainte.
Titlul: Răspuns: structuri de date? Scris de: Andrei Grigorean din Noiembrie 07, 2009, 03:19:17 Solutia data de devilkind este cea mai buna in cazul in care nu ai update-uri si poti citi query-urile dinainte. Altfel, poti sa faci cu arbori de intervale 2D, folosind O(N log N) memorie si avand complexitatea de O(log^2 N) pe query/update.
Titlul: Răspuns: structuri de date? Scris de: Ciocan Andrei din Noiembrie 10, 2009, 16:19:02 Da... o memorie n* max_val ar fi destul de mult :D. Destul de interesanta ideea cu AIB totusi... :-k
Solutia lui devilkind e intradevar si mai usor de implementat, si ceva mai eficienta. :ok: Am sa ma uit si peste un articol cu arbori bidimensionali...par destul de interesanti si utili :) Ca tot veni vorba de intervale...m-am tot gandit si la problema asta, dar nu i-am dat de cap... :eyebrow: Cum pot rezolva un querry : determinati numarul de elemente distincte dintr-un interval (a,b) ? Am vazut ceva de genu si la baraj in a doua zi de concurs... Titlul: Răspuns: structuri de date? Scris de: Paul-Dan Baltescu din Noiembrie 10, 2009, 17:39:27 Exista o problema (http://infoarena.ro/problema/distincte) foarte asemanatoare cu cea de care intrebi tu pe site. Solutia ei e prezentata in acest articol (http://infoarena.ro/preoni-2007/runda-4/solutii).
Titlul: Răspuns: structuri de date? Scris de: Ciocan Andrei din Noiembrie 10, 2009, 17:51:35 mersi Paul :D
Titlul: Răspuns: structuri de date? Scris de: Andrei Misarca din Noiembrie 10, 2009, 17:53:54 Eu am rezolvat problema de care zici (cea de la baraj) in O(NlogN) in mod asemanator cu solutia prezentata de devilkind. Am sortat query-urile si le-am rezolvat in ordine.
Titlul: Răspuns: structuri de date? Scris de: Andrei Grigorean din Noiembrie 11, 2009, 00:07:27 Eu am rezolvat problema de care zici (cea de la baraj) in O(NlogN) in mod asemanator cu solutia prezentata de devilkind. Am sortat query-urile si le-am rezolvat in ordine. Inseamna ca trebuie sa schimb testele :P. Titlul: Răspuns: structuri de date? Scris de: Andrei Misarca din Noiembrie 11, 2009, 15:19:58 Cu parsarea citirii + câteva optimizări se pot scoate timpi sub 0,8 secunde, după cum se vede aici (http://infoarena.ro/job_detail/362121). Totuși, sunt curios de soluția in O(Nlog*N). Cum se face cu mulțimi disjuncte, fără a mai sorta intervalele?
|