infoarena

 Asteptam parerile si criticile voastre !  :D

Pana la urma ramane la voi vinul si berea :D. Sau mai ramane valabila oferta dupa ce se pun problemele in arhiva? :P. Cred ca cei mai multi au luat probleme in ordine, crezand ca sunt ordonate dupa dificultate, ca la concursurile anterioare de pe infoarena. Oricum, concursul a fost foarte bine organizat, problemele interesante, eu am numai cuvinte de lauda... cine stie, poate mai faceti unul peste vreo luna-doua. Felicitari oricum pentru munca depusa !

Felicitari  =D> , pentru numarul de participanti si desfasurarea fara probleme.  Poate data viitoare bagati si o problema simpluta asa ca sa fie mai multe punctaje peste 100 ;).

Probleme poly si bridge trebuia sa garanteze punctaje mai mari de 200.  8)  Dar se pare ca au dat batai de cap..mai ales poly.  Iar easy query si parcare trebuia sa faca departajarea la varf  :ok:

Probleme au avut cam multe restrictii si precizari, si de aceea mi s-au parut mai greu de inteles. Ma refer aici in special la bridge, secv4 si parcare.

A fost un concurs reusit dupa parerea mea, so keep up the good work.  :ok:

intr-adevar problema bridge a avut un enunt destul de ciudat insa acest se datoreaza si faptului ca enuntul a fost schimbat de foarte multe ori din incercarea de a explica cat mai bine si mai clar cum se calculeaza numarul de moduri. Imi cer scuze ptr acel exemplu gresit, care se datoreaza intocmai acestui fapt, de asemenea au mai fost probleme la limita de timp care a fost schimbata pentru ca sursele scrise in Pascal aveau probleme. Oricum in arhiva am inteles ca limita va fi readusa la o secunda deoarece s-a descoperit ca intra si sursele scrise in pascal. Imi pare rau pentru incoveniente.
 Una peste alta noua cel putin ni s-a parut ca (,) concursul a fost frumos si destul de fun. Speram ca si voua vi s-a parut la fel.

Nice concurs-u', defapt chiar mi-a placut ... felicitari pt organizare si pentru munca.
Si apropo, poate mai organizati unul ... peste cv timp   :P :peace:

In timpul concursului comisia a facut si o mica cronica a celor ce s-au intamplat in timpul celor cinci ore. Informatiile trecute acolo sunt luate din evaluator sau din statusurile de pe messenger a participantilor. Fiecare replica inainte de a fi introdusa a fost acceptata de toti membri comisiei (deci va rugam sa nu sariti cu minusuri la karma :D)

14:00:00 Incepe concursul si Vlad d inca doarme.
14:20:31 prima submisie. 0 la poly de catre alexthero
14:20:36 primul punctaj de 100 de puncte la poly a obtinut Prostul
14:27:35 Filip e inspirat :)
14:29:32 Simi observa o greseala in exemplu de la bridge... oups
14:40:42 Se pare ca multi au abordat problema poly dar putini au reusit 100. La nici o alta problema nu s-a reusit 100 de puncte
14:59:34 Filip iar pleaca. Emotiile de concurs...
15:00:13 Devilkind se duce si el la toaleta
15:28:23 A trecut aproape 1 ora jumatate si nici o sursa la Parcare.
15:30:48 Limita de timp la bridge este modificata la 1.3 (Pascalu asta)
15:40:00 Prima sursa de 100 la Bridge facut de Steve Irwin
15:44:46 Gcosmin eroare de compilare la bridge
16:00:00 Filip inchide topicurile. Timpul de intrebari a expirat.
16:09:16 vlad b se duce sa duca gunoiul
16:24:20 Comisia face pariuri privind punctajul maxim
16:29:49 Se trezeste si Vlad d in sfarsit. Si uitati-va cu ce scuza vine  :"astronomy a fost de vina... ca m-a trezit cu 20 minute inainte, si io i-am zis ca e prea devreme..  si     am adormit din nou"
16:35:13 Filip pleaca. De data asta definitiv.
16:54:09 Dupa lungi asteptari gcosmin sparge bariera de 200 de puncte.
17:02:45 Coty vrea sa renunte.
17:09:58 Prima sursa de 100 de puncte la problema Secventa 4. Gcosmin acumuleaza 300 de puncte
17:16:47 Upb_guys vin din urma cu 220 de puncte
17:33:34 Comisia discuta despre istoria Romaniei si a Statelor Unite
17:42:17 Vlad D pleaca la scoala
17:55:23 Statusul Marinei: "busy - ma dau cu capul de pereti" ( va rugam nu deranjati )
17:56:36 Steve Irwin reuseste sa il ajunga pe gcosmin la 300  de puncte. Sa vedem : gcosmin vs Steve
18:06:44 Se pare ca si Upb_guys se alatura luptei din varful clasamentului cu 300 de puncte. Cine va fi primul care va depasi aceasta bariera? (suspans)
18:08:34 Se pare ca a fost nevoie sa ajungem in ultima ora de concurs pentru a vedea prima sursa la problema parcare e drept o sursa de 10 pct a lui Diac Paul insa e un inceput
18:10:49 O sticla de "Lacrima lui Ovidiu" + o bere la ONI pt. cine rezolva Parcare sau EQ
18:36:05 Steve trimite un brute de 36 de puncte la Easy query si trece in frunte cu 336 de puncte. Vor reusi oare ceilalti sa revina??
18:56:11 In timp ce ne asteptam ca unul dintre concurenti de pe locul 2 sa incerce sa il intreaca pe Steve iata ca acestia sunt depasiti si astfel devansati pe locul 3 de catre victorsb cu o diferena de 1 pct
19:00:00 Incheierea concursului si oprirea evaluatorului. Astfel totul se termina.

Se pare ca eu castigat pariul privind punctajul maxim. Vladcyb1 astept o bere. :)

am venit si de la scoala .... =))

lol... ce am mai adormit azi noapte

:'( nu gasisem in 4 ore rezolvarea la poly, iar la bridge presupusesem un PD dar... am zis ca daca nu iese poly si restul iau si ei 0 la bridge nu ma bag... anyway, frumos concurs, pacat ca am pornit cu convingerea ca nu fac nimica...

la mai mare  :thumbup:

Parerea mea este ca Secventa 4 e problema standard pe InfoArena.

Asta e bine sau e rau?  ???

Este si bine si rau! Din punctul de vedere al punctajelor e mai mult spre bine! :)
Tu ce crezi ?

Hm.... concursul a fost marfa doar ca.... la poly cand faceam in O(N^2) luat 40 pct (explicabil TLE). Cand incercam O(NLogN) luam 0 (WA pe toate.... desieu le testam la mine cu teste facute u programul celalalt). Daca a mai patit cineva asta si a descoperit ce avea poate imi zice si mie :D pt. k eu inca nu-mi dau seama dc. As vrea sa aflu.... :) de unde e..... inseamna ca am eu un bug major in Subsirul de NlogN.

Ca tot sunt pe forum, spune-mi cum ai reusit sa scoti O(N log N) !
Eu am 2^7 * N, adica O(N).

Am construit un alt sir b cu proprietatea ca daca am oricare doua elemente i si j (i < j): daca cmmdc( a(i),a(j) ) respecta conditiile atunci b(i)< b(j). Apoi am construit subsirul crescator maximal pe vectorul b :)

Nu inteleg ce contine b[k]. Mai spune! :)

b(k) contine o valoare care e mai mare decat toate valorile b(i), unde i apartine (1...k-1) si cmmdc( a(i),a(k) ) respecta conditiile din enunt.

