infoarena

Pe data de 6 martie va avea loc Olimpiada Judeteana la Informatica (http://olimpiada.info/oji2010/) pentru Liceu. Succes participantilor!

Succes tuturor participantilor!! :ok:

Da, succes tuturor :yahoo:

Sper sa ne vedem cu bine la ONI toata lumea . Bafta la toti .  =D>

Fie ca cei mai buni sa se califice si nimeni sa nu buseasca!

Bafta maine!  :winner1:

Așa să fie  :weightlift:

Mult succes tuturor participantilor ! Sper sa ne vedem la ONI.

Cei de-a 10-a, cum vi s-au parut problemele ? ](*,) :-s

clasa 10= foarte grele .... expozitie-am facut 2 cazuri=))))), si la cealalalta brut
cat ii ia unui calc sa citeasca 400.000 char ?

 Nu posta consecutiv. Editeaza-ti mesajele anterioare.

destul de greute... am inteles ca a doua se facea cu dinamica.... avand in vedere ca nu am apucat sa aprofundez...  :? iar prima... nu am avut destule cunostinte la matematica sa o fac... in rest, nu mi s-a parut extraordinar de grea... am incercat sa o fac cu un backtracking, dar m-a exasperat ca nu afisa tot timpul ce trebuia....

tie cum ti s-au parut??

 :D

L.E. eu am avut noroc cu cppreffernce, ca altfel nu ma descurcam sa citesc chestia aia... si am reusit sa determin si nr. de cuvinte... asta e... acum asteptam deseara rezultatele... :D

la prima am incercat 2 cazuri de ciupeala si la a doua, citeam 400k caractere :)))) in loc sa pun fin.eof , deci 0 puncte..

Fata de ce am avut la locala mult mai usoare dar tot, nu ma asteptam de loc la genul asta ( la 11-12 ).

Ce fel de problema era "immortal" de la XI-XII?

Sunt pe vreo undeva pe net subiectele?

Inca nu.
Deci ti s-au parut foarte usoare sau foarte grele.

a XI-a ceva ? Ati facut careva ? Eu la prima m-am incurcat la BT, nu am reusit sa-mi dau seama unde gresesc, iar la a doua...in cazul in care suma nu depindea de k, da  imi dadea bine, daca nu... In concluzie... zob ](*,)

backtraking .....
Mi s-au parut relativ grele, dar nu de nefacut dak eram putin mai atent, am gresit prosteste :-'

Bravo,  :rotfl: si eu la fel la problema 2.
 A trebuit sa fac 3 surse prin 3 metode diferite si eram demoralizat deja dupa ce nu mi-a iesit prima  :rotfl: .

Sunt a X-a la Colegiul National "Iosif Vulcan" Oradea ... la prima am inventat eu ceva formula geniala si merge pe exemplul lor si pe inca vreo 2 pe care mi le-am laut eu.. dar ma indoiesc ca iau ceva pe ea :fighting: . A 2-a am facut-o cu un vector de structuri in care retineam prima si ultima litera a cuvintelor.. apoi inchideam fisierul si il mai deschideam odata ca sa citesc si sa afisez si cuvintele. Voi? ID mycrosoftx_x , daca aveti chef de vorba :-??  :peacefingers:

La a 9-a cum vi s-au parut? Nivel ridicat, slabute? Eu sunt cam dezamagita, aia cu fractia nu mi-a iesit. Cealalta era realizabila...

la clasa a IX-am gresit la a doua problema din neatentie(n-am fost atent la restrictii). la prima pentru a iesi pe exemple mari trebuia qsort ca sa sortezi linia.

Eu am folosit sort-ul din STL, sigur merge si cu ala.

Frate cum sa iti dai delete in loc de rename la sursa in ultimele 5 minute .....  :fighting:   ](*,) 
Prima mi sa parut destul de usoara si a doua era o dinamica in 3 dimensiuni la care m-am chinuit 2 ore sa o scot. Dar din pacate am dat delete la back si ciudat nu mi-am gasit sursa in recycle bin ... se pare ca voi rata nationala .

Clasa X -- Problema 2 - Text
Intrebare:

