•domino
|
|
« : Decembrie 12, 2005, 00:18:42 » |
|
Aici puteţi discuta despre problema Monezi.
|
|
|
Memorat
|
|
|
|
•vladcyb1
|
|
« Răspunde #1 : Ianuarie 02, 2006, 17:21:09 » |
|
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
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•filipb
|
|
« Răspunde #2 : Ianuarie 02, 2006, 22:27:46 » |
|
Eu am 100 pe O(2^N * S) - facut recursiv... Deci trebuie sa mearga fara probleme algoritmul tau daca intr-adevar are complexitatea aia...
|
|
|
Memorat
|
|
|
|
•vladcyb1
|
|
« Răspunde #3 : Ianuarie 03, 2006, 10:42:55 » |
|
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.
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•bogdan2412
|
|
« Răspunde #4 : Ianuarie 03, 2006, 10:56:49 » |
|
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.
|
|
|
Memorat
|
|
|
|
•filipb
|
|
« Răspunde #5 : Ianuarie 03, 2006, 11:05:16 » |
|
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!
|
|
|
Memorat
|
|
|
|
•gogu
Client obisnuit
Karma: 42
Deconectat
Mesaje: 98
|
|
« Răspunde #6 : Ianuarie 03, 2006, 11:52:33 » |
|
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. 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.
|
|
|
Memorat
|
|
|
|
•vladcyb1
|
|
« Răspunde #7 : Ianuarie 03, 2006, 18:55:56 » |
|
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 ?
|
|
|
Memorat
|
Vlad Berteanu
|
|
|
•filipb
|
|
« Răspunde #8 : Ianuarie 03, 2006, 20:21:59 » |
|
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...
|
|
|
Memorat
|
|
|
|
•tm_radu
|
|
« Răspunde #9 : Ianuarie 22, 2006, 20:57:35 » |
|
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?
|
|
|
Memorat
|
Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
|
|
|
cristi8
Vizitator
|
|
« Răspunde #10 : Ianuarie 22, 2006, 21:23:45 » |
|
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:
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.
|
|
|
Memorat
|
|
|
|
•pauldb
|
|
« Răspunde #11 : Martie 16, 2006, 20:11:06 » |
|
Ce faci tu aici nu e cumva in O(2^n*n*s)?
|
|
|
Memorat
|
Am zis
|
|
|
•cristy
|
|
« Răspunde #12 : Iunie 30, 2006, 13:12:08 » |
|
ce va da pentru 4 100 2 3 4 5
?
|
|
« Ultima modificare: Iunie 30, 2006, 13:17:13 de către cristy »
|
Memorat
|
... lipsa de inspiratie ...
|
|
|
•Marius
|
|
« Răspunde #13 : Iulie 01, 2006, 09:23:43 » |
|
ce va da pentru 4 100 2 3 4 5
?
1155
|
|
|
Memorat
|
Faceti lucrurile simplu: pe cat de simplu posibil, dar nu mai simplu.
|
|
|
•ciprianf
|
|
« Răspunde #14 : Iulie 18, 2008, 15:06:18 » |
|
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: 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
|
|
« Ultima modificare: Iulie 19, 2008, 16:26:09 de către Farcasanu Alexandru Ciprian »
|
Memorat
|
|
|
|
•freak93
|
|
« Răspunde #15 : Septembrie 03, 2009, 17:21:28 » |
|
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.
|
|
|
Memorat
|
|
|
|
•savim
|
|
« Răspunde #16 : Septembrie 03, 2009, 17:25:04 » |
|
Sunt bunte testele, am facut un program sa cicleze daca s > 512 si nu a prins nimic .
|
|
|
Memorat
|
|
|
|
•freak93
|
|
« Răspunde #17 : Septembrie 03, 2009, 17:26:13 » |
|
Ms, atunci o sa mai verific in program
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #18 : Septembrie 03, 2009, 18:44:28 » |
|
De multe ori mi s-a întâmplat ca bitsetul în două dimensiuni să crape inexplicabil. S-ar putea să fie de la asta.
|
|
|
Memorat
|
|
|
|
•deneo
|
|
« Răspunde #19 : Iunie 21, 2011, 21:10:32 » |
|
Rezolvarea O(N^2*N*S) e de 100? Ca atat am luat cu ea si mi se pare ciudat
|
|
|
Memorat
|
|
|
|
•repp4radu
|
|
« Răspunde #20 : Martie 22, 2012, 11:20:09 » |
|
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!
|
|
« Ultima modificare: Martie 22, 2012, 16:53:23 de către Szasz Radu »
|
Memorat
|
|
|
|
•lucian666
Client obisnuit
Karma: 16
Deconectat
Mesaje: 84
|
|
« Răspunde #21 : Februarie 07, 2013, 19:53:45 » |
|
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 .
|
|
|
Memorat
|
|
|
|
•RaduGabriel2012
Strain
Karma: 7
Deconectat
Mesaje: 26
|
|
« Răspunde #22 : Mai 03, 2013, 20:13:45 » |
|
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
|
|
|
Memorat
|
|
|
|
•tziplea_stefan
Strain
Karma: 0
Deconectat
Mesaje: 10
|
|
« Răspunde #23 : Martie 21, 2017, 21:09:22 » |
|
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.
|
|
|
Memorat
|
|
|
|
•andreiiii
|
|
« Răspunde #24 : Martie 22, 2017, 12:46:37 » |
|
Am marit limita la 0.6.
|
|
|
Memorat
|
|
|
|
|