Apropo de chestii inexplicabile...  ](*,) Rezolvarea mea la problema bridge, desi e O(N*K), a luat 80 pct la concurs (TLE), iar din cauza modificarii timpului de executie in arhiva a luat 40 pct. Apoi am incercat sa nu mai citesc de doua ori :roll: si am luat 50 pct in arhiva... Din cate am inteles solutia oficiala chiar are complexitate O(N*K)...  :-k Are cineva vreo idee pentru cauza TLE-urilor?

nivan, cred ca gresesti la construirea sirului b[].
sims_gl, incearca cu memoizare, deoarece nu trebuie sa calculezi toata valorile din matrice.

 Cred ca ai dreptate desi pana acum am presupus ca partea aia din program e corecta.

 De curiozitate tu cum scoti O(N), ca sa stiu si solutia asta.

{last edit} Desi o sa aflu cand se publica solutiile.

Toata ideea este sa retii pentru fiecare element al sirului initial o configuratie in baza 2, unde daca al k-lea bit este 1, atunci al k-lea element din multimea {2, 3, 7, 11, 19, 23, 37} divide elementul curent.

hmmm ...  :-k

Penal... La sfatul lui astronomy am incercat sa nu mai folosesc %... Acum am 70-80 de puncte, depinde de cum merge evaluatorul  :)


o sa incerc si asta, mc mult!

imi place ideea  :) desi nu va cum ai reusit sa o descoperi

Marius,  interesanta idee, dar nu inteleg totusi, luand un caz particular; sa zicem 14:
Reprezentarea lui in baza 2 este : 1110
Asta ar inseamna dupa ideea ta ca 14 este divizibil cu  2, 3, si 7, dar cu 3 nu este ..  :?

{ultima modificare} : sau te-ai referit la o reprezentare in baza 2, dar nu referitoare strict la reprezentarea numarului ... nu de alta, dar asa am facut si eu, am retinut intr-o matrice a[k] = 1, daca elementul i din sir se divide cu elementul k din multime, dar tot nu imi dau seama cum ai scos O(n)  :-s

{2, 3, 7, 11, 19, 23, 37}
14 e divizibil cu 2, si 7, rezulta configuratia 1010000. Acum sigur te-ai prins! :)

hmmz, m-am prins mai greu avand in vedere faptul k asta a fost si ideea mea, dar mi-am dat seama ulterior, totusi raman nedumerit cum se poate scoate O(n), mi-e nu mi-a venit ideea nici pt O(N*logN)  #-o

Poi daca iti vine ideea de 40 pct adica O(N^2)... iti vine si aia de O(NlogN)

solutia oficiala e aia cu 127*N...

vlad berteanu a facuto in 5 minute tot cu implementare...  :D

enuntzu : scurt
implementarea: scurta

daca iti pica ideea pe loc... o faceai rapid

voi cum faceti in  O(N*logN)  ?

sursa mea foloseste 61 de Mb de memorie, calculez toate valorile matricii si mai fac si dinamica inapoi si a rulat in 0.6 :p

Sims tu faci dinamica inapoi sau inainte??

Bine ca ai scos poza aia =D&gt; +1.

Inainte... Tu cum faci inapoi? :shock: Pt fiecare treapta tii minte de unde te poti teleporta pe ea???

da, am un fel de lista de adiancenta. De asemenea folosind niste rafinamente se poate optimiza la memorie o(n).

OK, eu nu inteleg daca se poate folosi o matrice M[4000][4000]. Din moment ce valoarea maxima pe care o poate atinge un element e 666013, matricea trebuie sa aibe elemente reprezentate pe 4 bytes, astfel matricea ajungand la dimensiunea de 64 MB. Ce imi scapa?

P.S. Eu am rezolvat problema in O(MlogM + N * K) si memorie O(N + M).

4001*4001*4 / 1024 / 1024 = 61 mega.

Multumesc. Sunt un programator amator.

Felicitari pentru initiativa!! :thumbup: Concurs misto, cu probleme foarte "frumoase" (se stie de ce  :wink:) si interesante, si cu niste rezolvari pe masura  ](*,).