infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Dan-Leonard Crestez din Martie 08, 2004, 20:01:13



Titlul: 010 Stramosi
Scris de: Dan-Leonard Crestez din Martie 08, 2004, 20:01:13
Aici puteţi discuta despre problema Stramosi (http://infoarena.ro/problema/stramosi).


Titlul: Complexitate problema stramosi
Scris de: Chris din August 05, 2004, 17:46:25
Buna :D !!

Care este complexitatea "oficiala" la problema stramosi ?

Eu am trimis o sursa cu complexitate (N+M)*log(N) si imi merg 9 teste (nu mi se incadreaza in timp al 9 - lea test!!!). Am incercat sa optimizez programul si tot 90 de puncte ia (in for-ul de la 1 la m am operatii rapide - incrementari, atribuiri, "&" pe biti, si shiftari)... Exista cumva o complexitate mai buna ????? (sau singura metoda de a lua 100 de puncte e sa rescriu codul in limbaj de asamblare).


Titlul: 010 Stramosi
Scris de: andreit1 din August 07, 2004, 22:37:05
Exista o solutie de complexitate n+m*log(n) care e suficienta pentru 100 de puncte. Deci probabil ar fi bine sa lasi deoparte rezolvarea gasita de tine si sa cauti alta.


Titlul: 010 Stramosi
Scris de: Cristian Strat din August 12, 2004, 01:33:32
multi au luat 80-90 de puncte la aceasta problema pentru ca au spart linia de cache de prea multe ori (eg. in loc sa mearga in principal pe linii si dupa aceea pe coloane - asa cum ai citi dintr-o carte sau, mai bine zis, din RAM  :lol: ) au mers cu indicii rasturnati.


Titlul: Heeeeeelp!
Scris de: Chris din August 28, 2004, 14:21:48
:cry: Sincer sa fiu, nu prea am idei pentru complexitate N+M*log(N). Putin ajutor, va rog !!! Pentru fiecare nod retin stramosii cu ordinul putere a lui 2, si pentru a afla al k lea stramos folosesc reprezentarea binara a lui k pt descompunere!! (poate chestia asta imi cam da peste cap cache-ul!!) (desi folosesc numai shiftari, atribuiri si & pe biti (care iau in jur de 1 ciclu de procesor!))


Titlul: Re: Heeeeeelp!
Scris de: Mircea Pasoi din August 28, 2004, 17:32:29
Citat din mesajul lui: Chris
:cry: Sincer sa fiu, nu prea am idei pentru complexitate N+M*log(N). Putin ajutor, va rog !!! Pentru fiecare nod retin stramosii cu ordinul putere a lui 2, si pentru a afla al k lea stramos folosesc reprezentarea binara a lui k pt descompunere!! (poate chestia asta imi cam da peste cap cache-ul!!) (desi folosesc numai shiftari, atribuiri si & pe biti (care iau in jur de 1 ciclu de procesor!))


Probabil ca tu ai acolo acolo o matrice A[j] care zice al 2^j-lea stramos al nodului i... incearca sa tii in schimb in A[j] = al 2^i-lea stramos al nodului j (inverseaza dimensiunile).. vezi daca merge


Titlul: Thanks!
Scris de: Chris din Septembrie 01, 2004, 17:33:14
:D Mersi pentru sfat!!!! Am luat 100 de puncte daca am inversat indicii si am optimizat citirea/scrierea in fisier!!!


Titlul: 010 Stramosi
Scris de: cristi8 din Februarie 25, 2005, 11:49:29
mmm... eu am facut O(N+M) si am luat 100... seamana f mult cu problema "cerere", dar mai trebuiau niste kestii in plus..


Titlul: 010 Stramosi
Scris de: Bogdan-Cristian Tataroiu din Martie 16, 2005, 18:59:02
La problema aceasta e a treia oara cand mi se imtampla urmatorul lucru: fac problema recursiv si... doua teste ratate din cauza ca stiva e prea mica. Am stat mult pana sa-mi dau seama de ce imi da RUN ERROR - Invalid memory reference
E vreo metoda de a mari stiva cu 100-200 kilo astfel incat sa mearga o rezolvare recursiva? Nu pot sa fac si eu cautare in adancime recursiva... :(

Scuzati repetitia excesiva a cuvantului recursiv...


Titlul: 010 Stramosi
Scris de: VladS din Martie 16, 2005, 19:01:18
Poti sa simulezi stiva prin folosirea unui vector. Astfel algoritmul devine iterativ.


Titlul: 010 Stramosi
Scris de: Mircea Pasoi din Martie 16, 2005, 19:21:12
Citat din mesajul lui: bogdan2412
La problema aceasta e a treia oara cand mi se imtampla urmatorul lucru: fac problema recursiv si... doua teste ratate din cauza ca stiva e prea mica. Am stat mult pana sa-mi dau seama de ce imi da RUN ERROR - Invalid memory reference
E vreo metoda de a mari stiva cu 100-200 kilo astfel incat sa mearga o rezolvare recursiva? Nu pot sa fac si io cautare in adancime recursiva... :(

Scuzati repetitia excesiva a cuvantului recursiv...


Eu am implementat DF-ul recursiv si mi-a mers de 100  :-s


Titlul: 010 Stramosi
Scris de: Valentin Stanciu din Martie 16, 2005, 19:58:03
Vezi daca poti sa mai elimini din variabilele care le transferi functii!


Titlul: 010 Stramosi
Scris de: Iorgulescu Calin din Mai 04, 2005, 21:09:36
La problema asta, prima mea idee a fost pur si simplu sa scriu o functie recursiva care sa il intoarca pe a[a[a[a[a[a[a[a[....[q]]]]]]..]], unde a este vectorul. O astfel de abordare mi-a adus 80 de puncte. Luam TLE la ultimele 2. Am incercat sa retin stramosii 2^K, si am facut asta folosind o functie similara, dar asa, chiar si cu putine optimizari am luat 70 de puncte (3 TLE-uri).  :cry:  Cum as putea sa memorez mai repede stramosii de ordin 2^K decat parcurgand vectorul de tati pt. fiecare si cand ajung la o putere de a lui 2 sa o retin? Poate cineva sa ma ajute?


Titlul: 010 Stramosi
Scris de: Ionel Corneliu Gog din Mai 04, 2005, 21:34:48
Ai facut si cu operatii pe biti? Mai este o alta metoda de rezolvare asemanatoare cu cea de la problema Cerere, este si ceva hint la articole.
 8)


Titlul: 010 Stramosi
Scris de: Chris din Mai 05, 2005, 14:18:26
Poti sa calculezi matricea a[logN][N] , unde a[k] = cel de-al 2^k-lea stramos al lui i. O poti calcula in O(N*log(N)) prin relatia de recurenta :
a[k] = a[k-1][ a[k-1] ] (te folsesti de ce ai calculat deja).
Eu am obtinut 100 de puncte cu chestia asta (se raspunde la fiecare intrebare in O(log(N))) dar poti face ceva asemanator rezolvarii la problema "cerere" si sa raspunzi in O(1).


Titlul: 010 Stramosi
Scris de: Iorgulescu Calin din Mai 05, 2005, 19:46:52
Am reusit.  \:D/  Mersi Chris. Aici greseam. imediat ce am facut ca tine am luat 100. Trebuia sa imi fii dat seama k avand im matrice precedentul pot determina curentul. #-o  #-o  #-o  :oops:  :oops:  :oops:

Mersi mult si bafta in continuare!  :wink:


Titlul: ??
Scris de: vladut.forum din Iulie 29, 2005, 18:58:48
Eu iau numai 40 pct si nustiu de ce... matricea A o calculez corect
Cod:

fin>>p>>q;
stramos=p;

while (q>0) {
rr=1; count=0; varza=q;
while (varza>0) {count++; varza/=2;rr*=2;} rr/=2; count--;
      q-=rr;
      stramos=v[count][stramos];
      rr/=2;
      count--;
   }
  fout<<stramos<<'\n';
          }

ce  am gresit in aflarea al q-lea stramos a lui p... la ultimele doua teste iau TLE iar la restu WA si Correct (in total 40 puncte)


Titlul: 010 Stramosi
Scris de: vladut.forum din Iulie 30, 2005, 12:17:54
Acum am facut alfel, fac reprezentarea binara a lui Q... si aflu exact ce si cum.. acu astept sa reina evaluatorul ca vad ca e oprit pentru un timp...


Titlul: 010 Stramosi
Scris de: Bogdan-Alexandru Stoica din Decembrie 06, 2005, 11:53:19
io fac 4*N+M*log(N) (nu fac liste, fac cu alocare dinamica) si iau TLE la ultimele 2 teste...  ](*,)
1.2 e "la limita" dupa parerea mea. ar trebui sa fie un pic mai mult timp


Titlul: 010 Stramosi
Scris de: Bogdan-Cristian Tataroiu din Decembrie 06, 2005, 13:33:25
Poti s-o faci oricand in O(N + M)  :-'


Titlul: 010 Stramosi
Scris de: Bogdan-Alexandru Stoica din Decembrie 06, 2005, 20:27:25
pai am facut o(N+M), dar vreau sa iau max si cu solutia N+M*log(N)  :-'


Titlul: 010 Stramosi
Scris de: Sima Mihai Cotizo -vechi din Decembrie 28, 2005, 21:29:02
daca a e tatal lui i, avem neaparat a<i (ca valoare) ???


Titlul: 010 Stramosi
Scris de: Bogdan-Cristian Tataroiu din Decembrie 28, 2005, 21:44:39
Nu cred ca e neaparat, dar, totusi, la ce-ti trebuie sa stii asta? 8-[


Titlul: 010 Stramosi
Scris de: Sima Mihai Cotizo -vechi din Decembrie 28, 2005, 21:46:38
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... :( ramane de vazut


Titlul: 010 Stramosi
Scris de: Valentin Stanciu din Decembrie 28, 2005, 21:54:43
nu stiu daca am inteles exact ce zici, dar daca da, incearca sa faci o sortare topologica si o sa se aplice conditia intrebata de tine (tatal lui i e in stanga lui i in sirul sortat topologic)

sau.. poti sa aplici aceeasi gandire, dar nu parcurgi nodurile de la 1 la N, ci de la radacina la frunza printr-o parcurgere in adancime ceva..


Titlul: 010 Stramosi
Scris de: Sima Mihai Cotizo -vechi din 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 :P
cat despre parcurgere in adancime sau ce ai zis... ia-ma usor, ca nu stiu grafuri sau arbori... :( 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


Titlul: 010 Stramosi
Scris de: Bogdan-Cristian Tataroiu din Decembrie 28, 2005, 22:05:01
Daca nu stii grafuri (macar chestiile de baza, de genu parcurgeri in adancime) fa alta problema mai bine :) Dupa ce mai citesti ceva si mai faci niste probleme mai simple o faci si pe asta


Titlul: 010 Stramosi
Scris de: Valentin Stanciu din 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 :P


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 :) )

... 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 :)

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))