Problema a fost facuta cap-coada, insa am terminat-o fix in ultimul moment (cand a venit supraveghetorul sa-mi ia sursa) -- am facut o modificare -- am adaugat o matrice, etc. Primele doua cerinte sunt 100% respectate, se afiseaza numarul de cuvinte si numarul de cuvinte care trebuie scoase, problema este ca eu in loc de un k, sau o alta matrice, am creat o matrice care sa mentina datele de la 'j' -- cuvintele care respectau conditiile care sa imi mentina pozitiile pentru afisarea finala. Toata chestia este ca in exemplul dat -- pozitia cuvantului cu care indeplinea, practic, conditiile este egala cu numarul de cuvinte - 1 care trebuie afisate. Deci, in testul initial imi afiseaza ce-mi trebuie (deoarece cele doua numere coincid), insa, pe alte teste, este foarte posibil sa se afiseze baliverne -- deoarece profesorul imi spunea sa termin (la fix am terminat) eu nu am reusit sa realizez ce variabila trebuie pusa si am gresit litera respectiva.

Problema, algoritmul, programarea, in sine, dupa toate cele considerate, indeplinesc toate conditiile verificarea cuvintelor are loc in mod logic. Singura problema este aceea ... ca o constanta in + face diferenta.

Intrebarea mea este: daca o sa iau un punctaj minim -- daca fac contestatia se poate schimba ceva avand in vedere cele spuse mai sus (ca algoritmul in sine este foarte probabil sa fie bun)?

Multumesc anticipat.

La contestatie nu vei avea voie sa iti modifici sursa iar programul tau va fi rulat din nou pe evaluator (care foarte probabil va da acelasi raspuns). Contestatiile in general se fac pentru a modifica optiunile de compilare sau chestii de genul acesta si nu au respectat regulamentul. (de ex sa zicem ca iti compileaza programul cu borland).

Oh, cool =)
Thanks then :)


Mult succes celorlalti!

Salut colegi ai informaticii. Sunt clasa X-a. Prima problema nu am reusit sa o fac pentru ca nu mai aveam timp de scris din cauza ca am pierdut timp si nu mi-am dat seama ca la a doua problema trebuie sa folosesc flux si incercam sa citesc din fisier cu fstream.get(). Pana la urma am facut problema sa scrie in fisier doar 1. La cea de-a 2-a problema a mers totul OK, era dinamica si a mers bine. Am implementat un algoritm de O(n*n), chiar pacat, nu mi-a mers la teste mari. Apoi am facut o greseala stupida, am pus scrierea numarului de cuvinte dupa algoritmul O(n*n) si nu am luat acel 1 pct pe fiecare test  :fool: :aha:. ](*,). Oricum am ajuns la baraj. As vrea daca se poate o rezolvare de 100 de pct in C++, pentru ca rezolvarea oficiala ii facuta in Pascal  [-X. Sper sa ne vedem la nationala, bafta celor care sunt la baraj, ca si mine  :peacefingers:.

ce baraj  :-s ?

Ce flux la OJI clasa X-a?

Pai sunt la baraj, pentru ca am iesit la egalitate cu cineva din judetul meu, iar miercuri trebuie sa ma prezint. Iar despre flux, la problema 2-a la clasa X-a este nevoie sa citesti niste cuvinte dintr-un fisier. Primul lucru care l-am incercat eu sa-l fac a fost sa folosesc fstream.get() si strtok(). Mare greseala daca faceam asa, oricum am pierdut mult timp cu asta si nu mi-a dat nimic, apoi am folosit fstream>>pointer(f>>p;).

Nu mai pot ce ofticat sunt. Problema 2 n-am stiut-o si am lasat-o dar prima a fost super simpla (la XI-XII) . Dar nu inteleg ce naiba s-a intamplat ca am luat 0 puncte  ](*,). M-am uitat la solutie si pare aproape copy-paste dupa solutia mea, difera doar numele la variabile si ceea ce probabil mi-a adus cele 0 puncte, in loc sa adun elementele cu +1 am adunat cu +2, nu stiu ce m-a indus in eroare, mi-a ramas in minte dubla bordare a matricei. Deci nu mai pot de ofticat ce sunt. Asta e, mereu am ghinionul asta sa gresesc o prostie din asta.
Asta e, in cazul informaticii poti sa stii problema 99,9% daca gresesti ala 0.01% s-a dus totul. Acu n-am decat sa invat pentru urmatoare judeteana dar parca nici nu are rost ca sigur o sa fac la fel  :'(.
Anyway bafta celor calificati la nationala  :ok:....

