|
Titlul: 1197 Mess Scris de: Dragos-Alin Rotaru din Aprilie 23, 2013, 11:59:09 Aici puteti discuta despre problema Mess (http://www.infoarena.ro/problema/mess).
Titlul: Răspuns: 1197 Mess Scris de: Oncescu Costin din Aprilie 25, 2013, 18:22:52 Ma poate ajuta si pe mine cineva cu problema asta?Am citit solutia oficiala si nu inteleg cum pot retine pentru fiecare nod un aib pentru ca nu ar intra in memorie.Si de asemenea nu inteleg la ce te-ar mai ajuta sa tii minte valorile sortata(pentru ca daca reusesti sa retii aib-ul atunci nu mai e nevoie).
Eu am retinut in fiecare nod valorile sortate pentru ca nu am putut retine aib-ul. :-k Multumesc anticipat! Titlul: Răspuns: 1197 Mess Scris de: Carabet Cosmin Andrei din Aprilie 25, 2013, 21:30:12 Poti pleca de la reprezentarea unui arbore de intervale. Un nod dintr-un arbore de intervale caracterizeaza un interval, (st, dr) sa zicem. Acum sa presupunem ca iti mentii urmatoarele informatii pt fiecare astfel de nod:
1) o lista cu valorile din intervalul (st, dr) in ordine crescatoare. Aceasta lista se poate obtine prin interclasarea listelor fiilor acelui nod. Avand in vedere ca fiecare valoare apare in log N noduri, complexitatea dpdv al memoriei cat si al timpului este N log N la pasul asta. 2) conceptual vei mentine o alta lista de lungime nr de noduri, unde pe pozitia i, ai 1 daca valoarea i(in ordinea sortata de mai sus) e online, 0 altfel. Avand in vedere tipurile de operatii pe care vrei sa le executi, defapt iti vei mentine un aib de lungime tot nr de noduri care este construit pe baza listei de care spuneam. Pt stocarea acestor aib-uri este necesara de asemenea, tot N log N memorie. Cu aceste informatii, poti sa aplici acum operatiile date in felul urmator: Operatie de tip 1: Vei trece prin cele log N noduri din arborele de intervale care contin nodul p din enunt si le vei actualiza aib-ul asociat. Deci log ^ 2 N / operatie de acest tip Operatie de tip 2: Vei descompune intervalul (p, q) in log N noduri. Acum cauti binar rezultatul printre cele N valori posibile(presupunand ca mai ai o lista cu valorile initiale sortate in ordine crescatoare). Pt o anumita valoare, verificarea se poate face folosind structura de aib, in log (lungime nod) pt fiecare nod. Complexitatea teoretica e in cazul asta log ^ 3 N, dar se comporta destul de bine. Bafta! :) Titlul: Răspuns: 1197 Mess Scris de: Oncescu Costin din Aprilie 26, 2013, 16:42:21 Multumesc!Am reusit sa iau 100. :)
|