Titlul: 010 Stramosi
Scris de: Sima Mihai Cotizo -vechi din 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... :) si btw.. repet, daca tine de grafuri (muchii, noduri...) atunci... cred ca o sa ai un pic de furca :) 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]


Titlul: 010 Stramosi
Scris de: Valentin Stanciu din 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..)


Titlul: Răspuns: 004 Sortare topologica
Scris de: Valentin Stanciu din 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


Titlul: 010 Stramosi
Scris de: Sima Mihai Cotizo -vechi din Decembrie 28, 2005, 22:28:38
:P 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  ](*,)

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

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:


Titlul: 010 Stramosi
Scris de: Valentin Stanciu din 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" ;)

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:


Titlul: scuze... si ma reapuc de treaba
Scris de: Sima Mihai Cotizo -vechi din Decembrie 28, 2005, 22:43:22
nu citisem subiectu :P ...

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 ;) )... 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 :(

[later edit 2]
nu ai scris de geaba, daca da cineva search la "sortare topologica" gaseste aici... :P
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! [-o<


Titlul: Re: scuze... si ma reapuc de treaba
Scris de: Valentin Stanciu din Decembrie 28, 2005, 22:47:09
Citat din mesajul lui: Coty
nu citisem subiectu :P ...

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 ;) )... 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 :(


... pune sugestiile in categoria lor pe forum!


Titlul: 010 Stramosi
Scris de: u-92 din 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  :thumbup:


Titlul: 010 Stramosi
Scris de: cristi8 din 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... :( 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 ?".


Titlul: 010 Stramosi
Scris de: Sima Mihai Cotizo -vechi din 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


Titlul: 010 Stramosi
Scris de: Valentin Stanciu din 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


Titlul: 010 Stramosi
Scris de: ditzone din 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 )


Titlul: 010 Stramosi
Scris de: Sima Mihai Cotizo -vechi din 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  :shock: 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)


