"Finala Algoritmiada este considerată cel mai important concurs naţional din România, iar acest statut i-a adus colaborări cu diverşi sponsori." Desigur, un pic de modestie nu ar strica. Nu cred ca cineva ar alege participarea la finala Algoritmiada in defavoarea Olimpiadei Nationale de Informatica sau poate ma insel eu...

Cateva chestii mai urgente ar fi aducerea la zi a articolelor care prezinta solutii la problemele de la concursurile care au avut loc pana acum.
Imbogatirea arhivei educationale cu noi articole/probleme avand in vedere ca pagina de proiect stacneaza de ceva vreme iar unele par a fi terminate dar nu sunt puse de site.

Ar fi ok daca ati incerca sa reduceti overhead-ul pus pe cei din organizatie astfel.. lasati mai libera comunitatea prin posibilitatea de a pune tag-uri la probleme ( si aici sunt mai multe optiuni gen: fiecare concurent poate sa puna tag-ul corespunzator solutiei abordate etc... ); notarea nivelului de dificultate printr-o apreciere subiectiva a utilizatorilor care au rezolvat deja problema si sa avem o medie peste notele acestea. Stiu ca libertatea prea multa poate sa aduca haos contrar calitatii in informatie insa nu cred ca abordarea de tipul parental/directional e benefica mai ales ca devine din ce in ce mai greu de realizat ( multa munca ).

Liber la surse! Asta cred ca se poate face foarte repede si usor.

Un lucru pe care il mai folosesc este un wiki intern pe proiect. Bun pentru mentenanta in dezvoltare. Exista mai multe astfel de solutii.

Ai uitat sa spui despre tool-uri gen Beyond Compare, foarte utile cand lucrezi in echipa.

O veste foarte trista...

Facultatea aduce un plus de valoare in pregatire. Este o perioada in care sunt prezentate multe directii practice si teoretice ale domeniului de care ai sansa sa nu fi auzit ( pentru ca oricat de autodidacti am fi noi exista tot timpul directii de cercetare care ne scapa ) si care iti vor schimba perceptia asupra modului cum interactioneaza lucrurile.

Cu toate astea am o parere putin diferita . Cred ca poti sa inveti si singur. Problema este insa curba de invatare care este mult mai lenta ( informatia exista… universitatea nu este singurul loc unde se gaseste ) insa este nepractic/neeconomic etc ca sa fi nevoit sa cauti tot timpul tu informatiile despre un anumit domeniu pentru ca pana a ajunge sa dai de cartea care merita sa o citesti va trebui sa mai citesti inca nu stiu catea care sa te duca la ea… si asta de cele mai multe ori e o pierdere de timp… sau pentru ca poti sa primesti intr-un mod comprimat informatia care altfel ar trebui sa necesite mai mult timp. De altfel avantajul unuei facultati este si posibilitatea de a interactiona cu oamenii care au o anumita experienta in domeniul respectiv si asta nu numai prin intrebari legate de problemele de intelegere a materiei ci chiar in timpul procesului de invatare ( in timpul cursului - este mare lucru sa nu ramai blocat intr-o chestie marunta si sa poti sa treci la urmatoarea problema - ).

Viziunea de ansamblu pe care ti-o poate prezenta in cadrul unui curs asupra noilor notiuni este inca un lucru important care altfel ar necesita mult mai mult timp personal din partea fiecaruia.

Tibi : Domnu' Stupariu are un stil de a preda care il scoate in evidenta in facultate
Daca vrei o documentatie de OpenGL/grafica iti dau eu bibliografie… dupa cum spuneam… necesita ceva timp sa sti ce sa cauti… informatia este insa acolo

Gratuit ? Adica profesorii nu sunt angajati.. nu sunt platiti? Fac munca benevola? Si nu... faptul ca sunt prost platiti nu poate fi nici asta o scuza...

