495 Numere 6

[•DITzoneC]

Aici puteţi discuta despre problema Numere 6.

[•peanutz]

A luat cineva 100 cu varianta cu dinamica, adica O(a*nrdiv(b))? Vad ca intra solutia oficiala, varianta cu back. Daca la judet s-a luat 100 fara prea mari optimizari, cred ca ar trebui lasat si aici.

btw: e ok sa spunem si pe forum daca stim autorii?

[•pauldb]

Sigur, spune-i. Pe infoarena merg ambele variante de 100.

[•peanutz]

Am trimis sursa oficiala si nu merge. Nici a mea optimizata nu merge.

La asta e Ilie Vieru, si la cezar e Stelian Ciurea(la cezar sunt 99% sigur).

[•cos_min]

Am trimis sursa oficiala si nu merge. Nici a mea optimizata nu merge.

Mie mi'a mers dinamica in O( A*NrDiv(B) ) fara prea mari probleme. 

[•peanutz]

Da, asa e.. am precalculat o matrice unde gasesc pozitiile divizorilor si a intrat ok. Am impresia ca dura prea mult impartirea.

[•c_sebi]

ce as putea optimiza la solutia dinamica ca sa nu mai primesc TLE? multumesc.

[•pauldb]

Inlocuieste % cu scadere.

[•Tabara]

Iau 90 de puncte cu 1 TLE

Am optimizat tot ce am putut optimiza. Dinamica are complexitatea de O(A*nrdiv(B)*KONSTANTA )
unde KONSTANTA <= 9(defapt e numarul de divizori a lu B mai mici ca 9). Am pus scaderi in loc de modulo si tot nu merge. Iau TLE pe testul 9.

Ce optimizari as putea sa mai fac ?

Am trimis ca test si solutia oficiala si ia TLE pe acelasi test 9.
Am citit mai sus ce a scris peanutz dar nu prea am inteles.

[LATER EDIT] A mers pana la urma de 100.Trebuia sa scap cumva de operatia aia de impartire care manca mult timp.   ( Thanks Cosi )
 

[•ghitza_2000]

eu am trimis o formula si am luat 10 pct pe testul 9:D:D:D
write(g,((a*ct mod 9973)*ct1)mod 9973); unde ct= nr de div al lui b si ct1 = nr de div al lui b <10
*ct = nr de div al lui b-1:D,

[editat de moderator] Nu posta de doua ori consecutiv, de asemenea incearca ca postul sa aibe un sens.

[•stocarul]

Ma scoate din pepeni problema asta....
Cred ca ar trebui marit timpul....

Ce se poate mai performant decat ce am facut eu in codul:...
Adica am precalculat impartirile....in o(nr_div(b)*nr_div_mai_mic_10(b))
iar modulo il fac o data la 1000 de iteratii.....
Totusi primesc TLE pe testu 9....
Cred ca este prea aiurea ca la o problema sa se impuna un timp atat de mic....astfel icnat sa conteze stiu eu ce naiba ar putea conta....

Cod:

//salvam divizorii lui b
for(i=1;i<=k;i++)
	if(!(k%i)) //am asit un divizor al lui k
		d[++nr]=i; //salvam divizorul :P

//prelucram matricea c[][]...
for(i=1;i<=nr;i++)
	for(j=1;j<=nr&&d[j]<=9;j++)
		c[i][j]=d[i]/d[j];

//initializam pt a=1
for(i=1;i<=nr&&d[i]<=9;i++)
	m[1][d[i]]=1; //pt a=1, exista o singura posibilitate pt divizorii lui b mai mici ca 10

for(i=2;i<=n;i++) //calculam pentru fiecare a in parte
	{
	for(j=1;j<=nr;j++) //luam pe rand toate produsele care sunt divizibile cu k
		{
		m[i%2][d[j]]=0; //golim...am ajuns pt prima data pt i-ul asta :P
		for(p=1;p<=nr&&d[p]<=9;p++)
			if(!(d[j]%d[p])) // al j-lea divizor al lui k, este multiplu al celui de-al p-lea divizor
				m[i%2][d[j]]=m[i%2][d[j]]+m[(i-1)%2][c[j][p]]; //la psoibilitatiile gasite pana acum, se adauga si posibilitatile pt al p-lea divizor
		}
	if(i%1000) //din 1000 in 1000...facem modulo :P....ca sa economism timp :))
		for(j=1;j<=nr;j++)
			m[i%2][d[j]]%=modulo;
	}

//afisem numarul e posibilitati
printf("%d",m[n%2][k]%modulo);

[•Florian]

Incearca sa faci modulo prin scaderi repetate ( fara sa folosesti "%"), ca e mai rapid.

[•stocarul]

Incearca sa faci modulo prin scaderi repetate ( fara sa folosesti "%"), ca e mai rapid.

Am trimis si fara sa fac modulo deloc.....(desigur...la multe teste primesc WA)...dar la testul 9 tot nu intra in timp..

[•gabitzish1]

Incearca sa faci modulo prin scaderi repetate ( fara sa folosesti "%"), ca e mai rapid.

Asta merge mai rapid decat scaderile repetate:

Cod:

cat = X / MOD;
rez = X - MOD * cat;

[•stocarul]

Si eu ce fac?...
Am trimis sursa si fara modulo deloc...tot nu intra in timp....
La mine e posibil sa fie din cauza ca folosesc o matrice cu 2 linii....in loc sa folosesc 2 vectori (cred k am ales varianta mai frumoasa)
Insa nu cred ca din cauza asta trebuie sa am problema asta "pe rosu"......
Dupa parerea mea nu aici se face diferentierea dintre 2 surse.......
Inca o data zic....cred ca ar trebui marit timpul pt aceasta problema...

[•devilkind]

Poti rezolva problema in O(B * log A) si intra in timp fara probleme, deci dupa parerea mea limita de timp e buna.

[•zbarni]

Am facut retinand impartirile, scazand sau folosind expresia spusa de gabitzish, am pus short peste tot si tot imi iese din timp ... nu pot sa-mi dau seama ce poate fi, desi algoritmul e cam acelasi cu cel oficial. Un alt hint ar fi bineveit Btw, daca tot sunt testele de la judetene, cred ca ar fi fost fair sa intre macar algoritmul oficial

[•gh09]

Nu prea are precizie evaluatorul cand spune cata memorie am folosit......am un vector de 9000 si inca unu de 100 de elemente...teoretic ar fi ~40 de kb si mie imi arata ca am folosit 200...cam mare diferenta nu?

[•philip]

Dati-mi va rog niste teste, si raspunsul la ele, sa imi dau seama unde am gresit  .
Pe testele exemplu, pe testele create de mine, si pe 6 din 10 de la evaluare merge bine.
http://infoarena.ro/job_detail/280166

[•gabor_oliviu1991]

iti poti scoate testele oficiale de la OJI http://infoarena.ro/downloads?action=download&file=oji2007.zip&safe_only=false

[•philip]

Mersi 

L.E. Am facut o mica modificare (round in loc de trunc), dar la testul 7 primesc tot WA, desi pe testul oficial imi da raspunsul corect.
Pe infoarena sunt aceleasi teste?

Inca ceva... daca poate sa verifice cineva care a luat 100 de puncte, ce rezultat ii da pt a=8000, b=8192.

[•Pepelea_Flaviu]

Mie imi da 8929!

[•APOCALYPTO]

Imi poate oferi si mie cineva o problema asemanatoare cu explictia rationamentului in urma caruia gasim relatia de recurenta?

Multumesc anticipat!

[•Florian]

tablite , daca imi amintesc bine.

[•APOCALYPTO]

Ce s-a intamplat cu evaluatorul?
Am trimis o sursa pentru 60% din punctaj si iau numai WA desi la mine pe calculator imi dau toate testele corect(pentru a=1000, b=1000 raspunsul este 1293 nu?).  
http://infoarena.ro/job_detail/405365
Acasa utilizez codeblocks.
Mentionez ca pentru sursa de 60% am folosit sursa asta: http://infoarena.ro/job_detail/405317 pe care am folosit o matrice intraga in loc de 2 linii si imi depasea memoria. Cu toate astea am luat 20 de puncte la ultima sursa mentionata.
Multumesc anticipat pentru eventualele clarificari!

@Marcu Florian Mersi
Later edit: Am incercat pe testele de la OJI 2007 si pe toate testele in mici(cele 6) imi da raspunsul corect iar pe infoarena inca iau 0.
Later later edit: Bill Gates e de vina!