Pagini: 1 [2] 3 4   În jos
  Imprimă  
Ajutor Subiect: 010 Stramosi  (Citit de 30443 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
Coty
Nu mai tace
*****

Karma: 6
Deconectat Deconectat

Mesaje: 235



Vezi Profilul WWW
« Răspunde #25 : Decembrie 28, 2005, 21:59:57 »

da, ai inteles, dar sortarea topologica (parca) se baza pe cati tati are i... asta ar insemna sa stiu deja lista stramosilor, deci nu as mai avea nevoie de sortare Tongue
cat despre parcurgere in adancime sau ce ai zis... ia-ma usor, ca nu stiu grafuri sau arbori... Sad nu prea inteleg ce zici
acu ma gandesc la chestia aia care au zis-o mai sus cu 2^k... iese ceva cu log(n)... deci mai bine nu se poate
Memorat
bogdan2412
Echipa infoarena
Nu mai tace
*****

Karma: 410
Deconectat Deconectat

Mesaje: 951



Vezi Profilul
« Răspunde #26 : Decembrie 28, 2005, 22:05:01 »

Daca nu stii grafuri (macar chestiile de baza, de genu parcurgeri in adancime) fa alta problema mai bine Smile Dupa ce mai citesti ceva si mai faci niste probleme mai simple o faci si pe asta
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #27 : Decembrie 28, 2005, 22:07:26 »

Citat din mesajul lui: Coty
dar sortarea topologica (parca) se baza pe cati tati are i... asta ar insemna sa stiu deja lista stramosilor, deci nu as mai avea nevoie de sortare Tongue


nu stiu cum faci tu sortarea topologica, dar ea se poate face si in O(noduri+muchii). In cazul de fata inseamna O(N)

vrei sa iti descriu sumar o varianta de sortare topologica? (eu stiu 2 variante pentru complexitatea asta Smile )

... sa presupunem ca le ai sortate topologic, sigur merge ce ai zis tu mai departe?

[later edit]
apoi ce e aia parcurgere in adancime:
ai o functie recursiva in care tii nodul in care esti; functia se auto-apeleaza pt toti fii nodului
-- si urmeaza sa faci ceva in functia asta Smile

daca ai un graf, functia e la fel, si nu iei toti fii, iei toti vecinii; doar sa ai grija sa nu apelezi functia de 2 ori pt acelasi nod (tii o matrice de "vizitat")

... pentru problema asta ar trebui sa stii si cum sa tii o lista de fii/vecini (ca sa ramai la memorie O(N) si complexitate O(N) si sa nu ajungi pe la memorie O(N*N) sau complexitate O(N*N))
Memorat
Coty
Nu mai tace
*****

Karma: 6
Deconectat Deconectat

Mesaje: 235



Vezi Profilul WWW
« Răspunde #28 : Decembrie 28, 2005, 22:09:46 »

ti-as fi recunoscator, eu am auzit de ea, parca am vazut-o si implementata, dar perfect conceptu nu l-am inteles... Smile si btw.. repet, daca tine de grafuri (muchii, noduri...) atunci... cred ca o sa ai un pic de furca Smile dar sper sa inteleg

[edit - ca sa nu postez de doua ori]
 @tataroiu : zi-mi un lucru... cu cat creste indicele problemei, creste dificultatea? ca inseamna ca ma opresc aici... daca nu, oricum, probleme simple nu prea se gasesc pe aici... si nici nu ar trebui:P
[/edit]
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #29 : Decembrie 28, 2005, 22:18:27 »

indicele NU creste cu dificultatea.. ar fi oricum complicat sa definesti gradul de dificultate al unei probleme, fiin de multe ori o chestie subiectiva (ce e mai greu: numere mari <fara impartire sa zicem...> sau cautare binara? ... cea care ai exersat-o cel mai putin)

ideea era ca ai aflat ce iti trebui la o problema, sa te duci sa te documentezi, apoi revi si incerci ce ai invatat ...sau treci la alta problema

sa vedem daca facem o pagina de statistici pt fiecare problema gen timus, asa poate o sa putem clasifica cat de cat o problema grea si una usoara
.. intre timp uite-te la statistici la cati au luat puncte la o problema (eventual 100 de puncte..)
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #30 : Decembrie 28, 2005, 22:24:17 »

Algoritmul de sortare topologica
[se aplica pt grafuri aciclice]

tii minte pentru fiecare nod numarul de muchii care "vin" spre el (in cazul arborilor aceasta valoare va fi 0 sau 1) sa il numim vectorul spre[]
iei toate nodurile cu spre[nod] 0 si le bagi intr-o coada

iei fiecare nod din coada, il pui in vectorul cu nodurile sortate topologic, scazi de la toti vecinii (pt arbori "fii") lui 1 din spre[]; daca spre[vecin/nod] devine 0, bagi si acel vecin/fiu in coada
.. continui pana se goleste coada

-- alta varianta este o parcurgere in adancime cu IN time/ OUT time si sortare dupa OUT time
Memorat
Coty
Nu mai tace
*****

Karma: 6
Deconectat Deconectat

Mesaje: 235



Vezi Profilul WWW
« Răspunde #31 : Decembrie 28, 2005, 22:28:38 »

Tongue acum dintre exemplele tale... cautarea binara e simpla, operatiile pe numere mari sunt mancatoare de timp, dar... sa zicem ca ... destul de simple

de aplicat ce am invatat... am cautat de mi-au sarit capacele ce vrea sa fie acel DF, am gasit o implementare cu o functie recursiva... dar... nu prea inteleg daca nu mi se explica, sunt cam greu de cap  Brick wall

punctaju mediu al problemei e 75, eu am 70... deci sub medie... Sad

eu nu am zis ca asta ar fi usoara, singura data cand m-am exprimat a fost in legatura cu problema Invsc (bine, parca si la A+B) si atunci v-ati suparat, deci eu doar am vrut sa ... va intreb daca pot stoca acele liste de tati si daca nu cumva fac apel la o lista neprocesata

si NU am fost cu ideea sa faceti o pagina de statistici pt probleme = grea/usoara, ca ar fi ceva total subiectiv si ar varia pt acelasi concurent de la momentu cand vede ca ia 70 (variante, alte punctaje mai mici) la o problema pana cand o rezolva total

------------------------------------------------------------------------------------
scuze de neplaceri... daca exista

[later edit - iar ca sa nu postez de doua ori]
ultimu tau post e o parcurgere in adancime... sau ce?... sau sortare topologica, seamana cu ce ziceai, devin intr-un fel sortati...

si daca merge in continuare, eu zic ca merge... nu garantez... si tot devine mancator de timp ca pt i, ii determinam al k-lea stramos in O(1), dar trebuie sa copiem lista stramosului a... complicat, nu cred ca merge Annoyed
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #32 : Decembrie 28, 2005, 22:40:38 »

Citat din mesajul lui: Coty
si NU am fost cu ideea sa faceti o pagina de statistici pt probleme = grea/usoara, ca ar fi ceva total subiectiv si ar varia pt acelasi concurent de la momentu cand vede ca ia 70 (variante, alte punctaje mai mici) la o problema pana cand o rezolva total


nu a zis nimeni ca se clasifica ca grea/usoara
pur si simplu o pagina in care sa se arate pt fiecare problema o statistica cu numarul de useri care au luat maxim la poblema, numarul de "incarcari" mediu per user, numarul mediu de puncte per concurent sau altele..
toate puse in aceeasi pagina; ca asa cum e acum e putin mai greu sa iei fiecare problema pe o pagina/ tab separat si sa vezi numarul mediu de puncte si/sau numarul de useri care au rezolvat-o

Citat din mesajul lui: Coty
ultimu tau post e o parcurgere in adancime... sau ce?

"Post subject: sortare topologica" Wink

Citat din mesajul lui: Coty
si daca merge in continuare, eu zic ca merge... nu garantez... si tot devine mancator de timp ca pt i, ii determinam al k-lea stramos in O(1), dar trebuie sa copiem lista stramosului a... complicat, nu cred ca merge Annoyed

adica am scris atata degeaba?! Aha
... macar implementeaza ideeile pe care le ai, vezi cat iei/ daca iei ceva; apoi vino inapoi aici si scrie-ne care a fost finalul; practice!  Weightlift
Memorat
Coty
Nu mai tace
*****

Karma: 6
Deconectat Deconectat

Mesaje: 235



Vezi Profilul WWW
« Răspunde #33 : Decembrie 28, 2005, 22:43:22 »

nu citisem subiectu Tongue ...

cat despre pagina de statistici, ati putea sa puneti un link pe pagina problemei... dar cum deja sunt 166 probleme numa la arhiva (poate or mai fi si in rest, nu am prea cautat Wink )... o sa stati o vreme... si poate daca se poate, un grafic cu punctaje ceva... nush... doar sugestii...

[later edit]
exista deja linkul... discutia devine off topic Sad

[later edit 2]
nu ai scris de geaba, daca da cineva search la "sortare topologica" gaseste aici... Tongue
si macar eu am inteles cat de cat ce vrea de la mine, conceptu (= sortam dupa proprietatea de a avea x ceva)... si asta e scopul forumului, nu?
Multumesc de explicatie! Pray
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #34 : Decembrie 28, 2005, 22:47:09 »

Citat din mesajul lui: Coty
nu citisem subiectu Tongue ...

cat despre pagina de statistici, ati putea sa puneti un link pe pagina problemei... dar cum deja sunt 166 probleme numa la arhiva (poate or mai fi si in rest, nu am prea cautat Wink )... o sa stati o vreme... si poate daca se poate, un grafic cu punctaje ceva... nush... doar sugestii...

[later edit]
exista deja linkul... devine off topic Sad


... pune sugestiile in categoria lor pe forum!
Memorat
u-92
Vizitator
« Răspunde #35 : Decembrie 28, 2005, 23:38:56 »

ar trebui sa iei o carte si sa citesti despre grafuri si dupa aia n-o sa mai ai probleme.. asa e cam nasol sa-ti explice cineva pe forum ce e aia df, ca e chestie de baza.. un inceput ar fi cormenul sau un manual de a 11a

si n-ar trebui sa pleci de la ideea ca aici te opresti, ca celelalte probleme is prea grele.. daca te pui pe ele si studiezi materialul necesar le rezolvi pana la urma, bafta  Thumb up
Memorat
cristi8
Vizitator
« Răspunde #36 : Decembrie 29, 2005, 16:24:10 »

Citat din mesajul lui: Coty
pei daca era, atunci ... cum sa zic, pentru tatal lui i (pe care deja il procesasem) puteam sa retin intr-un fel lista de stramosi, asa ca al k-lea stramos al lui i era al (k-1)-lea stramos al lui a... da daca nu e... Sad ramane de vazut


oricum ideea ta e proasta. nu o sa poti sa raspunzi asa in O(1) la intrebari "care e al k-lea stramos al lui i ?".
Memorat
Coty
Nu mai tace
*****

Karma: 6
Deconectat Deconectat

Mesaje: 235



Vezi Profilul WWW
« Răspunde #37 : Decembrie 29, 2005, 17:10:36 »

de ce nu as putea?... as putea, dar ar fi total dezavantajos... nu stiu daca m-ati inteles, dar ... vreau sa bag toti stramosii lui i intr-un vector si sa afisez in O(1), dar risc sa fie mai mancator de timp... mai vad
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #38 : Decembrie 29, 2005, 18:35:06 »

Citat din mesajul lui: Coty
de ce nu as putea?... as putea, dar ar fi total dezavantajos... nu stiu daca m-ati inteles, dar ... vreau sa bag toti stramosii lui i intr-un vector si sa afisez in O(1), dar risc sa fie mai mancator de timp... mai vad


vectorul ala o sa aiba N elemente * N noduri = N*N si ca sa calculezi deci toti stramosii pt toate nodurile o sa iti iasa O(N*N) complexitate
Memorat
ditzone
Vizitator
« Răspunde #39 : Decembrie 30, 2005, 10:24:28 »

Nu neaparat... folosindu-se un DFS, se mentine o stiva cu stramosii elementului respectiv in care un element o sa se bage si o sa se scoata o singura data ( ca la problema Cerere ) -> O( n )
Memorat
Coty
Nu mai tace
*****

Karma: 6
Deconectat Deconectat

Mesaje: 235



Vezi Profilul WWW
« Răspunde #40 : Ianuarie 02, 2006, 22:52:12 »

ok, am aflat ce e aia DF, am implementat (pt fiecare nod retin stramosii lui)... dar astfel ajung la o matrice de n*n... ceea ce iese cu muuuuuuult din ce imi trebuie  Shocked idei de micsorare a matricei?

btw, DFul il fac iterativ (am vazut mai sus ca iese din stiva pt recursiv) iar algoritmul merge ca altfel nu luam 30 de puncte (este SIGUR din dimensiunea matricei)
Memorat
u-92
Vizitator
« Răspunde #41 : Ianuarie 02, 2006, 23:00:33 »

cauta si despre metode de reprezentare a grafurilor.. se poate n+m, unde m e numarul de muchii
Memorat
Coty
Nu mai tace
*****

Karma: 6
Deconectat Deconectat

Mesaje: 235



Vezi Profilul WWW
« Răspunde #42 : Ianuarie 02, 2006, 23:13:09 »

da, cu alocare dinamica in loc de matrice... dar cum fac atunci apel la un element anume din lista? fara sa ma deplasez in ea cu
Cod:

   element_curent <- element_curent.urmatorul

ca din cate stiu eu in pascal nu se poate... in C e chestia aia a
  • -y, unde x e varful al carui stramos trebuie sa il aflam, y al catelea stramos, iar a
  • este stiva, cu varful = x
[later edit]
alte metode n-am gasit, adica am gasit, dar nu se pot aplica aici... Sad sau nu am cautat unde trebuie
si am gresit, metoda asta ar avea nevoie de mai mult de n+m... deci trebuie sa mai caut
acu fac DF pt fiecare intrebare... si mai nasol Sad iau 10

[later edit 2]
m-am facut de ras... merge si in Free Pascal sa am
Cod:

 var p:^integer;
 begin
  ...
  p:[email protected];
  writeln((p+2)^);
 end.

dar... am o vaga impresie ca daca ii fac referinta catre stiva DE LA UN MOMENT DAT, pe care o modific ulterior, si ii cer pointerului sa imi afiseze al y-lea element, el o sa afiseze total altceva... ca doar s-a modificat stiva Sad deci ce optiuni am?
Memorat
u-92
Vizitator
« Răspunde #43 : Ianuarie 03, 2006, 00:07:07 »

nu prea am inteles ce vrei sa zici.. eu ziceam ca de exemplu ai asa:
Cod:

int G[MAXN][MAXN];

unde G
  • = nr de vecini ai lui x, si G
  • = al i'lea vecin al lui x

deci de fiecare data cand citesti o muchie x-y:
Cod:

G[x][ ++G[x][0] ] = y, G[y][ ++G[y][0] ] = x;


si daca aloci dinamic matricea obtii n+m memorie.
Memorat
Coty
Nu mai tace
*****

Karma: 6
Deconectat Deconectat

Mesaje: 235



Vezi Profilul WWW
« Răspunde #44 : Ianuarie 03, 2006, 11:28:22 »

nu cred ca mai e nevoie sa fac si  g[y][...] pentru ca e arbore... chiar am nevoie de urmasi?

am prins ideea, dar iese o matrice (cum ai declarat-o si tu, g[nmax,nmax]) de n*n=250000^2 = imens... asta faceam si eu... exact matricea asta, intr-un DF nerecursiv, foloseam o stiva si cand ajungeam cu stiva[varf]=x actualizam coloana x din matrice cu stiva de la acel moment... si continuam DF-ul... dar iese matricea prea mare...
daca o fac dinamic am doua variante:
 - ori fac liste si obtin aceeasi complexitate (pt timp) ca si cand as cauta pe v[v[v[v[...[v[g]]...] in mod iterativ (nefolositor)
 - ori fac o matrice de pointeri spre varful stivei, dar asta ziceam - ca se modifica stiva in timpul DF-ului... adica am :
Cod:

var st:array[1..250000]of longint; {stiva}
      a:array[1..250000]of ^longint;{pointerul catre varful stivei LA UN                                                            MOMENT DAT}
procedure _df(ceva);
begin
 while ceva do { un while care modifica stiva }
           begin
{            mai fac un pas in parcurgere.. ajung sa zicem pe nodul x}
              a[x]:[email protected][vf] ; {vf-varful, fac un pointer spre varful ei}
           end;
end;

begin {main}
{ citire, DF}
 for ask:=1 to m {pt fiecare intrebare}
{        afisez } writeln((a[x]+y)^); {al y-lea stramos al lui x}
end.


imi cer scuze daca e prea explicit... se poate sterge, oricum lipsesc conditiile si algoritmul e destul de banal... si sper ca intelegeti ce am vrut sa fac... si unde pot optimiza, ca eu nu stiu Eh?
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #45 : Ianuarie 03, 2006, 12:11:07 »

Citat din mesajul lui: Coty
am prins ideea, dar iese o matrice (cum ai declarat-o si tu, g[nmax,nmax]) de n*n=250000^2 = imens...

ai uitat ceva din ce a zis u-92: "si daca aloci dinamic matricea obtii n+m memorie."

Cod:
sa zicem ca in gr[i] se tin numarul de vecini ai lui i; (comun)

daca lucrezi in C, poti sa faci (int *) g[nmax] <- aloca memorie pt exact numarul de vecini (g[i] <- aloca gr[i]*int memorie);
deci g[1] are gr[1] elemente; g[2] are gr[2] elemente; si poti sa le accesezi ca g[x][y]

daca lucrezi in pascal, poti sa tii un vector v[nmax] in care tii minte vecinii pt nodul 1, apoi vecinii pt nodul 2, apoi vecinii pt nodul 3, si tot asa
adica primele gr[1] elemente din v, sunt vecinii nodului 1, urmatoarele gr[2] elemente sunt vecinii nodului 2, si tot asa
poti sa mai tii minte un vector s[nmax] in care tii minte pt elementul i pozitia de start in vectorul v a nodului i;
adica de unde incep vecinii nodului i
« Ultima modificare: Aprilie 05, 2006, 14:48:46 de către svalentin » Memorat
Crusher
Strain


Karma: -2
Deconectat Deconectat

Mesaje: 11



Vezi Profilul
« Răspunde #46 : Februarie 23, 2006, 12:25:05 »

Imi mai puteti da un exemplu sa-mi dau seama unde gresesc?
preaty please whith sugar on top!! Angel
Memorat
filipb
Nu mai tace
*****

Karma: 232
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« Răspunde #47 : Februarie 23, 2006, 16:05:54 »

Chestia cu cerutul exemplelor pe forum e cel putin "ciudata". Adica in timpul unui concurs cui mai ceri sa iti faca teste? Sau ceri direct testele oficiale? :lol:
Memorat
cristy
De-al casei
***

Karma: 2
Deconectat Deconectat

Mesaje: 136



Vezi Profilul
« Răspunde #48 : Martie 28, 2006, 20:21:38 »

am incercat problema...stiu ca ar trebui sa o fac...dupa ce scrie pe forum...dar nu am decat 90 de pct...am un TLE...cand pe testul 9...cand pe testul 10...am un NLogN+MLogN...este vreun shmen ce traba facut?...
Memorat

... lipsa de inspiratie ...
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« Răspunde #49 : Martie 28, 2006, 23:34:43 »

poti face si in O(n+m) dar merge si varianta ta. mai optimizeaza putin.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
Pagini: 1 [2] 3 4   În sus
  Imprimă  
 
Schimbă forumul:  

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