Probabil aceasta va fi catalogata drept dumb question dar voi intreba totusi : prin probleme de divizia 2 se intelege orice problema ce are division 2 level 1,2, sau 3 ?

Pai foarte bine s-ar putea micsora si limita de timp la 0.05 si s-ar putea ca solutia ta sa nu mai intre in timp .

Viteza sportivului se modifica uniform stau instantaneu ? Cu alte cuvinte vitreza este o functie continua ?

Ar trebui putin marita limita de memorie a acestei probleme .. eu am o solutie cu trie si aib , fac query pe aib ca sa aflu cate cifre are al k-lea nr din trie la momentul curent , si ia mle pe 5 teste . Daca lista de fii ptr fiecare nod din trie in mod dinamic , ia mle pe un test si tle pe 2 teste . Solutia cu lista de fii alocata static merge f bine ca timp . Rog un admin sa se uite putin peste limitele problemei . Multumesc anticipat .

Da , la asta ma refeream ... off speram sa fie de la asta . Iau wa pe 4 teste x( . Daca poate cineva sa-mi sugereze un test mai .. "special" as fi recunoscator ... Deci am tot incercat sa vad ce ar fi gresit in algoritmul meu si nu inteleg . Fac o parcurgere df si numerotez nodurile in ordinea in care au fost atinse in parcurgere . Sortez nodurile dupa aceasta valoare si elimin orikre pereche de 3 muchii de tip i - tata[ i ] , j-tata[j] , k-tata[k] astfel inkt dfn[ i ] < dfn[j] < dfn[k] . Am pus aceasta conditie pentru a calcula mai usor suma costurilor nodurilor din fiecare district , deoarece daca aveam 2 noduri pe acelasi lant si eliminam prima data nodul de pe un nivel mai jos atunci cand eliminam un nod de deasupra lui ar fi trebuit sa scad si valoarea nodului eliminat anterior . Oricum am facut calculul si metoda mea elimina oricare pereche de 3 muchii din arbore . Astept orice idee ...

populatiile oraselor sunt date in ordine nu ?

Ai dreptate . Solutia este eronata . Imi cer scuze ca nu m-am gandit mai mult ... a fost la repezeala si nu mi-am dat seama ca mai mereu in matrice ar exista un ciclu de cost pozitiv ( care ar imbunatati intr-una costul maxim al unui drum ) .

In cazul in care nu poti trece de 2 ori prin aceeasi celula din matrice ai urmatoarea solutie fara backtracking :
Folosesti algoritmul lui dijkstra , o stare fiind definita de ( i , j , cost ) ea reprezentand costul maxim al unui drum de la celula linieStart,coloanaStart la celula i,j . Evident vei modifica algoritmul pentru a-ti obtine costul maxim .

Baza de date este una mica , merge perfect pe sqlite . Va multumesc la toti 3 pentru raspunsuri .

O intrebare legata de baze de date gestionate in c# , cu ajutorul sql server. Se poate ca pe un calculator fara sql server sa fie accesata baza de date fara conectarea prin internet la un alt calculator ce are sql server , sau este necesar ca pe orice calculator pe care vreau sa rulez programul sa instalez sql server ?

Va multumesc la toti 3 pentru raspunsurile voastre . Am inteles acum de ce merge corect ideea de a baga toate terenurile in coada de la inceput .

Pai asta nu ar fi similar cu a face lee din fiecare teren acoperit cu apa ? Sau le introduc in coada pe toate din prima ? Daca le introduc din prima in coada pe toate nu ar trebui sa vizitez fiecare celula din matrice kte odata pt fiekre punct din coada ca sa asigur optimalitatea distantelor sau distanta ramane optima si daca vizitez fiecare patrat doar pentru primul drum care il contine ?

Daca se poate face N * M cu lee va rog frumos lasati-mi un hint ... Eu am facut 100 cu o dinamica dar fol 20mb memorie pe testul maxim . Multumesc anticipat .

Complexitatea ceruta e O(N * M) ?

You're the best . Mult succes in finala !!!

Am si eu 2 intrebari . Faptul ca ai terminat x facultate de prestigiu are vreo relevanta in obtinerea unui interviu ? Pentru cineva care doreste sa lucreze ca programator conteaza daca a terminat automatica sau informatica , sau doar skillul in programare?

Enuntul problemei se poate gasi aici http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1233.

Rezolvarea mea obtine 90 de puncte, iau wa pe testul maxim. Ideea de rezolvare se bazeaza pe cea prezentata in cartea "Psihologia concursurilor de informatica ".

Folosesc 2 matrici alocate dinamic Q si D cu urmatoarea semnificatie:

Cod:

D[i][j] = diferenta minima care se poate obtine cu un subsir de lungime maxima terminat in Q[i][j] 

In continuare voi detalia constructia matricii Q. Pe linia 0 din matricea Q construiesc exact vectorul explicat in cartea mentionata, iar pe fiecare coloana retin numerele suprascrise in ordinea suprascrierii lor, inclusiv numarul curent, numerele de pe fiecare coloana a matricei fiind sortate in mod descrescator .

Cand suprascriu elementul Q[0][ i] cu un alt element, caut pe coloana i-1 pozitia pe care se gaseste cel mai mare element mai mic sau egal cu Q[0][ i] . Notez aceasta pozitie cu x iar pozitia pe care o ocupa elementul Q[0][ i] in coloana i a matricei cu y.

Folosesc urmatoarea relatie de recurenta

Cod:

D[y][i] = min(max(Q[0][i] - Q[j][i -1],D[j][i -1]) ), x <= j <= numarul d elemente de pe colaona i-1 a matricii Q; 

Dupa cum este mentionat in carte, lungimea celui mai lung subsir comun este chiar numarul de elemente al vectorului Q, iar in cazul meu diferenta minima este
min (D[lungimeSir][ i]), 1 < = i <= numar de elemente pe coloana lungimeSir.

Astept orice sugestie / orice contraexemplu si sper ca va fi utila/util. Multumesc anticipat .

Stie cineva cand se calculeaza numarul de  locuri ale fiecarui judet  pentru ONI 2012?

Exista o mica eroare de scriere la explicatia exemplului . Este scris "suma vibilitatilor" .

De fiecare data cand inclus fstream sau vreun header stl in mingw nu mai pot face debug . De exemplu cu fstream cand trec peste vreo functie legata de afisaj / siruri d caractere / alocare dinamica imi deschidere headerul fstream mai apas f11 o data si imi inchide debugerul  . Cu stl patesc lucruri asemanatoare cand trec peste functiile ce sunt scrise in headerele din stl . As dori sa stiu daca alte persoane patesc la fel , si eventual sa-mi dea cineva niste solutii daca acestea exista . Multumesc anticipat .

Multumesc de raspuns !

Problema poate avea si mai multe solutii ? Pe testul din exemplu mie imi da 6 3 1 3 2 si eu cred ca e corect deoarece daca sparg felinarul 2 din intersectia 2 strada 1,2 nu mai este complet luminata .

Multumesc pentru raspuns si imi cer scuze pentru offtopic dar in topicul problemei respective era inactiv din 2008 si m-am gandit ca nu imi va raspunde nimeni . Mai am o intrebare ... o voi adresa tot in acest topic deoarece nu este neaparat legata d vreo problema anume . Am un sir d elemente si ma intereseaza maximul pe un interval la fiecare moment . Daca ar trebui sa sterg al 3-lea si al 4-lea element si as pune -infinit in locul lor apoi as interoga pentru intervalul [3,4] nu mi-ar -infinit ? Sau ar trebui sa consider ca pozitiile respective din sir devin inaccesibile ?

Poate cineva sa-mi explice cum se face update-ul cand se sterge un element dintr-un interval ? M-am izbit de acest lucru la problema zeap . Nu am gasit alta solutie decat a decala toate elementele spre stanga ...

Daca poate cineva as dori sa-mi dea  un test mai dificil ( nu ma refer la cele oficiale ) deoarece nu imi dau seama ce gresesc. Determin numarul minim de culori din prima colorare care mi-o da backtrackingul si apoi generez toate colorarile cu numarul de culori mergand doar pana la cel determinat prin metoda mentionata . Pe toate testele kre le-am dat .. imi merge.