007 Datorii

[•crawler]

poate iti intra in ciclu infinit 

[•Darth_Niculus]

 M-am gandit la chestia cu ciclu infinit... nu prea vad cum s-ar intampla asta.... pare corect totu'.... in fine gasesc eu ce are 

       --------

 Mdea nush ce avea .... am implementat din nou si acuma merge... wierd

[•dobre]

  Am incercat sa rezolv problema cu Arbori de intervale si iau TLE la toate. Am incercat sa optimizez cat am putut, fac siftari in loc de div dar tot aceeasi chestie. Vad ca altii au reusit cu AI deci ar trebui sa mearga si la mine. Am atasat un link pentru sursa mea http://infoarena.ro/job_detail/152903?action=view-source

[•EdeN]

Problema este foarte usoara daca se studiaza http://infoarena.ro/aib si se rezolva http://infoarena.ro/problema/aib.

Sper ca ajuta pe cineva ce am scris mai sus.

[•Pepelea_Flaviu]

Si cu arbori de intervale e la fel de usor ....

[•cosmin79]

Poate cineva va rog sa se uite pe sursa mea?
http://infoarena.ro/job_detail/330398 Am citit articolul despre AIB si am facut exact ce spunea acolo.Exemplul merge,dar iau incorect pe toate testele
Mersi anticipat! 

[•c_e_manu]

Mai da-ti teste, nu te folosi doar de exemplu. In plus, la problema asta te poti uita pe sursele celorlalti ca sa-ti gasesti greseala!

[•cosmin79]

Ma lamureste si pe mine cineva dc astea 2 fragmente de cod pentru aflarea pozitiei celui mai nesemnificativ bit de 1 nu sunt echilvalente:
1)

Cod:

		while (x%2==0)
		{
			poz++;
			x/=2;
		}

2)

Cod:

while(!(x&(1<<poz))) 
	 poz++; 

Mersi anticipat!

[editat] foloseste tag-ul "code" cand postezi cod pe forum

[•MciprianM]

Verifica daca ai initializat poz cu 0; De ce tip e x?
Daca x e long long si cel mai nesemnificativ bit e pe o pozitie poz mai mare decat 30 (si daca, cred, poz e int ) atunci 1<<poz va fi diferit de numarul pe care il cauti, pentru ca 1<<poz va fi de tip int.

[•cosmin79]

poz l-am initializat cu 0 si e de tip int.
Problema nu e ce se intampla mai incolo cu 1<<poz (desi oricum poz nu ajunge sa depaseasca 30 niciodata din cauza restrictiilor : x<=15000).Ce nu inteleg e de ce merge prima varianta de aflare a lui poz,in timp ce a 2-a merge.

[•deiosx]

am incercat sa fac problema cu liste si abia acum am incercat cu arbori si...
Ma rog abia acum merge

[•pauldb]

Nu mai posta daca nu ai nimic de spus.

[•stefan92]

imi poate explica cineva ce face "x += (x&(x-1))^x;" 

[•PlayLikeNeverB4]

omg diferenta dintre 40p si 100p au facut-o 4-5 linii de comentarii <=> 30-40 ms

[•Sadmann]

Eu cred ca teste sunt un pic prea "extreme", deoarece cu exact acelasi cod, odata am luat 40 pct, odata 80 si odata 100...

[•eudanip]

Probabil limita de timp e foarte stransa pentru a fi implementate AIB-urile in loc de Arbori de intervale.

[•ion_caliman]

am folosit arbori indexati binar dar imi iese din timp la toate testele, care poate fi problema?

[•pauldb]

Am impresia ca in Pascal parametrii vectori se transmit prin valoare, deci la fiecare apel al functiei suma tu ai complexitate O(N) deoarece se copiaza intreg vectorul. Nu sunt sigur ca e asa, dar ai putea sa incerci si sa vezi daca te scapa de TLE.

[•ion_caliman]

ai avut dreptate, am luat 60p, dar la 2 teste la fel arata TLE

[edit]
de fiecare data sunt teste diferite? luam 60p acum iau 0, dar nu am facut modificari

Editeaza-ti mesajele anterioare, nu posta consecutiv.

[•pauldb]

Sunt mereu aceleasi teste, dar probabil ca programul tau ruleaza aproape de limita de timp si obtii punctaje diferite. Un alt motiv pentru care iei TLE-uri este ca folosesti Pascal, care e mai incet. In rest, ai putea optimiza operatiile pe care le faci deja sau sa parsezi citirea.

[•ion_caliman]

problema este ca nu stiu ce e parsare...

[•gabitzish1]

Uite un feature frumos al forumului : Cauta in forum.
Foloseste-te putin de el sa vezi daca s-a mai discutat despre parsare. Nu are rost sa umplem toate topicurile cu aceleasi subiecte.
 

[•ion_caliman]

Multumesc! teoretic am inteles ce inseamna parsarea, dar practic nu am inteles cum o folosesti, daca ma poti ajuta cu ceva, cum se face, pas cu pas, ti-as fi recunoscator!

[•gabitzish1]

http://infoarena.ro/forum/index.php?topic=4549.0 acolo ai model de implementare atat pt numere pozitive cat si pt numere negative (poate o sa ai nevoie de ele mai incolo).
Ideea e ca vrei sa reduci timpul folosit pentru citirea datelor. Atunci, ca sa nu citesti foarte multe numere, pe rand, din fisier, citesti bucati din fisier si le retii ca si string'uri (poti citi cate o linie, sau cum o sa vezi in link'ul postat mai sus - bucati de X caractere) si iti formezi tu manual numerele de care ai nevoie prelucrand stringurile respective. A zis cineva ca asa merge mai repede decat citirea normala 
Mai "pas cu pas" cum sa'ti zic? - inlocuieste bucata de cod unde citesti tu datele, cu ce am explicat mai sus.

[•ion_caliman]

 cu parsare la fel primesc TLE, cred ca autorii au uitat ca unii lucreaza in Pascal si au pus limita de timp prea mica