- Cosmin - puteai sa citesti cuvant cu cuvant sau linie cu linie; Spre exemplu declarai o matrice de cuvinte c[n][m]; apoi
k=0; while (f>>c[++k]); si ar fi trebuit sa iti citeasca tot. Am vazut ca multi s-au complicat cu citirea din fisier si nu inteleg de ce.

aceeasi greseala si la mine, penibila problema, plus ca era dinamica pt 100p.am uitat de var.eof()...
no comment

salut! stie cineva daca pot sa merg mai departe cu 20 pt (primul pe judet)?

M'am uitat acu cateva minute peste rezultate din cateva judete, si in tulcea era cineva calificat cu 10 puncte. Dar nu vreau sa'ti dau sperante false ... depinde de fiecare judet decide pe cine sa trimita. Daca sunt punctaje mai mari la alte clase s-ar putea sa mearga aceia..

sper sa trec. Problema e ca daca mai stateam un pic reuseam sa o fac si pe a doua. In plus comisia era de forma la mine (la toate  NO COMMENT indiferent de intrebare)

http://olimpiada.info/oji2010/index.php?cid=rezultate&w=lic
ia vezi, poate s-au afisat la judetul tau ;) multa bafta

nu s-au afisat dar eu stiu ca am luat 20 pt si sunt primul pe judet la cl 9
cred ca din cauza contestatiilor(se termina la 18:00)

Ambele au fost usoare( dar necesitau atentie  :)  ). Eu am gresit la a 2-a ca nu am fost atent si am facut o rezolvare gresita dar care totusi ar fi luat 10 puncte( pentru locul 1 la noi in judet era destul stii si tu) :'(.
Si apoi am incercat si cu backtracking si cu memoizare( si chiar asa se face) si nu au iesit( recursivitatea asta :-').
In orice caz mai rau este de judet decat de noi, 22 de elevi din 23 cu 0 puncte, poate reparam onoarea la anul :-' .

La fel si la mine. Prima am facut-o cu back si mergea pe tot ce am dat eu, inclusiv exemplul din text. A doua cu dinamica si la fel dadea bine pe toate exemplele care mi-au trecut prin cap. Ca sa ma trezesc ca iau 0 pe prima si 10 pe a doua  ](*,)

Pe viitor recomand mai multe teste in exemplu, poate chiar si accesul la evaluator (nu si la teste) in timpul concursului pentru ca pleci acasa cu gandu la 100+ si te trezesti ca mine  ](*,) Nici nu e logic, ca daca e sa creezi un program pentru tine, stii clar pe ce date vrei sa-ti functioneze, nu trebuie sa ghicesti cazurile particulare, care de obicei sunt date ca exemplu :fighting:

S-au afisat testele la a 10-a? Eu nu le-am gasit ...

Asa e, nu -mi vine sa cred ca avem calificat cu 10 puncte si restu avem 0. Si sa nu mai vorbim ca in aia cu 0 sunt cativa care chiar stiu informatica calumea si au avut rezultate foarte bune si la nationala. Sa vad la concursu de saptamana viitoare poate ma califica la nationala la ala  :rotfl: daca la asta n-am fost in stare.
Pana la urma mare lucru nu stiu daca faceam la nationala asa ca in starea in care sunt acum ma ambitionez mai mult si poate per final ma aleg cu mai multe decat daca ma duceam la nationala (acu sunt pus mai mult pe treaba desi daca am tot ghinionu asta ma las pagubas :aha:)

Si eu ma asteptam sa mearga brici a doua problema(XI-XII) si m-am trezit cu 0 pct. :winner1:

Văd că şi dacă nu te prezentai aveai şanse să te califici. :)

am reusit sa ma calific. Mii de multumiri site-ului infoarena!!!  :winner1:

Felicitari  :D bafta la ONI