Titlul: 010 Stramosi
Scris de: u-92 din Ianuarie 02, 2006, 23:00:33
cauta si despre metode de reprezentare a grafurilor.. se poate n+m, unde m e numarul de muchii


Titlul: 010 Stramosi
Scris de: Sima Mihai Cotizo -vechi din 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... :( 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 :( iau 10

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

 var p:^integer;
 begin
  ...
  p:=@array;
  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 :( deci ce optiuni am?


Titlul: 010 Stramosi
Scris de: u-92 din 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.


Titlul: 010 Stramosi
Scris de: Sima Mihai Cotizo -vechi din 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]:=@st[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 :-s


Titlul: 010 Stramosi
Scris de: Valentin Stanciu din 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


Titlul: 010 Stramosi
Scris de: Tira Cristian din Februarie 23, 2006, 12:25:05
Imi mai puteti da un exemplu sa-mi dau seama unde gresesc?
preaty please whith sugar on top!! O:)


Titlul: 010 Stramosi
Scris de: Filip Cristian Buruiana din 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:


Titlul: 010 Stramosi
Scris de: Rus Cristian din 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?...


Titlul: 010 Stramosi
Scris de: Andrei Grigorean din Martie 28, 2006, 23:34:43
poti face si in O(n+m) dar merge si varianta ta. mai optimizeaza putin.


Titlul: Re: 010 Stramosi
Scris de: Sima Mihai Cotizo -vechi din Iulie 18, 2006, 15:07:11
(in primul rand mai citeste o data thread-ul ca sa vezi ca nu sunt primul care zice) incearca sa inversezi in matricea de stramosi indicii...

si acum intrebarea:
OK, sa zicem ca acum am citit pe net ( pe forum ) si am aflat ca programul meu sparge cache-ul... dar: de unde imi dau seama asta in timp de concurs? mereu e mai rapid sa citesti pe linie si pe urma pe coloana din memorie? (presupun ca raspunsul este DA) dar daca in timpul concursului ne lovim de problema asta, e o idee sa schimbam mereu indicii?

[later edit]
uitasem ce scrisesem in iarna  :rotfl: numai idiotenii... intre timp mi-a iesit problema, si mi-a iesit din cap ideea cu o matrice de n*n


Titlul: Re: 010 Stramosi
Scris de: Valentin Stanciu din Iulie 19, 2006, 19:12:34
ca idee, sa nu ai probleme cu cacheul, ar fi folositor sa incerci sa iti imaginezi cum o sa acceseze programul memoria, si totodata cum e tinuta matricea in memorie..
adica stii ca memoria e liniara, iar celelalte dimensiuni pur si simplu se aloca in continuarea ultimei parti, exemplu:
{{1 2 3}
{4 5 6}
{7 8 9}}
se tine minte in memorie 1 2 3 4 5 6 7 8 9 (sper sa nu ma insel..); ori daca programul tau le ia in ordinea 7 4 1 8 5 2 9 6 3, vezi ce se intampla? e bine sa accesezi elementele in oridine crescatoare tot timpul ca sa faca cache; daca le accesezi random, nu poate sa faca "read-ahead" si va trebui accesata memoria la fiecare operatie
daca nu stii exact la ce se refera "cache": daca tu accesezi elementul 1, apoi elementul 2, apoi elementul 3, apoi 4; controllerul de memorie isi da seama ca accesezi liniar si citeste din memorie 3 si 4 in acelasi timp in care citeste si 2 (read-ahead) si tine aceste valori intr-o zona tampon, mai rapida, dar mai mica (cache) .. asta se aplica la hardiscuri sigur, la procesor cred ca e putin mai complicat, ca in cache se tin anumite variabile mai des folosite, care pot fi fortat tinute sau dupa un algoritm (register int i de exemplu forteaza ca i sa fie tinut in cache)

pe scurt, incearca sa accesezi memoria cat mai "frumos" :) si eventual sa lucrezi cu puteri ale lui 2..

.. daca gresesc undeva, imi cer scuze, nu am citit undeva EXACT cum se fac aceste operatii si tot ce am scris este din propriile deductii din bucati de informatii :)


