Depinde de problema: daca ai sursa unica, poti folosi Dijkstra (cu heap-uri) sau Bellman-Ford (cu coada). Eu il prefer, in general, pe al doilea, pentru simplitate, cu toate ca primul se comporta, teoretic, mai bine.
Daca te intereseaza drumuri minime intre toate perechile de varfuri, folosesti Floyd-Warshall (sau Roy-Floyd, cum mai este numit).

Problema drumurilor minime este foarte bine tratata in CLR, o carte de care vei avea nevoie, daca te hotarasti sa incepi studiul serios

Iti sugerez, totusi, sa te documentezi putin mai mult inainte de a pune o astfel de intrebare pe forum, sunt pe internet suficiente surse de informare, in care vei gasi pe larg explicatii asupra algoritmului, poate mai complete sau mai usor de inteles decat iti va putea da cineva aici (eforturile lui Bogdan sunt cu adevarat de apreciat  un + de la mine). Abia dupa ce te vei convinge singur "cu ce se mananca" e indicat sa ceri sfaturi legate de anumite particularitati sau aplicatii.

In general, poti testa sursele pe site - daca iti compileaza aici, vor compila cu siguranta si la ONI. Spre exemplu, arborii de intervale ii poti testa in arhiva educationala, aici

Exemplul tau, de exemplu, compileaza cu warning-uri referitoare la fisierele header, care sunt considerate "deprecated". Foloseste in schimb

Cod:

#include <iostream>

Un automat finit poate fi folosit si pentru string matching. Odata construit automatul pentru un anumit pattern, toate aparitiile acestui pattern intr-un sir pot fi gasite in timp proportional cu lungimea sirului - complexitate O(N).

Nu stiu exact cum este implementat intern strcmp, insa banuiesc ca nu are la baza un algoritm liniar, prin urmare pentru siruri si patternuri de lungimi mari nu se va comporta la fel de bine ca un algoritm performant de potrivire, cum ar fi KMP (Knuth-Morris-Pratt), Rabin-Karp sau Boyer-Moore.

Termenul se refera la automate finite (finite automata). Pentru detalii vezi articolul lui Adrian Vladu de aici si prezentarea introductiva de aici.

Cat despre algoritmii de simplificare sau echivalenta, poti gasi cateva paper-uri pe net, insa cred ca sunt destul de avansati pentru inceputuri. Sunt multe altele de invatat pana la automate finite 

[iN]

Aha , am inteles, multumesc, dar cum ramane cu cel mai scurt subsir crescator maximal , asta ce inseamna?

Pe scurt, un subsir crescator este maximal daca nu mai poate fi extins. Trebuie sa determini cel mai scurt astfel de subsir. Un exemplu concludent este cel dat de Marius acum cateva posturi:

Cod:

subsir2.in 
12
19 17 -14 17 -6 21 19 8 -17 19 15 -22 

subsir2.out 
1
12

Aici, subsirul format de al doisprezecelea element (-22) este maximal (nu mai poate fi extins) si este cel mai scurt.

In alta ordine de idei, cred ca ar trebui modificati doi indici in restrictiile problemei, mai exact acolo unde apare B=(bi1,bi2...biN) modificat in B=(bi1,bi2...biK) 

testul 8 il pic si mam uitat pe cel de la oji am o mica scapare, dar nu stiu ce ar putea fi

any help?

here is the source: http://infoarena.ro/job_detail/181255?action=view-source

Fii atent cand faci update la matrice: la un anumit pas, poti updata si elemente care au valoarea mai mare decat zero, daca distanta gasita pana atunci este mai mare decat pas+1. Pentru a rezolva asta, trebuie sa mai adaugi o conditie in if:

Cod:

if (a[i-1][j]==0 && (r[i-1][j]==0 || r[i-1][j]>pas+1) && i-1<=n && i-1>=1)

Sau poti initializa toate elementele cu o valoare foarte mare si apoi modifica if-urile astfel:

Cod:

if (a[i-1][j]==0 && r[i-1][j]>pas+1 && i-1<=n && i-1>=1)

Am citit din postul de pe forumul TopCoder cum s-ar rezolva dinamic subproblema determinarii unei secvente de suma maxima cu minim A elemente. Este vreo metoda de a rezolva tot dinamic si restrictia ca lungimea secventei este <= B?

Cu un deque, in care pastrezi ultimele B elemente (sau cate ai nevoie, dupa caz).

Citisem solutia oficiala si articolul despre automate finite. Am inteles cum se poate construi un automat finit care accepta un cuvant, dar, din cate inteleg din solutie, trebuie construit un automat care accepta mai multe cuvinte, iar starilor de acceptare le voi asocia apoi valorile "strigatului" (nu pot construi un automat avand ca stari cele 100 * 1000 valori posibile pentru strigat...). Dupa asta, dinamica e evidenta.
Insa, asa cum am spus, ramane de construit automatul pentru cele M cuvinte. 

LE: Cred ca m-am prins cum se face: pot lua ca stari toate prefixele cuvintelor, prefixele comune aparand o singura data. Astfel am maxim LTot stari, unde LTot este lungimea totala a cuvintelor. Constructia automatului se poate face astfel in O( LTot*|sigma| )

LE2: ...sau nu 

Cum se poate construi un automat finit determinist care accepta mai multe (N) cuvinte?
Adica... nu imi dau seama care sunt starile lui 

La ce te referi cand spui ca poti calcula suma distantelor pana la nodurile care nu sunt in subarbore "on the fly"?
Eu am rezolvat problema cu doua parcurgeri DF, una ca sa determin suma distantelor pana la nodurile din subarbore, iar a doua pentru a determina (pe baza informatiilor de la primul DF) cealalta suma; problema e ca imi iese din timp pe un test.
Se poate face cu o singura parcurgere a arborelui? 

Am o intrebare: cum poate fi folosit template-ul "scrie-articole" pentru a adauga mai multi utilizatori? Ma refer la

Cod:

== include(page="template/implica-te/scrie-articole" user_id="nume_user") ==

Si aici, cum banuiesc ca a fost sau va fi situatia mai multor articole, contributii importante de redactare sau continut au venit din partea mai multor persoane. In particular, este cazul lui Marius, care a ajutat mult la cea de-a doua parte, si merita din plin mentionat

Daca nu poate fi folosit astfel, atunci poate il putem modifica (nu cred ca e atat de dificil - eu nu stiu totusi de unde se pot edita template-urile) pentru "multi-user support" 

Multumesc mult Figurile le-am facut in in Photoshop.
Oricum, continutul articolelor este cu mult mai important, si cred ca trebuie sa multumim cu totii lui Cosmin si lui Adrian pentru asta.
Keep up the good work!

Imi cer scuze pentru mult prea marea intarziere; am reusit, in sfarsit, sa definitivez redactarea, si multumesc mult lui Marius si lui Stefan pentru contributiile importante la continut 

Am adaugat un link in pagina de articole si am trecut proiectul drept finalizat pe http://infoarena.ro/implica-te/scrie-articole

fgets pune in stringul citit si ultimul caracter '\n' , poate de asta.

...Chiar daca intrebarea e de mai bine de 2 ani, poate raspunsul va ajuta pe altcineva cu aceeasi problema

Ma ofer eu sa transcriu articolul. E in regula?

Am folosit map din C++ si am luat 2 TLE ... Cum ati implementat hashul ?

Map din STL este de fapt un arbore rosu-negru, deci update si query logaritmic. Foloseste un hash "home-brewed"

Pai implementezi o rezolvare brute-force (care sigur te conduce la solutia corecta) si faci si un generator de teste. Pentru fiecare test, compari rezultatul obtinut prin brute-force cu rezultatul programului pe care vrei sa il verifici (poti face si un script bash care face chestia asta de 100 de ori, adica genereaza cate un test, ruleaza brute-ul, ruleaza programul tau si compara rezultatele).

Si eu am facut-o in O(n) si am luat 100 din prima deci sigur e greseala de implementare la rmikeweb...nu stiu daca merge pe toate testele insa am facut-o exact ca pe Secventa2 +verficarea cu limita superioara mutand startul cu unu daca nr de el din secventa este mai mare decat maximul de el din care poate fi alc secventa recalculand valoarea cu startul mutat(in O(1) calculez suma de la x la y deci am preprocesat),chestie care nu trebuia facuta la Secventa2(unde se verifica doar limita inferioara).Ori sunt testele prost alese ori e chiar buna solutia...insa eu mizez pe a doua optiune!!! 

Eu mizez pe prima
Din cate am inteles, tu nu iei in vedere decat secventele de lungime exact U... 

imi explica si mie cineva.. ca unui nestiutor.. cum se face un brut force ?

Pur si simplu verifici toate secventele posibile

Aham.. Ms mult

E corect, dar te complici prea mult in calculul cmmdc. Poti face, de ex:

Cod:

int cmmdc( int a, int b ) {
	int r;
	while( b ) {
		r = a % b;
		a = b;
		b = r;
	}
	return a;
}

Din cate tin minte, ca sa iei 100 trebuie lucrat cu intregi pe 64 de biti.

Care e diferenta dintre "Bine, Ionel!" si "Ok... pentru moment". Adica primesc 10p in amandoua cazurile, insa as vrea sa stiu daca s-ar putea mai bine (nu gasesc stop-ul minim, sau secventa cea mai scurta etc..)

Acum imi dau seama ca nu (cred ca) se poate aplica algoritmul in n log n pentru cel mai lung subsir crescator la problem asta, deoarece nu exista relatie de ordine totala pe multimea punctelor din plan (o astfel de relatie ar fi echivalenta cu o relatie de ordine pe multimea numerelor complexe...). Asadar, nu se poate face cautarea binara din algoritmul in n log n... curaj cu AIB

  Exista vreo functie care returneaza in O(1) nr de biti de 1 ai unui nr ?

Numarul de biti de 1 se numeste Hamming weight. Il poti calcula in O(log N), cu o masca pe biti, sau cu niste formule dubioase in timp (aproape ) O(1). Vezi http://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation

Da, am parsat citirea si a intrat lejer in timp.
Cu toate astea, o mica obiectie pt problema: limitele de timp ar trebui puse, dupa parerea mea, in asa fel incat un algoritm de complexitate optima sa poata lua max fara sa fie nevoie de citiri "dubioase" .
Pareri?