Insa ar trebui sa te gandesti inca odata la ideea de gratuit... ultima data cand imi amintesc cam jumatate din salariul meu se duce la stat pe tot felul de taxe. Asta face ca sistemul de invatamant sa nu fie "gratuit" iar cum eu nu pot alege sa platesc sau nu taxe am tot dreptul sa fiu revoltat pe modul in care banii ( si ai mei ) ajung in buzunarul unor oameni a caror evaluare ( de care am eu parte la job anual ) nu aud sa fi facut schimbari ( dat afara ) personalul care nu corespunde pozitiei ocupate.

Cat despre bursa... motivul pentru care statul o da este pentru mai multe motive insa scopul final este acela de a incuraja performanta ( nicidecum nu ar trebui confundata cu cutia milei de care ar trebui sa ma bucur doar pentru ca este ceva in ea ). Cand statul ofera o bursa cu care iti ei max 2 carti bune asta arata cat ii pasa lui pentru ca noi ( muritorii de rand ) sa putem sa avem parte de o pregatire buna. Nu ma trimite la biblioteca, eu am dat exemplu legat de carti la fel de bine putea fi altul.. si nu, la biblioteca nu am gasit muuulte carti bune care ar fi fost necesare. In continuare am pretentia la decenta din partea statului tocmai pentru ca pentru banii aia lunar care ii dau ( sau i-au dat parintii mei pana acum, etc .. ) statul roman vine si spune "vei avea aia, aia si aia.." lucruri pe care eu nu le vad.

Oricum, sa sti ca nu statul roman a inventat invatamantul public si sistemul de burse ( o fac mai toate statele ) problema este modul in care o aplica pentru ca la noi statul mimeaza implicarea si sustinerea pregatirii oamenilor insa stie sa le ceara taxele dupa ce ajung sa se angajeze.

Sa sti ca multi studenti aleg un drum "gresit" tocmai pentru ca nu isi permit sa traiasca altfe... ( nu am zis toti.. dar foarte multi ) si ajung sa se angajeze. Asta nu inseamna ca nu stiu ca vor pierde... doar ca nu toata lumea are luxul de a alege...

Ar mai fi un lucru, sumele de bani pe care statul le plateste per student sunt relativ de aceas valoare cu sumele date de studentii la taxa. Asta ar trebui sa iti ridice un semn de intrebare pentru ca studiile la noi sunt mai scumpe per student decat in strainatate insa calitatea se degradeaza de la an la an. Dubios, nu?

Ca o concluzie. Platesc ! Platesc prea mult...

"Cercul" asta vicios este "aprovizionat" si de sistemul de invatamant din romania care parca te impinge spre directia gasirii unui loc de munca ( sa fim realisti, bursele sunt niste glume proaste cand vine vorba de valoarea lor, am zis de burse pentru ca teoretic ele sunt "varianta" financiara pentru locul de munca ). Pentru asta studentii nu sunt vinovati .

Despre vina profesorilor se poate spune doar un lucru. Nu au nicio scuza pentru ca isi fac treaba defectos ( cei care nu si-o fac... si nu sunt cativa, modul in care se trateaza student in general nu este de ai atrage catre facultate ci mai degraba cu nepasare si superficialitate ). Neprofesionalismul e ceva ce tinde sa acapareze modul in care sunt sustinute cursurile la master. O spun in cunostinta de cauza dupa mai multe peripetii neplacute la un master la AC in Poli.

Ar mai putea fi mentionate si :

Modern C++ Design: Generic Programming and Design Patterns Applied de Andrei Alexandrescu

http://www.amazon.com/Modern-Design-Generic-Programming-Patterns/dp/0201704315

Compilers: Principles, Techniques, and Tools (2nd Edition)  de Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman

http://www.amazon.com/gp/product/0321486811/ref=pd_lpo_k2_dp_sr_1?pf_rd_p=1278548962&pf_rd_s=lpo-top-stripe-1&pf_rd_t=201&pf_rd_i=0201100886&pf_rd_m=ATVPDKIKX0DER&pf_rd_r=1M638GB72K1S3Q5GQAZ7

