Ultimele mesaje ale lui: Adrian Budau

Afişează mesaje
Pagini: 1 ... 22 23 [24] 25 26

576	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / 1199 Ciob	: August 26, 2011, 20:42:04
Aici puteti discuta despre problema Ciob. Multumim Mihai-Alexandru Dusmanu. pentru adaugarea ei.

577	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / 1175 S013	: August 26, 2011, 20:39:19
Aici puteti discuta despre problema S013. Multumim Mihai-Alexandru Dusmanu. pentru adaugarea ei.

578	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / 1174 Icrisop	: August 26, 2011, 20:37:00
Aici puteti discuta despre problema Icrisop. Multumim Ionut Bogdanescu. pentru adaugarea ei.

579	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / 1173 Color 4	: August 26, 2011, 20:32:34
Aici puteti discuta despre problema Color 4. Multumim Ionut Bogdanescu. pentru adaugarea ei.

580	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 958 Dinti	: August 25, 2011, 16:22:59
Rezolvat.

581	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 018 Siruri 2-3-monotone	: August 09, 2011, 18:12:22
O idee pe care am oferit-o o data ar fi o dinamicain 3 dimensiuni d[ i ][j][k] pentru siruri de lungime i cu valori intre 1 si j si cu ultimele elemente avand o ordine k. Iti las tie problema gasirii numarului de elemente pe care trebuie sa le considiri si recurenta dinamicii. Rezolvarea asta ar fi cam O(N^2) cu o constanta maricica dar accectabila.

582	infoarena - concursuri, probleme, evaluator, articole / Concursuri / Răspuns: IOI 2011	: Iulie 25, 2011, 11:47:03
Nici mie nu mi s-a parut ok cum au fost anul acesta subtask-urile. Numarul de punctaje diferite ce se pot obtine e cam 45. Problema usoara fiind rezolvata cam de toti se reduce la cam 20. E greu sa se faca trecerea dintre medalii asa. Anul trecut a fost ok deoarece ultimul subtask deobicei avea un punctaj partial.

583	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 1886 Module	: Iunie 25, 2011, 20:22:01
Asa a fost si in timpul probei onsite. Oricare ar fi 3 noduri x, y, z astfel incat x si y sunt in S si z nu apartine lui S A(x, z) = A(y, z). Nu vad care ar fi greseala

584

infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 903 Hartie

: Iunie 18, 2011, 21:47:19

Cod:

585	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 839 Palindrom2	: Iunie 12, 2011, 19:50:51
Acum aceeasi sursa ia Killed by Signal 11 pe toate testele. Nu cred ca e gresita avand in vedere ca initial lua 100 de puncte. L.E: Greseam limitele. Iau 100 acum deci si-a revenit @Tiberiu Eu credeam ca memoria unui program pe infoarena e marimea afisata + marimea executabilului (asa mi s-ar parea normal sa intri in cei 640 de kilobytes) altfel ar fi un pic cam dificil, sau imposibil in cei 64 de kilobytes cum a fost la aceasta problema.

586	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 839 Palindrom2	: Iunie 11, 2011, 10:34:17
E o problema de evaluator. Sursa mea care initial lua 100 de puncte acum ia Memory limit exceeded pe toate testele. Poate acum se aduna marimea executabilului la memorie (la mine are aproximativ ~600 kilo bytes). Cineva din admini ar trebui sa se uite peste eval. Tu nu te mai stresa cu ea deocamdata ca nu ai ce face

587	infoarena - concursuri, probleme, evaluator, articole / Algoritmiada 2011 / Răspuns: Derdelus	: Februarie 20, 2011, 15:09:36
Daca unul din cuburile bazei este stricat se considera ca poate ajunge in 0 moduri in el?

588	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 1097 Difprim	: Decembrie 22, 2010, 12:30:39
Bool nu prea e folositor ca tip de date, consuma 1 byte pentru a mentine 2 valori(true and false). Desi in conditiile de fata intra in memorie la unele probleme s-ar putea sa nu intre.

