150 Monezi

[•domino]

Aici puteţi discuta despre problema Monezi.

[•vladcyb1]

Ce complexitate ati reusit sa scoateti pentru 100 ? Eu am ceva 2^N*(S+N)...si iau 60...iar daca fac 2^N*S*N iau tot 60  

[•filipb]

Eu am 100 pe O(2^N * S) - facut recursiv... Deci trebuie sa mearga fara probleme algoritmul tau daca intr-adevar are complexitatea aia...

[•vladcyb1]

Hai sa ti povestesc un pic cum fac....

 Iau fiecare submuiltime 1..2^n-1 scot din ea un bit de 1 care reprezinta un numar din cele N si obtin o alta submultime pe care am calculat-o anterior. Numarul pe care l-am scos il combin cu rezultatele de la  submultimea obtinuta si memorez.

  Submultimile 1..2^n-1 le-am memorat pe biti si ocupa 9 MB.

   

[•bogdan2412]

E buna rezolvarea ta.
Din cate am vazut eu tu faci in Pascal si s-ar putea ca asta sa fie cauza. Compilatorul C optimizeaza foarte mult programul pentru problema asta daca folosesti optiunea O2. Cand a fost data la concurs problema asta s-a scos aceasta optiune de compilare ca sa fie sanse egale pentru cei din Pascal si C. Acolo, e drept pe calculatoare mai slabe, de la un program care merge in 2.5 secunde fara optiunea O2 se ajungea la unul care merge in 1 secunda cu optiunea respectiva. Acum pe Infoarena nu prea pot sa faca acest lucru doar pentru o singura problema... Ori incerci sa optimizezi serios programul tau (nu sunt sigur ca o sa mearga), ori treci pe C, ori o lasi balta ....
Good luck.

[•filipb]

Submultimile 1..2^n-1 le-am memorat pe biti si ocupa 9 MB.

S-ar putea de aici sa ti se traga. Algoritmul tau e la fel ca al meu mai putin aici... Incearca sa faci un back recursiv in care sa construiesti sirul de 0 si 1, si uita-te ca pe nivelul curent diferi doar cu un bit de cel anterior ( ultimul bit )-deci nu mai e nevoie sa retii tot sirul de 2^n biti. Eu am mai putin de 20K memorie. SPOR!

[•gogu]

Un compilator bun nu poate inlocui cateva optimizari facute de mana. Si pascalul poate fi foarte rapid, doar ca compilatorul de pe infoarena se comporta un pic cam ciudat.
Uite borderoul meu de pascal, facut cu un back de sub 20 de linii.

Cod:

TEST 1	...[0.27s]...	OK!
TEST 2	...[0.29s]...	OK!
TEST 3	...[0.27s]...	OK!
TEST 4	...[0.28s]...	OK!
TEST 5	...[0.01s]...	OK!
TEST 6	...[0.01s]...	OK!
TEST 7	...[0.01s]...	OK!
TEST 8	...[0.01s]...	OK!
TEST 9	...[0.01s]...	OK!
TEST 10	...[0.01s]...	OK!

Am cam trebuit sa optimizez un pic, dar mi se pare normal. In primul rand, cel mai bine e cand variabilele sunt mici si poti sa profiti in plin de cache.

[•vladcyb1]

 Mai..eu nu prea inteleg cum faceti voi backul.....
      Pentru fiecare nivel memorati vectorul cu sume si pe urma cand inaintati pe urmatorul nivel combinati numarul corespunzator nivelului cu sumele obtinute pe nivelul anterior ?

   Nu cred ca e asa....pt ca ar veni 2^N*N*S.....nu ?

 

[•filipb]

Exact asa facem, dar nu uita ca nu se ia de la inceput toata chestia, deci complexitatea pe un nivel din back e O(S), nu O(N*S). Daca ai retinut in A - daca suma i se poate obtine, atunci tot ce ai de facut pt. un nou nivel este sa copii vectorul de pe nivelul anterior si pt. fiecare suma i pt. care ai A sa setezi si A[i+VALOARE_MONEDA_CURENTA] cu 1 sau True...

[•tm_radu]

Eu am facut altfel....sa-mi zceti daca-i buna metoda.
Am folosit metoda programarii dinamice, adica x = numarul de moduri in care se poate obtine suma i;
am facut un sir a care tine sumele tuturor subseturilor, si asa incrementez x[j+a], daca am putut obtine suma j inainte. raspunsu este a[1] + a[2] + .... + a[numarul tuturor subseturilor];
ce nu-i bine?

[cristi8]

ce va complicati...
eu am avut doar un vector a = in cate moduri se obtine suma i.
si am facut un back recursiv in care nu retineam nici stiva, nimic pe biti.. doar faceam ceva de genu:

Cod:

  
  val = v[lev];
  for(i = val; i <= s; i++)
    a[i] += a[i-val];
  back(); // moneda lev era in subset
  for(i = s; i >= val; i--)
    a[i] -= a[i-val];
  back(); // moneda lev nu era in subset

si cand nivelul atingea nivelul maxim, adunam la solutia finala numarul i-urilor pentru care a era nenul.

[•pauldb]

Ce faci tu aici nu e cumva in O(2^n*n*s)?

[•cristy]

ce va da pentru
 
4 100
2
3
4
5

?

[•Marius]

ce va da pentru
 
4 100
2
3
4
5

?

1155

[•ciprianf]

Of, nu reusesc sa iau mai mult de 40 de pcte, iau 6 WA-uri, desi nu inteleg unde am gresit. Am complexitatea O(2^N*S) si am facut asa backul recursiv:

Cod:

void back(int k,int w[]){
	for(int i=s[k-1]+1;i<=n;i++){
		s[k]=i;
		int t[S]={1,0};
		for(int j=0;j<=sum-v[i];j++)
			if(w[j]){
				t[j+v[i]]=1;
				sol++;
				if(j && !t[j]) sol++;
				t[j]=1;
			}
			else if(t[j]){
				t[j+v[i]]=1;
				sol++;
			}
		back(k+1,t);
	}
}

Limitele le-am verificat si sunt ok.Imi poate spune cineva unde am gresit? sau poate sa imi dea niste teste ? Ms anticipat


LE:Chiar nu stie nimeni?
LLE: Am rezolvat-o pana la urma

[•freak93]

Cred ca in unele teste s>512 , aveam un vector bitset A[1<<18][530] si nu-mi mergea(luam SIGSEGV la 2 teste - in total luam 20 de puncte), am pus 1200 in loc de 530 si nu mai primesc eraore desi primesc 60 de puncte.

[•savim]

Sunt bunte testele, am facut un program sa cicleze daca s > 512 si nu a prins nimic  .

[•freak93]

Ms, atunci o sa mai verific in program

[•Mishu91]

De multe ori mi s-a întâmplat ca bitsetul în două dimensiuni să crape inexplicabil. S-ar putea să fie de la asta.

[•deneo]

Rezolvarea O(N^2*N*S) e de 100? Ca atat am luat cu ea si mi se pare ciudat

[•repp4radu]

Imi puteti da un test mai mic? Programul imi merge (pe testele care mi le-am dau eu), dar iau 0 puncte cu incorect.

Mersi anticipat!

LE Am rezolvat!

[•lucian666]

Salut . Ar trebui marita limita de timp . Am o solutie  2^N * ( S+N ) iterativa  si obtin doar 60 pct . Submultimile  le construiesc cu ajutorul operatiilor pe biti  .

[•RaduGabriel2012]

Eu am facut O( 2^n *  S) , consider fiecare submultime ca submultimea anterioara + ultimul element si am optimizat memoria ca la ciurul lui Erathostene . Iau 70p cu TLE pe testele 2,3,4 http://www.infoarena.ro/job_detail/946131 
 

[•tziplea_stefan]

Probabil ar trebui marita putin limita de timp, am o solutie de complexitate O(2^N*S) si am incercat sa o optimizez cat am putut, in schimb, nu am reusit sa trec de 70 puncte. 

[•andreiiii]

Am marit limita la 0.6.