Modific modul in care lucreaza update() si query().
Cand o sa am un link de la articol o sa il postez aici.

 Arbori indexati binar se pot utiliza in calcularea min/max la fel ca si arborii de intervale. Mai important, exista solutie in logN amortizat folosint arbori indexati binar.
 
Practic, cele doua structuri de date sunt la fel de puternice !

Un design bun face foarte mult !

Realitatea dupa care toti fugim ! Realitatea pentru care parintii vror sa ne duca la cele mai bune scoli generale, pentru care incercam sa luam note cat mai bune la capacitate pentru a ne duce la cele mai bune licee, motivul pentru care invatam sa ne ducem la cele mai bune facultati, motivul pentru care vrem cele mai bune job-uri. Toti luptam pentru asta, e ceva natural. Stiu ca solutia e mai grea dar asta e adevarata solutie care sa rezolve cu adevarat ceva. Faptul ca o facem niste reguli care sa mutileze avantul unui varf sau altul nu consider ca este de apreciat si nici unul care sa aduca rezultate benefice.

Ok, vad ca nu s-a inteles destul de clar ce am spus. Modul in care pui problema este gresit. Nu ICHB-ul il ia… ca nu vine si il fura ( sechestreaza , obliga ) elevul vrea ( de cele mai multe ori chiar inainte ca cineva sa ii faca o propunere ). Asta este motivul adevarat care a iscat acesta discutie. Faptul ca oamenii nu sunt altruisti ci chiar se gandesc la ei prima data. Si pe buna dresptate, de ce as vrea sa stau intr-un loc unde de cele mai multe ori nu invat nimic? Asta e realitatea!

In in al doilea rand unul din scopul competitie este corectitudinea. Motivul pentru care olimpiada de informatica este apreciata este datorat modului in care se face evalurea. Rolul comisiei este minimizat la maxim si mi-a placut asta. Stiu cum se face la alte materii unde 10 sutimi date aiurea te duc mai sus sau mai jos si ia si trage la raspundere… e si complicat. Totusi competitiile de tipul acesta ( fara echipa ) nu pot fi bagate in aceas oala cu celelalte ( baschet … etc ). Principiul meritocratiei a tinut faima competitiei. Pana acum puteai sa spui "m-am calificat pana la etapa X" si era total rezultatul tau; acum ai sanse sa fie din cauza unei comisii. Si da, sunt paranoic nu din cauza comunismului  ( care tinde deja sa fie un cliseu care ma irita, sunt tari vestice in care chestia asta este mai urata ca la noi, chiar si in state, oricum nu asta e subiectul nostru ) ci pur si simplu pentru ca se distruge un principiu amestecand oalele. Doar pentru ca US si altii fac altfel nu inseamna ca trebuie sa fiu deacord sau sa imi placa.

Stiu cum se face cand sunt mai multi. De cele mai multe ori se duc primii la fiecare clasa ( daca sunt punctaje egale si trebuie sa mearga unu se da baraj ) .

Nu e important cate exemple pot sa dau . Important a fost sa arat ca exista. De altfel cate exemple poti sa dai tu invers? 1 max 2 ( dar nu as zice mai mult. Daca mai scotocesc cred ca mai gasesc si eu unul. Motivul unor astfel de rezultate desi pare dubios este datorat si unei ambitii si munci continue. Un pic de credit si pentru elev .

In principiu toate aceste "sabloane" le cunosc. Nu am terminat chiar ieri liceul . Tu chiar crezi ca motivul rezultatelor slabe ale provinciei sunt date doar de plecari ale elevilor? Eu ma indoiesc… motivele sunt mult mai complexe. Cand eram in in liceu si era la inceputul competitiei campion la clasa 10 erau sute de participanti. Acum abia daca mai erau 50 de participanti in toata tara. Frumos, nu? O scadere a interesului care are la baza altceva decat plecarea a catorva oameni. Asta e o problema mult mai profunda iar tu vrei sa o tratezi la suprafata.

Si inca ceva, stiu ce inseamna sa fie unul bun, stiu cum ii trage dupa el pe cei din clasele mai mici… e ceva normal dar sa nu crezi ca o sa mai vrea cineva sa stea la discutii cand o sa stie ca ala micu de clasa 9-a poate sa ii ia locul la nationala. Fiecare pentru el! Asta o sa fie in gandul fiecaruia! O sa dispara pana si acele grupuri mici care inca mai sunt...

Similitudinile pe care le-ai facut cand te-ai inspirat pentru a scoate acesta regula nu sunt naturale. Hai sa tratam omul si nu boala !
Eu per sa vina cineva si cu alte propuneri….

Cat despre ACM. Eu cu siguranta sunt naiv insa stiu sigur ca daca nu exista nimic organizat rezultatele sunt haotice. Faptul ca am avut cateva calificari la finala ACM facute pe forte propri arata doua lucruri. Interes scazut in disciplinare si munca al studentilor ( cum rezolvi asta ? ) si faptul ca nu exista un cadru organizat ( la ucrainiei exista ).

S-au spus cateva lucruri interesante pana aici motive pentru care doresc sa adaug si eu cate ceva.
In primul rand se atinge tangential adevarata problema iar solutia propusa ( initial ) este total inadecvata. ( acesta este parerea mea si o sa subliniez de ce in urmatoare randuri ).

In primul rand juridic : Nu e normal sa faci reguli doar ca ca sa ataci pe cineva. Abordarea asta nu este nici sanatoasa. Sa fim realisti... Copii pleaca pentru ca de cele mai multe ori acesta este singura oportunitate pe care o ai sa ajungi undeva unde sa poti sa inveti mult mai mult. ( Nu este asta normal ?! Nu asta am vrea toti sa facem?  Ce ai alege tu intre a sta in localitatea ta la o facultate locala si a pleca intr-un centru universitar ?! Exemplele pot merge pana la " ce ar fi fost pt Romania daca ai fi ramas tu in Romania si lucrai aici si nu in state " ) Pe de alta parte, a trata o problema a sistemului de invatamant romanesc prin a pune piedici e total gresit. Problema este in alta parte ( centrele slabe, interes scazut in invatare/predare ). Astea sunt lucrurile pe care ar trebui sa ne preocupe.

In al doilea rand practic : Cum o sa pui in aplicare sistemul? Considerand ca se avem 5 copii si trebuie sa selectam doar 4, cum alegem? Dupa punctaj? Este etic? Statistic discutand punctajele la clasa 11 sunt unele mai slabe intr-o prima fata relativ la toate clasele... Vom selecta numai copii de clasa 9-a doar pentru ca acolo se reusesc mult mai usor puntaje mari? Alta abordare... lasam la indemana unor profesori sa selecteze... Dar care argument poate fi adus in favoarea selectiei unuia sau altuia. Pana acum singurul ( si cel natural ) era punctajul dintre concurentii de aces clasa ( care concurau ) cum o sa fie normal sa clasezi diferenta de pregatire dintre elevii care doresc sa mearga mai departe? Destul de dificil, nu mai spun ca o sa apar tot felul de imprejurari dubioase (favorizari) care o sa creeze multi elevi frustrati.
O alta problema : Cand eram eu in liceu era o bucurie sa mai gasesti inca o mana de oameni pasionati in acelas liceu de acelas lucru ca tine ( si chiar si in licee cu traditie in concursuri de informatica era greu sa dai de mai mult de 3-4 pasionati ). O astfel de solutie nu o sa faca decat sa produca o ruptura si mai mare facand ca toti elevii in loc sa faca share de informatii, sa discute sa se ascunda si sa fie intr-o continua competitie facand din ce in ce mai greu evolutia/pregatirea. E pur si simplu contraproductiv.

In final tin sa mentionez ca problema este reala. Un centru in care se aduna oamenii si se lucreaza nemaiavand timp sa studieze pe cont propriu nu e neaparat un lucru bun nici pentru cei care sunt acolo. Ceea ce spunea Mircea Pasoi legat de faptul ca astfel de centre sunt bune pentru varfuri si rele pentru restul e cum nu se poate mai adevarat. Se distruge creatia, dorinta si pasiunea transformandu-se in munca. Abordarea sanatoasa initiala era data de faptul ca fiecare avea ocazia sa studieze iar in intrunirile urmatoare ( concursuri/forum etc ) sa evolueze prin schimb de idei. Abordarea acesta e mult mai sanatoasa decat aceea in care ti se spune ce sa faci, cum ... si asta la fiecare pas. Practic este la fel de bun cat este si cel care te pregateste. Cu toate astea nu cred in solutia prezentata de Mircea. Sa nu ne ascundem dupa deget. Nu are rost sa vb despre schimb de informatie etc, cand noi ani de zile am avut probleme in a intelege ca este normal si nu e rau ca sa avem sursele publice la toate problemele pe infoarena. Imi amintesc si acum explicatii prin care se incerca sa se forteze binele prin tot felul de sanctiuni pentru o problema inventata si anume copierea surselor pentru ca unii se simteau amenintati mai apoi la urmatoarele competitii.

Elevi de clasa 9-a care sa fie mai buni decat cei de clasa 12 au mai fost si nu erau in liceul international ( ex. M. Patrascu ) .

Problema exista insa tin sa precizez ca ar trebui sa ne gandim la o solutie mai buna decat cea prezentata initial. Eu in continuare nu vad cum faptul ca lasand cativa copii buni acasa incurajezi informatica in alte centre. Judetele in care punctajele sunt ~0 tot ~0 o sa fie. Pe principiul "daca eu nu pot sa fac nimic sa fie mai bine atunci macar sa fie si altuia rau" nu ajungem niciunde. Se doreste stoparea plecarii catre un singur centru? Faceti alte centre mai puternice!( sau sa facem, nu ma dezic ) Asta ar trebui sa fie abordarea corecta...

Tin sa precizez inca un amanunt important. Legat de rezultatele nostre slabe la ACM. Nu inteleg de ce toata lumea ramane surprinsa. Ce inseamna in Romania acest concurs? Aproximativ nimic... Nu se fac pregatiri nu se face nimic... o mana de studenti se aduna si formeaza cateva echipe si apoi participa la etapa de SE Europei coordonati de un antrenor a carei singur atribut este faptul ca a selectat studentii dupa un test si care nu are nimic de-aface cu preatirea studentilor ( acestia sunt de fapt fosti elevi care in liceu participau la concursuri de informatica si care au o experienta destul de buna in domeniu ) . Nu poti sa pretinzi in felul asta rezultate. E absolut normal ! ( acesta este parerea mea ca urmare a experientei mele de student la Universitatea Bucuresti si tind sa cred ca lucrurile nu difera foarte mult in alte parti... dar poate s-au mai schimbat intre timp )

Un curs bunicel la nivel undergrad de statistica si probabilitati predat la Harvard: http://www.extension.harvard.edu/openlearning/math102/

Un curs bine structurat de algebra liniara predat la MIT:
http://ocw.mit.edu/courses/mathematics/18-06-linear-algebra-spring-2010/video-lectures/

[Later edit]

Nici macar cu parsare de mana nu trece de 95 de puncte.... dubios... (  tot depaseste timpul ) ...

Later edit Am redimensionat vectorul si a intrat...

Poate ar trebui pus un pic mai mare time-ul la acesta problema. Adica.. cu solutia O(N^2) se ia 95 de puncte. Iese din timp la testul 15. E destul de aiurea sa fiu nevoit sa parsez de mana ca sa iau 100 de puncte.

[Scuze... gresala mea... rezultatul era bun... nu interpretam eu bine rezultatul...]

Pe minue nu ma intereseaza sa schimb un semn... ca asta am vazut si eu( dupa cum am mai scris ) pe mine ma intereseaza sa imi dau seama unde este eroarea logica....

in ceea ce priveste linia respectiva... logic e corect:
operator< face: A X B > 0  => unghi(B) > unghi(A) => unghi(A) < unghi(B)  ( intoarcere la stanga... sens trigonometric ) si atunci este true ...

Scuze... gresala mea... rezultatul era bun... nu interpretam eu bine rezultatul...

De ce daca aplic sort() peste un vector de elemente de genul ( la care am implementat operatorul "<") :

Cod:

class vect {
public:
    float x,y;
    
    vect():x(0.0f),y(0.0f) {}
    
    vect(int X,int Y):x(X),y(Y) {}
    
    const int operator<(const vect& aux)  const{
        if(x * aux.y - y * aux.x  > 0.0f) return 1;
        if(x * aux.y - y * aux.x <=0.0f) return 0;
    }
    
    vect operator-(const vect& aux) const {
        return vect( x - aux.y , y - aux.x );
    }
};

mi le sorteaza descrescator ?
Conform specificatiei daca "<" este corecta trebuie sa intorc true (1). pentru: "a<b" vectorul din stanga este mai mic fata de cel din dreapta daca produsul lor vectorial este mai mare ca 0 ( adica am intoarcere la stanga in cercul trigonometric ).
In cazul asta de ce mi le sorteaza descrescator?(dupa unghi) Adica... e suficient sa schimb semnele si o sa fie crescator... dar de ce face asa?

Nu este obligatoriu sa faci cautarea unui punct de pe invelitoatea convexa si sa sortezi in jurul lui. Poti sa faci sortarea si relativ la un punct aleator ( ex.: ( 0 , 0 )  ) . Doar ca la sfarsitul scanarii mai trebuie facute niste verificari.

Despre ce inseamna algoritmi in general si importanta lor in industrie cred ca oricine are treaba cu acest domeniu are cel putin o idee ( de la "maimuta" la cercetator ). O prezentare interesanta ar merita si modul in care acestia pot fi implementati pentru a aduce maxim de performanta si de reutilizare. Cand zis asta nu ma refer cat de bine poate cineva implementa un flux... etc, ci mai degraba la probleme de design de software... In lumea reala un design bun poate face ( uneori ) mai mult decat o complexitate imbunatatita pe anumite subrutine. Ar trebui mentionat si acest fapt pentru viitorii pasionati ai domeniului.
De cele mai multe ori solutiile trebuie implementate in arhitecturi complexe si integrate cu alte arhitecturi iar modul in care interactioneaza poate scoate ( sau nu ) la suprafata calitatile/hibele noului algoritm.

Ex. E usor sa gandesti implementarea unui BSP ( binary space partition ) mai urat este sa te gandesti cum implementezi o arhitectura care sa inglobeze intr-un engine grafic acest arbore si sa se foloseasca la maxim acesta noua solutie de a randa partial elementele unei scene.
Ex. E usor sa realizezi cum desenezi o linie pe ecran... dar totul devine complex cand trebuie sa randezi o lume intreaga. Cum analizezi acesta problema? Cum organizezi codul pentru a face totul flexibil la modificari ?
Ex. Pare destul de logic cum parsam si interpretam un string pentru a evalua o expresie aritmetica insa daca discuti despre crearea unui compilator lucrurile se complica.
Ex. Cei care utilieaza OpenGL pentru grafica. Daca nu si-ar adapta algoritmii pentru state machine-ul arhitecturii acestui api nu ar reusi sa isi umbunatatesca perfomantele. ( chiar si modelul utlizat de openGL este unul ales astfel incat sa imbunatatesca performantele operatiilor grafice... )

Scuze pentru atatea exemple din grafica... defect de meserie

Exemplele pot continua

Care au fost medaliile? 3 de argint ?

te referi la segmente... cand zici "DA", etc... , da?

O confuzie tot mai des intalnita este asocierea dintre software engineering si capacitatea de a rezolva problemele de algoritmica. Un astfel de job necesita de cele mai multe ori multe alte cunostinte si nicidecum nu se limiteaza la o gandire algoritmica buna.
http://en.wikipedia.org/wiki/List_of_basic_software_engineering_topics