Poti sa faci Dijkstra cu heapuri sau cu un arbore de intervale. atunci iti va intra in timp.
mai poti sa faci si Bellman Ford cu coada. Despre
Dijkstra gasesti aici http://infoarena.ro/problema/dijkstra (unde poti sa te uiti la sursele celorlati concurenti, de exemplu pe cea a lui Filip: http://infoarena.ro/job_detail/153886?action=view-source).

Dijkstra cu heapuri suna cam asa:
vei tine un heap H in care vei avea distantele de la sursa la fiecare nod calculat pana la pasul curent (atentie, relatia de ordine trebuie sa fie key(A)<=key(B), pentru ca in varf sa ai minimul dintre toate elementele). cand vrei sa alegi minimul dintre distante nu trebuie decat sa iei nodul care se afla in varful heapului. cand reactualizezi distanta pentru un nod j, il scoti din heap si il reintroduci cu noua distanta. 

daniel, parerea mea este ca atunci cand vrei sa initializezi un vector cu o valoare, sa faci cu for. este o metoda sigura si clara. nu o sa conteze prea tare (la timp ma refer) daca faci cu memset, int A[]={0}, sau cu for. in cel mai rau caz (daca esti fff ghinionist) o sa-ti iasa din timp maxim un test, din cauza initializarii unui vector. 

foloseste long double (daca nici atunci nu merge, compileaza cu g++. si eu am avut probleme cu precizia pt gcc - nu la problema aceast, dar in general)

tot nu e bine. am zis ca in if-ul:

Cod:

if(v[j]>=v[i] && v[j]<min)

reactualizezi doar minimul.

trebuie sa fie ceva de genul

Cod:

if (V[j] >= V[i] && V[j] < min)
{
        min = V[j];
        if (l[i] > l[j]+1)
        {
              l[i] = l[j]+1;
              p[i] = j;
        }
}

de ce nu faci un debug pe un test care nu-ti merge. vezi la ce i nu iti da cum ar trebui.

poate multa lume se duce mai intai sa dea proba si apoi sa iasa le bere 
de obicei te orientezi la fata locului. daca iti spune cinvea un local si tie nu-ti place?

nu cred ca e buna conditia asta

Cod:

 if(v[j]>=v[i] && l[j]<l[i] && v[j]<min) 

scoate l[ j ] < l[ i ]. daca se indeplineste conditia (fara l), reactualizei min si apoi vezi daca solutia curenta iti imbunatasete solutia calculata anterior, adica:

Cod:

if (l[j]+1 < l[i]) {
l[i] = l[j]+1;
p[i] = j; }

ai grija ca in caz de egalitate reactualizezi p[ i ] cu minimul dintre val lui si j.

limita este pusa corect. evaluatorul arata timpul la care ti-a omorat programul si probabil afiseaza un pic mai putin. s-au luat 100 de puncte si cu 134ms: http://infoarena.ro/job_detail/13486
incearca sa trimiti sursa asta si o sa te convingi:

Cod:

#include <stdio.h>

int main()
{
	while(1);
	return 0;
}

varule, ca sa ii pice tot programul trebuie sa ii pice ambele functii. Din ce am inteles eu a aplicat 2 greedyuri si ia solutia cea mai convenabila dintre cele 2. O abordare destul de buna uneori poate chiar mai bine decat sa bagi solutia oficiala si sa o busesti

adevarat varule, dar pe al doilea test nu intra in comp1().

[...]
Functia compl1() cauta doua randuri consecutive libere (complet).
[...]

daca am inteles bine ce face comp1(), atunci ar trebui sa pice testul (patratele marcate cu 1 sunt patratele blocate):
0000            22222
0000    =>    22222
1100            1122
1100            1122

oricum, daca pe ala nu pica prima functie, sigur pe testul asta pica comp2(), deci iti pica tot programul:

10001              10221
00001              22221
00001     =>     22111
00001              00221
10001              10221
                                             

da. daca tot te chinui sa iti mearga, de ce sa nu profiti si de avantajele pe care ti le ofera gnu? 

Nodurile presupun ca au voie sa se repete

si eu am presupus acelasi lucru 

aprilish, bolundish, mamaliga cu macrish. 

Poti rezolva problema prin programare dinamica:
D[ i ][ j ] = distanta minima de la nodul de start panala nodul i trecand prin exact j noduri. Initial D[ sursa ][1] = 0, iar pentru o stare (i,j) deja calculata vei trece intr-o stare (i',j+1) unde i' este un vecin al lui i.

probabil nu ai citit atent enuntul:

Daca a si b sunt numere prime intre ele, atunci se va tipari 0.

 

Unguru Bulan

http://www.youtube.com/watch?v=ZWcGRDjfxps&feature=related
http://www.youtube.com/watch?v=A5A-FKvVqjE&feature=related
http://www.youtube.com/watch?v=JH5RESLlIGs&feature=related
http://www.youtube.com/watch?v=dyjkgrNDqro&feature=related
http://www.youtube.com/watch?v=JA1YwJmAnAU&feature=related
http://www.youtube.com/watch?v=MY9onB3AVeU&feature=related
http://www.youtube.com/watch?v=qFnypWeCfsw&feature=related
http://www.youtube.com/watch?v=5zTQrW6eMDo&feature=related

initializeaza variabilele/vectorii in care retii minimele cu 2 000 000 000.

sund sold out nu cred ca mai suplimenteaza, mai sunt bilete doar la sectoarele de langa peluza. dai 2 mil sa vezi nimic 

Nu si-a luat nimeni bilet? 

Algoritmul lui Dijkstra este un algoritm de tip greedy. In randurile de mai jos D[ i ] reprezinta distanta de la nodul sursa (S), iar C[ i ][ j ] = costul muchiei (i,j).

Initial D[ i ] = INF (pt i dif de S) .
pasul 1: cautam nodul i pentru care D[ i ] este minim.
pasul 2: parcurgem toti vecinii lui i si reactualizam distanta pentru un vecin j, daca D[ j ] este mai mare decat            D[ i ]+C[ i ][ j ]. reluam de la pasul 1.

pasul 1 se poate face in O(n) (parcurgand vectorul D si luand minimul), iar complexitatea finala va fi  O(N*N+M). Daca vrei sa faci acest pas mai repede, de fiecare data cand reactualizezi distanta pentru un vecin o introduci intr-un heap (in O(log N)) si vei face pasul 1 in O(1), iar complexitatea finala va fi O(NlogN + M).

(prin log x se intelege log2 x)

Iti sugerez sa citest ceea ce am zis mai sus uitandu-te, in paralel, pe sursa lui Filip: http://infoarena.ro/job_detail/153886?action=view-source

[3]

Spunem ca un subsir B=(bi1,bi2...biN) este crescator maximal daca ai1 ≤ ai2 ≤ ... ≤ aiK si nu exista nici un x astfel incat: sa existe j < K, ij < x < ij+1 si aij ≤ ax ≤ aij+1, sau 1 ≤ x < i1 si ax ≤ ai1 sau iK < x ≤ N si aiK <= a

pentru exemplul lui wefgef:
8 6 3 9 10 3 2 5 1 3 7 5 2 8 4 10.

subsiruri crescatoare care nu sunt maximale sunt
8 6 3 9 10 3 2 5 1 3 7 5 2 8 4 10 (se mai poate extinde cu 9 si cu ultimul 10)
8 6 3 9 10 3 2 5 1 3 7 5 2 8 4 10 (se mai poate extinde cu ultimul 10)
8 6 3 9 10 3 2 5 1 3 7 5 2 8 4 10 (se mai poate extinde cu 7, 8, 10, sau cu 5, 8, 10).

daca din exemplele de mai sus consideram intr-o secventa si numerele boldite si numerele subliniate, vei avea subsiruri crescatoare maximale.

http://youtube.com/watch?v=S1BU1z9JiGM&feature=related
http://youtube.com/watch?v=n3Mm67EqrYI&feature=related 

dupa ce ai citit articolele de pe TC, poti sa te uiti peste problemele de geometrie aduna de Cosmin Negruseri (http://infoarena.ro/implica-te/scrie-articole)

ai citit articolul cu solutii?
eu am luat 100 folosind Bellman Ford cu coada.

problema s-a dat la OJI in 2004. arhiva o gasesti aici.

daaaaa