010 Stramosi

[•Coty]

(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  numai idiotenii... intre timp mi-a iesit problema, si mi-a iesit din cap ideea cu o matrice de n*n

[•svalentin]

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

[•devilkind]

stiu ca ar putea parea stupid dar cum fac DF in o(n)  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.

[•svalentin]

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!

[•Cosmin]

O(n + m) ...

[blasters]

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

[•Alx]

E testul 10 mai special? Ca la el am luat TLE, WA si SIGSEGV (cu surse diferite desigur).

[•blasterz]

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

[•pauldb]

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

[•Alx]

Tot nu merge. Ma gandeam... P poate sa fie 0? Si daca da, in acest caz se afiseaza Q, nu?

[•blasterz]

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 )

[•devilkind]

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.

[•Programmer01]

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?
 

[•pauldb]

Runtime Error, daca nu ma insel .

[•sima_cotizo]

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

[•Florian]

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

[•DITzoneC]

Trebuie sa ai ceva de genu b[ k ][ i ] = b[ k-1 ][ b[ k-1 ][ i ] ]. Iei al 2^k-1-lea parinte al celui de al 2^k-1-lea parinte al lui i adica al 2^k-lea parinte al lui i.

[•Florian]

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? 

[•DITzoneC]

Pai ideea e sa faci log(n) query-ul. Gasesti k maxim astfel incat 2^k<=p. Apoi mai trebuie sa afli al p-2^k-lea stamos al lui b[k][q] lucru care il faci recursiv ( gasesti iar k' maxim astfel incat 2^k'<= p-2^k... si tot asa) pana cand ajungi cu p=0 caz pentru care raspunsul este nodul insusi.

Sper ca se intelege din ce am explicat.

[•Florian]

Da. Am inteles foarte bine. Multumesc de ajutor. 

[•marin]

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 ?

[•marin]

Da, mi-am dat seama, vectorul cu intrebari il puneam tot de 250000 ...

[•k_ounu_eddy]

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)

[•Pepelea_Flaviu]

baga o parsare....ar trebui sa mearga si foloseste in loc de pow operatii pe biti (1 << k inseamna 2 ^ k)

[•k_ounu_eddy]

In sfarsit... 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.