Am o nelamurire in privinta programarii dinamice. Eu de obicei rezolv problemele de dinamica gandind "unde pot sa ajung din pozitia data" nu " de unde pot sa ajung ".
Spre exemplu la problema suma in triunghi solutia e sa calculam bestul intr-un tablou t(i,j), unde solutia se va gasi in t[1][1] si  t(i,j)=max(t[i+1][stanga],t[i+1][dreapta])+a(i,j) (a(i,j) elementul din triunghi).
Ei bine eu gandesc in felul urmator,  t(i,j)=max(t[i-1][stanga],t[i-1][dreapta])+a(i,j) (cu limitele de rigoare pentru stanga si dreapta), si valorile se modifica daca se gaseste o solutie mai buna.
Solutia o gasesc iterand peste ultimul rand.
Stiu ca solutia mea are ceva pasi in plus, dar mi se pare mai intuitiva, adica efectiv "merge" in ordinea descrisa de problema adica de la varf la baza.
Am vazut ca mai exista probleme de dinamica care se rezolva doar cu metoda asta (de la oji, sudest de exemplu), dar acolo e putin mai altfel treaba.
Vroiam sa intreb daca e bun rationamentul meu si daca as putea avea probleme cu el, sau daca e un alt mod de a aborda o problema de dinamica (la dinamice din cate am vazut in functie de problema pot exista mai multe interpretari corecte).

Pai insemna ca nu iti afiseaza nimic, sau nu afiseaza ceva.
Poata nu ai pus limita bine la un vector, si eu am patit la fel.

Nu sunt sigur dar cred ca exista un caz pe care problema nu il trateaza si care ar face sa nu mai poata fi rezolvata cu dinamica, solutia official devenind ... gresita .
E posibil sa ajunga in aceeasi casuta cu o cantitate maxima din doua directii dar din una dintre directii cu mai putine comenzi efectuate astfel incat in final cea cu mai putine comenzi sa obtina o cantitate mai mare.
Ori in rezolvarea acceptata oficial in cazul in care am ajuns cu o anumita suma, aceea va ramane la fel chiar daca am ajuns cu 100 comenzi acolo, iar din alta directie am ajuns cu 20 de comenzi (caz in care e posibil sa avem un rezultat mai bun).
Mentionez din nou ca nu sunt sigur, dar mie asa mi se pare.

Am folosit peste tot short int, nu prea vad ce optimizari ar mai putea fi facute.
Culmea e ca am facut un vector unsigned char (m-am uitat peste valori sa fiu sigur ca nu e nevoie de mai mult) si desi ar fi trebuit ca vectorul sa ocupe jumatate din memoria initiala (vectorul avea intial 10000 de elemente, deci acu ar fi echivalentul a 5000 de elemente), la rezultate imi arata ca, consuma cu 10 kb mai mult, la penultimu test. Asta da paradox.

Nu poate nimeni da un indiciu in legatura cu memoria? ca vad ca majoritatea celor cu 95 de puncte, au facut o modificare mica in sursa si au trimis-o la cateva minute distanta, deci cred ca e ceva simplu ...
Am incercat sa fac vectorii sa ocupe mai putina memorie prin citirea fisierului de 2 ori si culmea imi ocupa mai mult spatiu la evaluare, chiar daca vectorii mei sunt mai mici (i-am testat ).
Pana si sursele oficiale iau MLE pe 2 teste. E ceva ciudat ...

Pana la urma cum e, trebuie ca toate nodurile sa aibe gradul par, sau pot exista fix 2 care au gradul impar :
A connected undirected graph is Eulerian if and only if every graph vertex has an even degree, or exactly two vertices have an odd degree.
Vad ca cele afirmatii se bat cap in cap ....

Nu inteleg deloc de ce nu merge testul 8. Algoritmul meu memoreaza in sol[ i ][ j ] - maximul  pana la (i,j) (desigur memorez undeva solutia ca sa fie pe lina si coloana potrivita). sol[ i ][ j ]=max(sol[ i-1 ][ j ],sol[ i ][ j-1 ],a[ i ][ j ]-sol[ i ][ j-1 ],a[ i ][ j ]-sol[ i-1 ][ j ]).
Teoretic ar trebui sa mearga perfect.
Ba chiar arata si greseala din exemplul lui domino (vad ca nu a mentionat nimeni, pentru primul test solutia e 3 2 4 nu 3 2 6).

De ce da rezultat gresit (80 de puncte) daca intializez direct vecinii nodului de start (calculez direct h[1][vecin x][vecin y]), dar daca intializez h[0][xi][yi] merge perfect (chiar daca se fac EXACT ACEIASI pasi).

Nu trebuia sa scrie aici " Daca b = 0, atunci a * 1 + b * 0....."  y=0 in loc de b=0?

Chiar asa eu inca nu am gasit alta solutie decat sa fac cu grafuri (defapt lee modificat). Exista vreo solutie mai simpla ? ca ma indoiesc ca se dadea asa ceva la clasa a IXa, adica ar inseamna ca ce se da acu e floare la ureche.

Pai algoritmul este destul de mare, dar nu prea se da asa ceva la concursuri eventual se da impartirea unui numar mare la un numar mic. Oricum alta varianta n-ai decat sa scrii toate functiile alea.

Cred ca cel mai bine era sa gasesti pe cineva care putea sa le scaneze si sa le posteze pe net inainte sa le dai ca in momentul de fata o mare parte din articole nu le poti downloada.

Iti dai seama cat de ineficient este acest lucru in back ? ma rog, tot iei niste puncte, eu unul daca faceam ce ai zis ma calificam la nationala, dar pentru 100 de puncte zic ca trebuie sa il optimizezi cat poti, chit ca e posibil sa gresesti ceva si sa iei 0 puncte 

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  .

Sunt mai multe probleme cu anumite evaluatoare. Spre exemplu am intalnit o problema in care foloseam un for cu i<=expresie, asa ca am memorat expresia intrun auxiliar ca sa nu repete calculul mereu; surpriza a fost ca timpul de executie este cu mult mai mic la varianta aparent mai rapida (desi daca ma gandesc bine compilatorul ar trebui sa realizeze ca se repeta calculul si sa optimizeze asta, sau poate ca nu  ....). Ma rog asta mi se intampla in mingw, dar banuiesc ca la fel ar fi si daca ar fi o problema de olimpiada evaluata cu evaluator oficial pentru ca tot la fel a fost compilata sursa.

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 ?

La ce concurs te referi? La cel de la Campulung? Are si faza nationala   . Eu nu stiu prea multe detalii abia astazi am aflat de el si i-am spus lu' profu' sa ma inscrie.

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 ?

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 .

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   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 )

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  ....

- 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.

Da asa e l-am uitat pe 2  . Stiam ca eu am gresit dar chiar nu inteleg cum de am putut rata nodul ala.
Multumesc mult pentru raspuns

Eu nu inteleg de ce in raspuns este valoarea 11, nu trebuia sa fie 10 ?

-devilkind, vad ca nu prea ai inteles deloc bine; daca imi uram tara si vroiam sa plec, nici nu mai intrebam (defapt totusi nu pot spune ca o iubesc prea mult ca in majoritatea privintelor nici nu se apropie de tarile mai dezvoltate economic, dar nici nu mi se pare foarte rau); chiar nu vreau sa plec, de asta am intrebat daca se merita sau nu, ca sa stiu daca am un motiv destul de intemeiat sa plec.

-cosmin : multumesc pentru raspunsuri, ai dreptate in multe priviri; acu nu stiu ce sa zic ca ma pot angaja la google sau microsoft ca asta inseamna sa concurez cu cei mai buni informaticieni,olimpici internationalo din lume, ceea ce e totusi destul de greu, nu ma vad la un asemenea nivel, dar consider ca ai vrut sa spui ca indiferent de facultate daca sunt bun o sa ma pot angaja oriunde (desi probabil as avea mai multe sanse cu o facultate de top).

Cortizo-  am prea multe de spus si mie greu sa scriu si sa modific atat,adica nu stau sa fac o compunere, daca am vorbi fata in fata ar fi mult mai usor;
Pe mine ma intereseaza mai mult avantajele dupa facutlate, adica slujba , locuinta s.a. Ca despre studii stiu destule, am un fost coleg la manchester (cred ca pe undeva pe locul 30 in lume ca universitate) care se plange ca e prea usor, abia au facut ceva materie de clasa a 6a si acu au ajuns la logaritmi la sectiunea de computer science; la fel din cate am auzit si pe la MIT e cam la fel; nu ma pot plange ca mie imi place ca nu te iau cu cine stie ce chestii, si tinand cont ca faci doar ce-ti trebuie nu pot avea decat cuvinte de lauda, dar eu pot trece bine mersi si prin automatica, si sa ies cu aceleasi cunostine (ca ce imi baga pe gat oricum uit); deci pe langa conditiile super de viata si modalitatea de predare, m-ar interesa .... cu ce ma aleg dupa terminarea universitatii, tinand cont ca probabil n-o sa ma mai intorc vreodata in tara, si o sa am un loc de munce in tara unde am terminat universitatea sau in orice caz, in strainatate. Acum , imi dau seama ca nu prea are cine sa-mi raspund ca majoritatea de pe forum nici nu studiaza sau nici n-au studiat in strainatate, iar unii care au studiat, sunt doctoranzi in informatica sau ce o fi, adica sunt preocupati de cercetare (eu vreau doar sa fiu programator, nu sa inventez algoritmi super avansati).
p.s.: scuze din nou pentru exprimarea de cacao

Gata, am reusit  . Multumesc mult de raspuns !

Stie cineva daca sunt afisate pe undeva rezolvarile subiectelor de la campion, ca nici macar nu am cu cine discuta in legatura cu rezolvarea lor (nu fara sa intreb la aproape fiecare problema cate ceva).