Titlul: Raspuns: 010 Stramosi
Scris de: Savin Tiberiu din Iulie 19, 2006, 21:12:07
stiu ca ar putea parea stupid dar cum fac DF in o(n)  :D eu il fac in N^2 si imi iesa din timp pe 5 teste. Aceeasi problema o am si la cerere si nush cum sa o rezolv.


Titlul: Re: 010 Stramosi
Scris de: Valentin Stanciu din Iulie 19, 2006, 22:27:27
tii vecinii unui nod intr-o lista de adiacenta.. si daca stai sa calculezi complexitatea iese O(N+M)

Edit: initial am scris O(N), sorry!


Titlul: Raspuns: 010 Stramosi
Scris de: Cosmin Negruseri din Iulie 20, 2006, 16:05:40
O(n + m) ...


Titlul: Raspuns: Re: 010 Stramosi
Scris de: blasters din Noiembrie 17, 2006, 17:27:01
ca idee, sa nu ai probleme cu cacheul, ar fi folositor sa incerci sa iti imaginezi cum o sa acceseze programul memoria, si totodata cum e tinuta matricea in memorie..
adica stii ca memoria e liniara, iar celelalte dimensiuni pur si simplu se aloca in continuarea ultimei parti, exemplu:
{{1 2 3}
{4 5 6}
{7 8 9}}
se tine minte in memorie 1 2 3 4 5 6 7 8 9 (sper sa nu ma insel..); ori daca programul tau le ia in ordinea 7 4 1 8 5 2 9 6 3, vezi ce se intampla? e bine sa accesezi elementele in oridine crescatoare tot timpul ca sa faca cache; daca le accesezi random, nu poate sa faca "read-ahead" si va trebui accesata memoria la fiecare operatie
daca nu stii exact la ce se refera "cache": daca tu accesezi elementul 1, apoi elementul 2, apoi elementul 3, apoi 4; controllerul de memorie isi da seama ca accesezi liniar si citeste din memorie 3 si 4 in acelasi timp in care citeste si 2 (read-ahead) si tine aceste valori intr-o zona tampon, mai rapida, dar mai mica (cache) .. asta se aplica la hardiscuri sigur, la procesor cred ca e putin mai complicat, ca in cache se tin anumite variabile mai des folosite, care pot fi fortat tinute sau dupa un algoritm (register int i de exemplu forteaza ca i sa fie tinut in cache)