Eu am pierdut 100 de p din cauza la un spatiu in printf ..... am inteles ca nu se pot face modificari in sursa asa ca nu o sa ne mai vedem la oni .  :'(  Felicitari tuturor care sau calificat , si pentru cei care au busit si nu sunt a 12 a poate va  consoleaza faptul ca mai avem o sansa la anu . Problemele au fost foarte ok la 11-12 dar am inteles ca la a 9 a a fost cam rupere.

Incredibil.... eu am pierdut 50 de puncte din cauza unui while caruia nu i-am pus bine conditia de "finish" (pe exemplu a mers).

Iar la a 2-a problema nu m-am incadrat in timp. Am incercat sa implementez Dijkstra (fiecare nod sa aibe legatura cu nodurile adiacente pe verticala,respectiv orizontala) .
Stie cineva daca Dijkstra ar fi fost o solutie viabila ?

multumesc.

Nu prea cred ca puteai sa faci dijkstra ca mereu schimbai nodurile si muchiile si dijkstra iti afla un traseu de lungime minima.Ce costuri aveai tu pe muchii ? aveai costul 1 deci puteai sa faci bfs si mai scuteai din timp . Dar ideea era ca tu daca faceai bfs cand mergeai dintr-un nod in altu trebuia sa vezi daca mai trebuie sa adaugi muchii si trebuia sa faci si stergeri ... si tu trebuia sa afli un traseu maxim care sa treaca prin toate nodurile iar bfs-ul iti afla un traseu de lungime minima .  Parerea mea e ca doar back mergea de 100 .

A doua problema era "joc". Back-ul era pentru prima("immortal").



@moon: Eu cred ca nu ajungeai la un rezultat bun aplicand Dijkstra. Trebuie programare dinamica.

Cum ai facut dijkstra? ai inversat semnul numerelor , ca sa poti sa afli maximu ? :-k
ai luat ceva puncte pe ea?

Nu am luat nimic pentru ca nu am avut timp sa il termin :(
Ideea era sa initializez o variabila cu valoarea lui a[1][1], dupa care sa aflu distanta maxima (cu inversare de semn) intre a[1][1] si a[2][n] (pe baza grafului), si odata aflata acea distanta sa afisez d[n]+x. (costul de la a[j] - a[j+1] = valoarea ce se gasea la coordonatele i,j+1. , asa ca la final ramanea valoarea lui a[1][1] neadaugata).

Se putea construi lista muchiilor impreuna cu costul astfel : a[j] - a[i+/-1][j] ,  a[j] - a[j+1] .

Teoretic ar trebui sa mearga. Insa nu am vazut Dijkstra declarat drept solutie oficiala ...

Esti sigur? Eu am inteles ca nu are cum s-o trimita cu 10 puncte. Desi nu prea schimba datele problemei insa acum si eu ma oftic mai tare ca nu am trimis prima sursa  :aha: chiar daca stiam ca nu da bine ca luat 10 :rotfl:.
La ce concurs te referi? La cel de la Campulung? Are si faza nationala  :shock: . Eu nu stiu prea multe detalii abia astazi am aflat de el si i-am spus lu' profu' sa ma inscrie.

Da, si eu puteam lua 100 pct, cu primul loc la nationala, dar in loc de un for de la 1->m am uitat sa-l schimb si am pus 1->4.  :'(. Asta e, soarta.

Si cum verificai daca drumul nu contine mai mult de "k" celule consecutive pe aceeasi linie? :fool:

Cel mai probabil construia muchii de la (i,j) doar la k elemente precedente :-k

Din cate stiu e cam al doilea concurs dupa olimpiada ca importanta, sau ceva de genul.
Stie cineva unde pot gasi subiecte la etapa judeteana a concursului "Urmasii lui Moisil" ? sau sunt facute de fiecare judet in parte ?
Si cam cate locuri sunt pe judet ?

Al doilea concurs ca importanta dupa Olimpiada este Algoritmiada, parerea mea. :P

Perfect de acord :P

Poate cineva sa faca o poza cu lista q punctajele afisata la Vianu? k ajtia pe site nu o posteaza nici mortzi ji stau q  :banana: in :shock: . Mor sa stiu dak am trecut.

Ma rog, eu ma refeream ca el doilea concurs ca importanta dintre ce cele care nu se desfasoara online, adica de care stie tot poporu. Algoritmiada e un concurs online in cea mai mare parte (exceptie ultima runda parca adica pentru cei calificati).
Ma rog, mai putin ma intereseaza asta.
Dar nu inteleg de ce anu asta se organizeaza faza judeteana, concurentii nu erau alesi dintre participantii la oni ?

Locul 2 la OJI in BH .. am inteles ca am baraj miercuri  :-k

Succes la ONI  :ok:

Al doilea concurs ca importanta este Olimpiada, dupa Algoritmiada :P.

Salut ! Va rog sa ma lamuriti si pe mine cu cateva chestii caci particip pt prima data la oji.
In primul rand, m-ar interesa cum se face selectia lotului judetean. Judetul nostru are 10 locuri. La clasa mea eu am fost al treilea, dar am inteles ca am o sansa sa ma calific daca la clasele celelalte sunt punctaje mai mici. Am observat ca sunt al 6 pe judet dupa punctaj.(incluzand toate clasele)  :-k

Si inca ceva...Din experienta voastra, dupa contestatii, se mai pot schimba multe lucruri ? Adica nu imi dau seama cum o sursa ar putea obtine un punctaj mai mare. Totusi sper sa nu ma trezec cu cine stie ce punctaje dupa contestatii, ca apoi  ](*,) ](*,) ](*,)

Salut, am si eu o intrebare, am participat la clasa a X-a la OJI si am luat pe problema 2 "text", Memory limit exceeded cu

d,max,i,n,j,k:integer;
    s,l:array[1..20000] of char;
    ret,al:array[1..20000] of byte;
    st:array[1..20000] of string;
    cuv,ct:longint;
    v:array[1..400000] of char;
    f,g:text;

era normal sa iau memory limit exceeded??? In freepascal imi intra in limita de 2 mb(1 mb stiva).

Cred ca fiecare judet are modul sau de a-si forma lotul. Cel mai logic ar fi sa trimita elevii aflati cel mai sus in clasamentul pe tara de la OJI.

La contestatie se ruleaza din nou programul pe teste. Nu ai voie sa modifici absolut nimic in sursa.

Ai 1 MB = 1048576 Bytes pentru variabile globale.

    d,max,i,n,j,k:integer; - 12 bytes
    s,l:array[1..20000] of char; - 40.000 bytes
    ret,al:array[1..20000] of byte; - 40.000 bytes
    st:array[1..20000] of string; - 255 x 20000 = 5.100.000 bytes
    cuv,ct:longint; - 8 bytes
    v:array[1..400000] of char; - 400.000 bytes
    f,g:text;

Exact. Nu prea aveai cum sa te califici daca incepi programarea din clasa a IX-a. Si eu am avut mare noroc ca m-am calificat.

Pai si asa ar fii bine...

Mda a fost cam greu la clasa a 9-a.Nu stiu dc chiar "rupere" eu intr-a 9 am inceput informatica si am doar o ora pe saptamana si problema a doua era chiar simpla daca iti dadeai seama de o chestie(evident eu nu mi-am dat  :fighting:) Dar din cate am observat, la a 11-a, a fost cel mai greu in conditiile in care in judetul nostru e doar un punctaj de 10 si restul de 0.

Apropo pt nationala cam ce ar trebui sa stii la clasa a 9-a ?

Eu cred ca te poti astepta la orice. Nationala e natioanala. Cu cat lucrezi mai mult si stii mai multe cu atat mai bine.

La a X-a, prima problema se facea cu o dinamica o(N * D * numere mari), iar cealalta cu o dinamica o(N). In niciun caz flux, desi ma gandisem in timpul concursului la asta.

A gasit cineva testele pentru OJI postate pe undeva? pe olimpiada.info apar numai enunturi si solutii .. acolo apareau de obicei...
Sunt foarte curios pentru ca la XI-XII m-am concentrat pe " joc " ( o dinamica am incercat ) si eram convins ca e buna.. defapt am luat doar pe cealalta ceva.. cred ca am depasit limita de memorie ca am fost cam "darnic" cand am declarat si nu am mai reveni ulterior.. ma rog daca stie cineva ceva despre teste, spuneti va rog! mersi

Am eu evaluatorul. Da PM cu mail si ti-l trimit.

Teodor Anton Pripoae, explica-mi si mie putin modul tau de gandire la problemele de la a X-a  :-'

Iti explic eu :).
Prima problema ar putea fi reformulata in felul urmator: sa se gaseasca numarul de partitii ale lui N (partitie = sir de numere cu suma N), de lungime D (adica formate din D numere), astfel incat fiecare numar din partitie sa fie >= K. Pentru a rezolva asta facem programare dinamica: C[ i ][ j ] = numarul de solutii daca am fixat primele i numere din partitie si avem obtinuta suma j. Raspunsul se va gasi in C[D][N]. Te las sa te gandesti la recurenta, daca vrei ti-o zic. Se poate face in O(N^2 * D) - facand dinamica inainte, sau daca optimizezi in O(N * D), cu sume partiale.


La cea de-a doua e mai simplu, dupa ce ai determinat toate cuvintele tii sirul D[ i ] cu semnificatia lungimea maxima a unui lant avand proprietatea din enunt care se termina cu cuvantul i, si L[ch] = lumgimea maxima a unui lant pana la pozitia i (adica din ce am calculat pana acum) care se termina cu caracterul ch. D[ i ] = L[prima_litera_din_cuvantul_i] + 1. Si daca D[ i ] > L[ultima_litera_din_cuvantul_i] atunci actualizezi valoarea din L. Raspunsul va fi numarul de cuvinte - maximul din sirul D (numarul minim de cuvinte eliminate). Pentru a face reconstituirea se tine un vector suplimentar, prev[ i ] = cuvantul care vine inaintea cuvantului i in solutia care da valoarea D[ i ].

Sper ca ai inteles! Spor la implementat! :)

Ca sa verific k-ul as fi putut sa implementez de mai multe ori dijkstra (de 9 ori maxim, din moment ce k era intre 2<10) ... sau as fi putut sa construiesc muchiile treptat, pe baza celor vizitate anterior  :-k.

Oricum, chiar si daca nu as fi verificat k-ul, sunt sigur ca ar fi obtinut >= 30 puncte.

Nu inteleg ce e gresit la urmatoarea dinamica (inafara de faptul ca gradul de complexitate nu este optim ) : (clasa a X-a, problema a 2-a )
nrmin[ i ] = numarul minim de cuvinte ce trebuie sterse (din primele i-1 cuvinte ) ca sa obtinem un text ce respecta regulile enuntului, acel text terminandu-se cu al i-lea cuvant

Daca nu iei k-ul in considerare = 0 pct.

evaluatorul folosit se poate gasi undeva? nu inca nu? sau? iar despre teste? :-s daca le aveti sau ceva.. spuneti.. skull ti-am dat PM cu mail(mai devreme si am dat unu si acu)  sa imi trmiti daca ai, mersi!

garantez si eu pt asta, ca asa am facut eu, nu l-am luat in considerare si ma asteptam sa prind ceva puncte, dar de unde...0. :aha:

N-am primit niciun PM.

Gasesti evaluatorul pentru XI-XII aici (http://fisierulmeu.ro/28VV3LBNJT37/Eval-1112-rar.html) sau aici (http://www.filehost.ro/847040/Eval_1112_rar/).

am dat 3 PM-uri nush de ce nu s-au trimis.. mersi l-am luat

@skull   Il vreau si eu pentru a X-a te rog. Il ai ?

LE : Ti-am dat si eu PM.

pune-l si pe cel de-a zecea te rog aici :thumbup:

Cam asa am facut si eu.

Nu-l am decat pe cel de la XI-XII. :thumbdown:

Au fost adaugate problemele de la OJI 11-12 in Arhiva de probleme (http://infoarena.ro/arhiva?display_entries=50&first_entry=950).

Metoda greedy obtine 10 puncte si nu tine cont de k....

Bogdan Andre, te rog pune si la a 10-a

Problemele de la a 10-a cat si de la a 9-a sunt in lucru. Vor aparea zilele urmatoare  :)

Felicitari Marius!

http://olimpiada.info/oji2010/index.php?cid=rezultate&w=lic&judet=09&clasa=12

 :shock: :shock: :shock: :shock:
am vorbit cu cineva o sa se modifice :D :ok:

http://www.liis.ro/~cex_is/Informatica/pregatire.html


gasiti aici evaluatoarele pt orice clasa la "arhiva si evaluatoare"

Felicitari celor calificati! Ne vedem la ONI :P.

Eu am luat 70 de puncte, back la ambele probleme (a XII-a). Pt immortal imi mai ramasese doar o ora si in graba am facut o eroare in gandire si am facut o solutie cu complexitate mai mare decat era nevoie. Am luat 40p :)).

ne vedem la oni friendz ;)  :weightlift:  :banana:

cand se pun loturile  ???

Asta depinde de fiecare județ. La noi, de exemplu s-a afișat lotul pentru oni.

E real sau e doar un scenariu inventat de tine pt a ironiza subiectele ?  :ok:

din pacate,real....

@ Radu Vlad: Nu sunt de acord cu tine.
La prima problemă, Gigel ar fi trebuit să citească limitele, iar cu puțină experiență și-ar fi dat seama că o abordare de tip greedy nu ar lua mai mult de 10 puncte, și că problema nu pare a admite soluție polinomială.

La cea de-a doua problemă, dacă ar fi citit din nou limitele ar fi văzut N <= 5000 și K <= 10. Cum K << N (a se citi mult mai mic) este destul de evident că o rezolvare care nu ține cont de K e extrem de probabil să ia 0. Iar dacă nu îi venea ideea de dinamică în mod sigur ar fi fost mult mai bine să facă un back. Decât un greedy cu șanse serioase de a lua 0, mai bine un back care să ia 40, și povestea cu profesoara care i-a zis să nu facă back mi se pare absurdă.

Ca o concluzie, subiectele mi s-au părut echilibrate, nu au fost nici prea simple, dar nici prea grele, motiv pentru care comisia cred că ar trebui felictată pentru efortul depus.

polinomiala?saracu Gigel n-a auzit de asa ceva,face info dintr-a 9a,nu de secole...

omule,daca tu vezi back intr-o problema din aia(2)....respectul meu...ei bine,mie imi pare rau dar nu vad...recunosc,nu imi place backul,nu pentru ca nu as sti sa-l folosesc,ci pentru ca e ineficient.oricat ai imbunatati un back,tot ineficient ramane....dar ma rog,fiecare vede cum are ochii.

zici ca sunt echilibrate....uite , ca sa-ti dau o statistica...in 2009 primii 100 de informatiieni de clasa a11a au avut peste 58 de puncte...anul asta doar 32 au resit aceasta performanta...nu crezi ca e o discrepanta cam mare?deasemenea,doar 42 de a12a din cei 100 de anul trecut au luat peste 58....asta in cazul in care mai sunt unele persoane care spun ca din a11a pana in a12a mai inveti informatica

daca deranjeaza postul meu,spuneti si-l voi sterge...is doar frustrarile mele pe care nu am avut unde sa le postez,asta e!o sa inghit in sec!

Mi-e mi s-a parut anul asta mai usor decat in ultimii 2-3 ani ( referitor la problemele de la cls 11-12 ). Si da, daca ai pretentii sa rezolvi probleme de OJI, ar trebui sa stii sa faci legatura intre restrictii si rezolvare. De obicei, restrictiile iti "dicteaza" complexitatea rezolvarii. Repet, back la a-11a, mi se pare usor.

Polinomială este derivat din polinom, mai pe scurt nu poți găsi un algoritm care să aibă complexitatea N², N⁵ sau N³⁷.

Sunt de acord că backul este ineficient ca timp. Dar limitele erau mici (N, M <= 20 și cel mult 15 nemuritori), deci nu se cerea ceva eficient ca timp și mai degrabă ceva care să dea rezultatul corect. Recunosc că și eu m-am țăpit la problema asta pentru că în loc de back am făcut o chestie care deși ajungea mai repede la rezultat mânca mai multă memorie și am pierdut 50 de puncte.

În legătură cu rezultatele ai dreptate, în sensul că sunt mai slabe decât anul trecut, dar dacă te uiți sunt 25 de oameni de a11a care au peste 100 si 35 de a12a. Prin urmare, eu zic că se putea.

Îți înțeleg supărarea, pentru că s-a dat ceva ce nu se prea aștepta nimeni, dar nu trebuie să te descurajezi. :)

Asta ar trebui privita ca pe o experienta de invatare din care tragi 2 concluzii importante:

- Referitor la problema 1: Nu exista asa ceva ca "cea mai ineficienta metoda de programare", nu toate metodele de programare fac acelasi lucru. Backtracking-ul are un scop: sa exploreze toate posibilitatile, trebuie sa realizezi ca nu toate problemele pot fi rezolvate cu solutii mai rapide. Daca reusesti sa o faci fara backtracking, s-ar putea sa fi eligibil sa iei un milion de dolari. http://en.wikipedia.org/wiki/P_versus_NP_problem :)

- Referitor la problema 2: Nu te poti astepta sa iei mai multe puncte cu o solutie care rezolva *alta* problema, decat cu o solutie care rezolva problema corect dar e mai eficienta.

In plus, la scoala se studiaza backtracking, si exista probleme care se rezolva cu backtracking'ul. Probabil nu te plangeai daca aveai ceva permutari sau combinari de facut..

Totusi, e olimpiada si e normal sa fie ceva original, si mai greu decat o problema clasica.

In principiu ar trebui sa stii ca backtrackingul e defapt cel mai important algoritm pentru olimpiada. Au fost ani la oni in care doar daca faceai back la toate te clasai in primii 20, eventual intrai si in lot. De asemenea orice problema pe care nu intelegi cum sa o faci (si esti bun, adica nici ceilalti nu or sa fie mult mai buni ca tine) fa-o cu back, ca s-ar putea si fii singurul care ia ceva puncte pe ea. Si noua ne spun profii sa nu folosim niciodata back ca e prost, mai ales cel recursiv (desi ma indoiesc ca o sa fie usor sa implementezi ceva iterativ), dar daca ar fi sa ascultam de ei ... multi nu s-ar califica.
Oricum e clar ca subiectele de anul asta au fost incredibil de usoare, cred ca doar a fost ceva in atmosfera in timpul oji si d-aia au luat multi punctaje mici  :P.

In primii 20 sa intri doar cu back...... poate doar la clasa a 11a , ca acolo sunt punctaje mici....iar despre lot nici vorba!
E bine sa stii back, poti sa-ti verifici sursa cu el.... iar cel recursiv nu e mai lent decat cel iterativ (nu se simte diferenta prea mare).

daca tie back-ul ti se pare original , imi pare rau ca te contrazic...in rest,prefer sa nu mai comentez... traiasca back-ul....

Ar trebui sa intelegi ca tu nu ai experienta oamenilor care ti-au raspuns si in loc sa-ti plangi soarta, sa inveti de la ei pentru a fi mai bine pregatit. Un factor important, adesea decisiv, la Olimpiada (la toate etapele) este psihologia de concurs si, din povestea ta, mi-a fost foarte clar ca tu duci mare lipsa de asa ceva. Poti depasi acest neajuns lucrand mai multe probleme (nu doar in ajunul Olimpiadei) si participand la mai multe concursuri (Algoritmiada, .campion, etc.).

Anual, vad ca foarte multa lume are pretentia sa ajunga la Olimpiada Nationala, dar foarte putini cunosc si sunt dispusi sa faca sacrificiile necesare pentru asa ceva.

Foarte adevărat grăiești din punct de vedere al sacrificiului și al pregătirii. :ok:

:) cred ca rezolvatul de probleme interesante e distractiv si motivant nu e un sacrificiu.

Cred ca Paul se referea la timpul "asa zis pierdut" cu pasiunea ta. Eu cel puțin am o plăcere imensa când rezolv o problema pe infoarena de 100p. Am asa o satisfacție ca am învățat ceva nou. Poate alții nu au același interes.

Scenariu: Gigel scrie paragrafe, nu totul pe o linie.
Concluzia: Cineva citeste ce a scris. :wink: