Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: .campion - problema [entries] .  (Citit de 4372 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
costi_.-.
Strain
*

Karma: 2
Deconectat Deconectat

Mesaje: 30



Vezi Profilul
« : 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  Brick wall? La asta m-am gandit si eu  Whistle .... 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  Cry.

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  Cry .
Deci e cineva amabil sa-mi spuna cum se poate rezolva problema , de 100 de puncte  Huh ?  

Sursa : http://pastebin.com/TmBjAGdc
Memorat
Steve
Client obisnuit
**

Karma: 36
Deconectat Deconectat

Mesaje: 72



Vezi Profilul
« Răspunde #1 : 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
Memorat
costi_.-.
Strain
*

Karma: 2
Deconectat Deconectat

Mesaje: 30



Vezi Profilul
« Răspunde #2 : Noiembrie 11, 2012, 21:59:50 »

Multumesc Steve .
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines