010 Stramosi

[•Coty]

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

[•bogdan2412]

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

[•svalentin]

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

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

[•Coty]

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]

[•svalentin]

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

[•svalentin]

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

[•Coty]

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

[•svalentin]

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

ultimu tau post e o parcurgere in adancime... sau ce?

"Post subject: sortare topologica"

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

adica am scris atata degeaba?!
... 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!  

[•Coty]

nu citisem subiectu ...

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...
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!

[•svalentin]

nu citisem subiectu ...

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!

[u-92]

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  

[cristi8]

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 ?".

[•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

[•svalentin]

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

[ditzone]

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 )

[•Coty]

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

[u-92]

cauta si despre metode de reprezentare a grafurilor.. se poate n+m, unde m e numarul de muchii

[•Coty]

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?

[u-92]

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.

[•Coty]

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

[•svalentin]

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

[•Crusher]

Imi mai puteti da un exemplu sa-mi dau seama unde gresesc?
preaty please whith sugar on top!!

[•filipb]

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:

[•cristy]

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?...

[•wefgef]

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