pe scurt, incearca sa accesezi memoria cat mai "frumos" :) si eventual sa lucrezi cu puteri ale lui 2..

.. daca gresesc undeva, imi cer scuze, nu am citit undeva EXACT cum se fac aceste operatii si tot ce am scris este din propriile deductii din bucati de informatii :)


Am impresia ca daca  matricea respectiva are marimi numere puteri ale lui 2 se acceseaza mai repede un element aleator din matrice

int a[1024][1024]; // de exemplu


Titlul: Raspuns: 010 Stramosi
Scris de: Cojocaru Alexandru din Decembrie 15, 2006, 17:13:13
E testul 10 mai special? Ca la el am luat TLE, WA si SIGSEGV (cu surse diferite desigur).


Titlul: Raspuns: 010 Stramosi
Scris de: Mircea Dima din Decembrie 15, 2006, 18:46:32
E testul 10 mai special? Ca la el am luat TLE, WA si SIGSEGV (cu surse diferite desigur).

Cred ca unele teste sunt mai mari decat scrie in textul problemei

Pune si tu
#define maxn 350 000
#define maxm 400 000

eu luam 80 daca puneam

#define maxn 250 000
#define maxm 300 000


Titlul: Raspuns: 010 Stramosi
Scris de: Paul-Dan Baltescu din Decembrie 15, 2006, 19:01:37
Daca ai vectorul a[maxn], inseamna ca vectorul a contine maxn pozitii: 0...maxn-1, asa ca daca indexai de la 1 se explica de ce luai sigsegv. Se recomanda sa declari vectorii un pic mai mari decat ai nevoie, preferabil o putere a lui 2, dar nu prea mari (pentru ca prea multa memorie declarata face programul sa ruleze mai incet).


Titlul: Raspuns: 010 Stramosi
Scris de: Cojocaru Alexandru din Decembrie 15, 2006, 20:57:36
Tot nu merge. Ma gandeam... P poate sa fie 0? Si daca da, in acest caz se afiseaza Q, nu?


Titlul: Raspuns: 010 Stramosi
Scris de: Mircea Dima din Decembrie 15, 2006, 21:25:05
Daca ai vectorul a[maxn], inseamna ca vectorul a contine maxn pozitii: 0...maxn-1, asa ca daca indexai de la 1 se explica de ce luai sigsegv. Se recomanda sa declari vectorii un pic mai mari decat ai nevoie, preferabil o putere a lui 2, dar nu prea mari (pentru ca prea multa memorie declarata face programul sa ruleze mai incet).

aveam 250 005 si 300 005
dar am incercat si valori mai mari.... pana m-am enervat si am pus 350 000 si 400 000

nush... probabil accesam memorie aiurea :|

PS stiam faza cu 2^n ;))


Titlul: Raspuns: 010 Stramosi
Scris de: Savin Tiberiu din Decembrie 24, 2006, 08:14:27
testele respecta conditiile din enunt. Eu am luat 100 cu o sursa care avea:
#define NMAX 250001
iar matricea in care retin stramosi e declarata a[20][NMAX] so try something else.


Titlul: Raspuns: 010 Stramosi
Scris de: Mierla Laurentiu Marian din Februarie 10, 2007, 19:05:45
Am si eu o intrebare legata de evaluator
Pentru fiecare test primesc "Non-zero exit status"
Ce ar trebui sa insemne asta, avand in vedere ca lucrez in Pascal?
 


Titlul: Raspuns: 010 Stramosi
Scris de: Paul-Dan Baltescu din Februarie 10, 2007, 19:22:42
Runtime Error, daca nu ma insel :).


Titlul: Raspuns: 010 Stramosi
Scris de: Sima Cotizo din Februarie 11, 2007, 00:50:48
Daca faci halt; cumva in program, incearca halt(0)... sau si la exit parca era la fel... [cred ca daca era RTE atunci zicea si care... :-? ]


Titlul: Răspuns: 010 Stramosi
Scris de: Florian Marcu din Noiembrie 19, 2007, 17:59:47
Eu vreau sa incerc sa rezolv problema cu ajutorul acelei matrici [logN][N]. Am rezolvat-o recursiv (calculand a[a[a[a..a[q]]]..]]]) si am luat doar 80. Problema e ca nu prea inteleg cum se calculeaza matricea aceea. Nu prea imi dau seama de relatia de generare.  Fac cam asa:
*calculez separat prima linie: b[1][ i ]=a [ a ( i ) ];
*k=2;
*while(2^k<=n)
      {
       for(i=1;i<=n;++i) b[k][ i ]=a[b[k-1][i-1]]; // AICI E PROBLEMA!
       ++k;
      }
*continui rezolvarea;

b[][] e matricea care trebuie generata, iar a[] e vectorul initial. Care e relatia de recurenta? [daca ma poate ajuta cineva]. :|


Titlul: Răspuns: 010 Stramosi
Scris de: Adrian Diaconu din Noiembrie 19, 2007, 22:59:13
Trebuie sa ai ceva de genu b[ k ][ i ] = b[ k-1 ][ b[ k-1 ][ i ] ]. Iei al 2k-1-lea parinte al celui de al 2k-1-lea parinte al lui i adica al 2k-lea parinte al lui i.


Titlul: Răspuns: 010 Stramosi
Scris de: Florian Marcu din Noiembrie 20, 2007, 16:26:02
Multumesc pt ajutor. Am facut cu matrice si iau tot 80 de puncte cu tle pe ultimile 2. Banuiesc ca problema e ca eu gasesc cel mai mic nr k, astfel incat 2^k<=p. Si apoi aflu a[a[a[b[k][q]]]]]. Deci practic, matricea aia ma ajuta sa scap de cateva apelari a functiei cu care creez recursivitatea. Iese insa din timp, si intrebarea care imi vine in minte este daca se poate da raspunsul in O(1). Citisem insa pe forum ca raspunsul se da in log(n). Eu asa cred k am. Acum cred ca intervine faza aia cu linia de cache. Eu memorez in b(i,j) al 2^i-lea stramos al membrului j. Trebuie sa inversez dimensiunile?  :?


Titlul: Răspuns: 010 Stramosi
Scris de: Adrian Diaconu din Noiembrie 20, 2007, 21:43:28
Pai ideea e sa faci log(n) query-ul. Gasesti k maxim astfel incat 2k<=p. Apoi mai trebuie sa afli al p-2k-lea stamos al lui b[k][q] lucru care il faci recursiv ( gasesti iar k' maxim astfel incat 2k'<= p-2k... si tot asa) pana cand ajungi cu p=0 caz pentru care raspunsul este nodul insusi.

Sper ca se intelege din ce am explicat.


Titlul: Răspuns: 010 Stramosi
Scris de: Florian Marcu din Noiembrie 21, 2007, 17:24:05
Da. Am inteles foarte bine. Multumesc de ajutor.  :)


Titlul: Răspuns: 010 Stramosi
Scris de: Mari n din Februarie 17, 2008, 22:59:06
Am facut o parcurgere in adancime. Am incercat sa merg pe aceeasi idee ca la problema cerere (la care am luat 100p). Pentru fiecare nod tin o lista de cereri pentru stramosii lui (memorez in noduri stramosul cerut si pozitia in lista de cereri).
In parcurgerea in adancime, tin o stiva cu nivele si cand sunt la un nod, parcurg lista de cereri si caut in stiva de nivele.  Complexitate n+m
Iau 80 p, pe testul 9 WA iar pe 10 Killed by signal 11.
Ce gresesc ?


Titlul: Răspuns: 010 Stramosi
Scris de: Mari n din Februarie 17, 2008, 23:06:24
Da, mi-am dat seama, vectorul cu intrebari il puneam tot de 250000 ...


Titlul: Răspuns: 010 Stramosi
Scris de: Iacob Eduard din Octombrie 25, 2008, 00:29:05
Va rog ajutati-ma putin.Dupa lungi "chinuieli",am reusit sa inteleg si eu cum sa fac algoritmul.L-am implementat,si merge(pentru 2 teste,care le-am facut eu).Problema e ca atunci cand trimit sursa imi zice la toate SIGSEGV.
Precizez ca matricea mea are dimensiunea matrice[20][250001](am calculat ca matricea nu are cum sa aiba mai mult de 20 linii ,pt ca inseamna 2^20>250000).Daca declar matricea cu dimensiunile [20][100],la primul test imi da WA si la restul SIGSEGV.Va rog spuneti eventualele greseli.Sau dak s-ar putea un mic test... :-'
[EDIT]:Aveam o mica greseala in sursa,si de aia luam WA.Am corectat-o ,dar nu iau decat 60 p.Ce as mai putea sa optimizez?Citirea as putea sa o optimizez cumva?(citesc cu fscanf,deci pierd putin timp dak n=250000)


Titlul: Răspuns: 010 Stramosi
Scris de: Flaviu Pepelea din Octombrie 25, 2008, 10:45:04
baga o parsare....ar trebui sa mearga si foloseste in loc de pow operatii pe biti (1 << k inseamna 2 ^ k)


Titlul: Răspuns: 010 Stramosi
Scris de: Iacob Eduard din Octombrie 25, 2008, 10:56:00
In sfarsit... \:D/ Am luat 100
Ms mult Flaviu.Tot ce am facut e sa inlocuiesc pow cu <<. La chestia asta ma gandisem si eu,numai ca eu in loc sa fac 1<<k,faceam k<<index,si mai erau nevoie de inca niste variable,deci imi iesea din timp. :wink:


Titlul: Răspuns: 010 Stramosi
Scris de: Dragos din Aprilie 15, 2009, 19:59:35
nu intzeleg o chestie dc 2^k trb <=n  dak avem totzi stramoshtii (1->2->3->4->5->6) unde primul stramos e 2 iar al 5-ilea 6 iar 2^5>6


Titlul: Răspuns: 010 Stramosi
Scris de: Florian Marcu din Aprilie 15, 2009, 22:19:05
pai ai A[ k ] [ i ] - cel de-al 2^k-lea stramos a lui i. Daca 2^k > n, atunci cel de-al 2^k-lea stramos a lui i nu exista [ pt ca i are maxim n stramosi ]  :)


Titlul: Răspuns: 010 Stramosi
Scris de: Dragos-Alin Rotaru din Februarie 05, 2010, 14:49:18
Fac un df recursiv si am o complexitate de O (N + M). Cu toate acestea primesc KBS 11 pe ultimul test. Am modificat limitele pana la 400 000  si am ajuns sa folosesc 40MB din memorie dar degeaba. Daca ar putea sa ma ajute cineva i-as ramane recunoscator. Multumesc.
Aici e sursa : http://infoarena.ro/job_detail/391337?action=view-source (http://infoarena.ro/job_detail/391337?action=view-source).


Titlul: Răspuns: 010 Stramosi
Scris de: Paul-Dan Baltescu din Februarie 06, 2010, 07:24:18
Poate e din cauza recursivitatii. Incearca sa scrii DFS-ul iterativ.


Titlul: Răspuns: 010 Stramosi
Scris de: Dragos-Alin Rotaru din Februarie 06, 2010, 13:47:33
Am luat suta in sfarsit. Din cauza df-ului recursiv era KBS-ul ala. Multumesc inca o data . :)


Titlul: Răspuns: 010 Stramosi
Scris de: Mihai Jiplea din Februarie 12, 2010, 11:24:11
Obțin "Killed by signal 11(SIGSEGV)." oricât de mare mi-aș fi declarat vectorul, iar algoritmul respectă la fix ideea matricii A[log(n)][n].  :readthis:
E a noua oară când uploadez sursa cu modificări minore care am crezut eu că pot fi cauza iar răspunsul e tot același.. signal 11
http://infoarena.ro/job_detail/395149?action=view-source


Titlul: Răspuns: 010 Stramosi
Scris de: Andrei Ilisei din Aprilie 11, 2011, 11:44:37
a luat cineva 100p cu un program de complexitate n+m*p?
Pentru fiecare query caut stramosul cu ceva de genul x = tata [ x ]; (pentru asta am luat 80 p cu TLE pe ultimele 2)
Am incercat si sa imi 'preprocesez' al p-lea stramos pentru fiecare om si am luat memory limited exceeded pe ultimele 4 teste


Titlul: Răspuns: 010 Stramosi
Scris de: UAIC.VlasCatalin din Iulie 05, 2011, 10:08:41
Poate cineva sa-mi explice de ce la intrbarea 5 din exemplu raspunsul e 8 dar nu 10?


Titlul: Răspuns: 010 Stramosi
Scris de: George Marcus din Iulie 05, 2011, 11:46:31
Al 3-lea stramos al lui 13 este 8. Mergand in sus pe arbore primul e 12, al doilea e 10.


Titlul: Răspuns: 010 Stramosi
Scris de: Lucian Bicsi din Februarie 12, 2015, 21:59:09
Complexitatea oficiala este O(m+n)? Eu asa am facut-o, chiar fara multa bataie de cap(ca implementare)


Titlul: Răspuns: 010 Stramosi
Scris de: Mihai Calancea din Februarie 12, 2015, 22:29:41
Sunt 2 soluții, cea pe care o ai tu în O(n + m) și una în O(n log n + m log n) care are avantajul că poate răspunde online la query-uri, nu are nevoie să le știe pe toate de la început. Ambele idei și implementări sunt utile  :)


Titlul: Răspuns: 010 Stramosi
Scris de: Ciocoiu Vlad din Septembrie 01, 2019, 22:53:53
Ok am rezolvat problema cu stramosii de ordin 2^k ai fiecarui nod dar nu inteleg de ce ruleaza mai repede daca inversez indicii din matrice, imi poate explica cineva?