|
Titlul: .campion - problema [entries] . Scris de: Costinnel din Noiembrie 11, 2012, 11:12:07 Salut.
Deci este problema aceasta de pe siteul campion : http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1227 Toata filosofia e sa implementezi operatiile pentru multimi disjuncte, nu ](*,)? La asta m-am gandit si eu :-' .... pana am vazut ce valori pot lua elementele : 1<= P <=10 000 000 Pai as avea nevoie de trei vectori de intregi de maxim 10 milioane +1 de elemente.Insa numai unul ocupa ~38Mo de memorie :'(. Numarul maxim fiind de 5000 de operatii pot fi maxim 5000 elemente.Am asociat deci fiecarui element o cheie unica , dupa ordinea in care apare la citire .Operatiile le pot aplica acum asupra cheilor iar consumul se reduce la trei vectori de 5001 intregi. Eu am implementat o tabela de dispersie[..cred..] folosind arbori de cautare in loc de liste , ca sa pot determina rapid cheia unui element.Nu mai am probleme cu memoria , insa ...TLE :'( . Deci e cineva amabil sa-mi spuna cum se poate rezolva problema , de 100 de puncte ??? ? Sursa : http://pastebin.com/TmBjAGdc Titlul: Răspuns: .campion - problema [entries] . Scris de: Stefan Eniceicu din Noiembrie 11, 2012, 15:29:44 Ma gandeam in felul urmator:
Fie matricea (bitset ca sa consume putin) multimi[5000][5000], care iti zice pentru multimea "i" 1 daca elementul "j" se afla in multimea respectiva sau 0 daca nu. Fie vectorul v[5000], care iti zice pt. nodul i in ce multime se afla el. La inceput ai v[ i ] = i, evident. La o operatie de tip +, parcurgi multimi[J] si bagi toate elem. din multimi[J] in multimi[ I ] si pentru fiecare element din multimi[J] faci ca "v"-ul corespunzator sa pointeze la I si nu la J. Oricate operatii de tip + ai, nu vei face mai mult de O(P + N^2) pasi. Pt. operatia ?, multimi[v[ I ]][J] va fi 1 daca I e conectat la J, 0 daca nu. Complexitatea e O (P + N ^ 2). Asa scapi de logN-urile alea de la arbori si overhead-uri aiurea. Daca vrei si mai multa viteza, poti sa bagi bitsetu de mana ca nu-i mare chestie si se vede diferenta, dar cred ca e destul. Hope it helps! :weightlift: Titlul: Răspuns: .campion - problema [entries] . Scris de: Costinnel din Noiembrie 11, 2012, 21:59:50 Multumesc Steve .
|