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

Karma: 6
Deconectat Deconectat

Mesaje: 235



Vezi Profilul WWW
« Răspunde #50 : 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  Rolling on the Floor Laughing numai idiotenii... intre timp mi-a iesit problema, si mi-a iesit din cap ideea cu o matrice de n*n
« Ultima modificare: Iulie 18, 2006, 15:10:22 de către Coty » Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #51 : 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" Smile 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 Smile
« Ultima modificare: Iulie 19, 2006, 19:21:50 de către svalentin » Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #52 : Iulie 19, 2006, 21:12:07 »

stiu ca ar putea parea stupid dar cum fac DF in o(n)  Very Happy 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.
Memorat
svalentin
Nu mai tace
*****

Karma: 88
Deconectat Deconectat

Mesaje: 704



Vezi Profilul
« Răspunde #53 : 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!
« Ultima modificare: Iulie 20, 2006, 18:48:47 de către svalentin » Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #54 : Iulie 20, 2006, 16:05:40 »

O(n + m) ...
Memorat
blasters
Vizitator
« Răspunde #55 : 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" Smile 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 Smile


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
Memorat
Alx
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 17



Vezi Profilul
« Răspunde #56 : Decembrie 15, 2006, 17:13:13 »

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

The important thing is not to stop questioning.
                                                     Albert Einstein
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #57 : 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
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #58 : 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).
Memorat

Am zis Mr. Green
Alx
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 17



Vezi Profilul
« Răspunde #59 : 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?
Memorat

The important thing is not to stop questioning.
                                                     Albert Einstein
blasterz
Nu mai tace
*****

Karma: 92
Deconectat Deconectat

Mesaje: 255



Vezi Profilul
« Răspunde #60 : 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 Neutral

PS stiam faza cu 2^n Wink)
« Ultima modificare: Decembrie 15, 2006, 21:27:45 de către Dima Mircea » Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #61 : 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.
Memorat
Programmer01
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 15



Vezi Profilul WWW
« Răspunde #62 : 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?
 
Memorat

Programmer01
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #63 : Februarie 10, 2007, 19:22:42 »

Runtime Error, daca nu ma insel Smile.
Memorat

Am zis Mr. Green
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #64 : 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... Confused ]
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #65 : 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]. Neutral
« Ultima modificare: Noiembrie 19, 2007, 21:57:25 de către Marcu Florian » Memorat
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #66 : 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.
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #67 : 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?  Confused
Memorat
DITzoneC
Nu mai tace
*****

Karma: 301
Deconectat Deconectat

Mesaje: 962



Vezi Profilul
« Răspunde #68 : 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.
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #69 : Noiembrie 21, 2007, 17:24:05 »

Da. Am inteles foarte bine. Multumesc de ajutor.  Smile
Memorat
marin
Strain


Karma: -1
Deconectat Deconectat

Mesaje: 22



Vezi Profilul
« Răspunde #70 : 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 ?
Memorat
marin
Strain


Karma: -1
Deconectat Deconectat

Mesaje: 22



Vezi Profilul
« Răspunde #71 : Februarie 17, 2008, 23:06:24 »

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

Karma: -104
Deconectat Deconectat

Mesaje: 161



Vezi Profilul
« Răspunde #72 : 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... Whistle
[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)
« Ultima modificare: Octombrie 25, 2008, 10:09:20 de către Iacob Eduard » Memorat
Pepelea_Flaviu
Client obisnuit
**

Karma: 30
Deconectat Deconectat

Mesaje: 98



Vezi Profilul
« Răspunde #73 : 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)
Memorat
k_ounu_eddy
Vorbaret
****

Karma: -104
Deconectat Deconectat

Mesaje: 161



Vezi Profilul
« Răspunde #74 : Octombrie 25, 2008, 10:56:00 »

In sfarsit... Dancing 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
Memorat
Pagini: 1 2 [3] 4   În sus
  Imprimă  
 
Schimbă forumul:  

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