589	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 546 Polig	: Decembrie 17, 2010, 08:26:35
Am sa-ti dau un hint pentru solutia N ^ 2 log N, ar fi cam aiurea sa postez rezolvarea. Se pastreaza dinamica initiala. Trebuie sa observi ca daca notezi cu A multimea k-urilor din care poate provine dinamica[ i ][ j ] si cu B multimea k-urilor din care poate provine dinamica[ i ][ j' ] atunci A este inclus in B sau invers.

590	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 1090 Rk	: Decembrie 14, 2010, 20:46:39
In concurs am bagat radix sort(pentru fiecare bit) si dupa fiecare pas al soratarii o parcurgere cu 2 indici, ca sa determin raspunsul pentru fiecare query. Sper sa-i foloseasca cuiva

591	infoarena - concursuri, probleme, evaluator, articole / FMI No Stress 2010 / Răspuns: Nc	: Decembrie 12, 2010, 11:54:11
Daca ultimul rand din fisierul de intrare nu se termina in vreun semn de punctuatie se mai considera fraza? Ex: Cod: Aceasta este o propozitie, bla bla

592	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 1015 Xp	: Noiembrie 27, 2010, 22:59:52
Nu stiu daca chiar vrei sa afli solutia cu invers modulari. Asta e cea care am implementat-o in timpul olimpiadei si am luat 80 nu 100. Cred totusi ca se poate obtine si 100 daca e optimizata asa ca hai sa-ti explic: Descompui numarul Q in factori primi Q=p1^q1 * p2^q2 * ..... pk^qk Orice numar val[ i ] din sir poate fi impartit in xval[ i ] si yval[ i ] astfel incat xval[ i ] yval[ i ] = val[ i ] si xval[ i ] are factori primi numai din multimea {p1,p2,....,pk} si yval[ i ] factori primi care nu apartin aceastei multimi. Daca notam cu P produsul val[1] * val[2] * .... * val[n], cu xP produsul xval[1] * xval[2] * ... * xval[n] si tot la fel yP din yval[1] s.a.m.d, atunci P = xP * yP Pentru a putea calcula prod[ i ] se observa ca in loc sa calculam P/val[ i ] putem calcula (xP/xval[ i ]) * (yP/yval[ i ]) (modulo Q). yp si yval[ i ] necontinand factori primi comuni cu Q sunt prime cu Q si deci putem aplica invers modular pe ele. Calculam inversul modular a lui yval[ i ] si il inmultim cu yP. Asa obtinem o parte din prod[ i ]. Pentru a obtine a xP/xval[ i ] putem putem face o precalculare. Observam ca k (numarul de factori primi din descompunerae lui Q) e relativ mic <=20. Aflam pentru fiecare valoare la ce putere se afla in xP(sa o notam cu zk). Asta se face la prima parcurgere a sirului cand se calculeaza si yP. Observam ca p1^z1 * p2^z2 * ... * pk^zk = xP Dupa ce aflam aceste valori se poate calcula o matrice calc in care calc[ i ][ j ] reprezinta pi^(zi-j). j<=30 (evident modulo Q). Avand aceste valori calculate putem afla pentru orice xval[ i ] cat face xP/xval[ i ]. Il descompunem pe xval[ i ]= p1 ^ q1' * p2 ^q2' * ... * pk^qk'. Atunci xP/xval[ i ] va fi egal cu produsul elementelor calc[ i ][ qi' ] pentru i de la 1 la k. Asa se formeaza solutia: 1) La prima parcurgere se descompune fiecare val in xval si yval si se calculeaza zi (pentru i de la k) si yP; 2) Se calculeaza matricea calc. (asta se face usor prin exponentiere rapida pana la zi-30( pentru i de la 1 la k) si inmultind cu pi pana se ajunge la zi cu exponentul. 2) La a doua parcurgere se descompun iar numerele val in xval si yval(pentru ca evident ele nu se pot mentine in memorie). Se calculeaza xP/xval[ i ] dupa procedeul descris mai sus si yP/yval[ i ] folosind invers modulare. Se inmultesc cele 2 astfel obtinandu-se prod[ i ] care se XOR-eaza cu raspunsul . Later Edit: Complexitatea Worst Case este O(n*log₂(val_max) ) unde val_max in situatia de fata este 1.000.000.000. Pe cazul mediu se comporta mult mai bine, un O(n) cu constanta 8 din cate cred, voi incerca sa calculez si sa pun aici.

593	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 257 Catun	: Noiembrie 11, 2010, 15:02:22
O sa tin minte. Mie sincer imi intra in cap Bellman-ford la BF si Breadth-first-search la BFS. Ma voi adapta

594	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 257 Catun	: Noiembrie 11, 2010, 02:45:14
Nu inteleg exact la ce te referi cand spui real-time, dar daca vrei o solutie in O(n) dupa BF, pur si simplu la BF mai tii o valoare pentru fiecare nod, anume foratareata de care apartine, la care evident ca poti da update in O(1) cand treci prin acel element in BF. In rest e buna ideea. Sper sa te ajute

595	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 1054 Fibo2	: August 26, 2010, 12:24:36
Cu exponentiere rapida de matrici.

596	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 866 Bile5	: August 06, 2010, 16:06:03
"Datorită aşezării, din urna i pot extrage bile doar prietenii i şi ((i+1) mod N).". Liderul neluand nicio bila din urna 0 si luand 3 din gramada 3 ia preietenul 1(nu prietenul 3) restul din gramada s.a.m.d pana s eiau toate 13. Deci enuntul este corect

597	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 951 Vrejuri	: August 05, 2010, 22:54:25
Da. E bun articolul, tu nu cauti marimea taieturii maxime, ci marimea copacului care are taietura maxima(asta e logic daca te gandesti ca pe masura ce creste inaltimea finala a copacului creste si marimea taieturii mai marr din cele 2 tipuri de taieturi care se fac). Cred ca la asta te refereai

598	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 067 Triang	: Iulie 26, 2010, 17:01:28
Prima metoda ar fi sa calculezi mediatoarea(x si y al dreptei).A doua si dupa pararea mea mai simpla de inteles este cea folosind numere complexe(asta daca ai cunostinte despre ele): Ai acolo o teorema: Un triunghi e echilateral daca numerele complexe cu afixele A,B,C(ABC fiind triunghiul in ordine trigonometrica) satisfac urmatoarea relatie: a+epsb+epsepsc=0 unde eps=cos 60+isin60; Stiind a si b, c poate fi: 1) -aeps-bepseps sau 2) -beps-aeps*eps(considerand triunghiul in ordine invers trigonometrica). Sper sa te ajute

599	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 1067 Trenuri2	: Iunie 21, 2010, 10:40:26
Testele la aceasta problema sunt aceleasi, ca m-am testat cu cele oficiale si imi da corect? La testul 4 am 3 valori care difera cu 0,001, si la testele 6 si 8 cate o valoare care difera cu 0,001 in rest totul la fel. L.E:Am trimis sursa modificand afisarea, initial afisam doar 3 zecimale, acum le afisez pe toate si iau 100. Cred ca evaluatorul care calculeaza diferenta nu e destul de exact.

600	infoarena - concursuri, probleme, evaluator, articole / Arhiva de probleme / Răspuns: 1047 Minge	: Mai 13, 2010, 12:17:04
Pentru cazul cand e par afisezi cumva n/2-1? Incearca si vezi cat iti da pentru 6 si 14 daca faci asta si o sa vezi cum sa iei 100.

Pagini: 1 ... 22 23 [24] 25 26

infoarena informatica de performanta