Probabil ca scapi din vedere anumite cazuri. Solutia oficiala studiaza toate situatiile posibile de joc si este descrisa aici.

Ca sa iei in calcul toate subsecventele, trebuie sa studiezi toate prefixele tuturor sufixelor. Sunt totusi subsecvente comune, pe care nu trebuie sa le numeri de doua ori, iar acestea apar ca prefixe comune ale sufixelor consecutive.

Lungimea prefixelor comune dintre sufixele consecutive (consecutive in lista de sufixe sortate) le tii intr-un tabel lcp[], pe care il poti construi in paralele cu sortarea sufixelor (vezi in articol).

De obicei compilatoarele expandeaza inline functiile simple (de genul swap) in etapa de optimizare. De asta s-ar putea ca in unele cazuri sa nu faca diferenta daca specifici in mod explicit acest lucru. In general poti lasa compilatorul sa decida care functii vor fi expandate si care nu, se descurca destul de bine

Ca tot veni vorba de swap, ca sa schimbi valorile a doua int-uri poti scrie (in C)

Cod:

a^=b^=a^=b;

Incearca si vezi de ce functioneaza (a^=b inseamna a = a xor b, iar expresia de mai sus este parsata de la dreapta spre stanga)

Vad ca solutia cu AIB-uri pentru maxime pe intervale, de complexitate teoretica O(log² N) pe update si query, se comporta mai bine in practica decat cea cu arbori de intervale (cu O(log N) pe fiecare operatie). Cel putin in implementarile mele

Iteratorii sunt un fel de pointeri, cu care poti parcurge un container (de exemplu un vector).
Iti recomand cartea "STL Tutorial and Reference Guide", de Musser, Derge si Saini - dupa bucata introductiva iti vei forma o parere destul de clara asupra STL-ului, iar acesta va fi un pas mare inainte

Daca nu gasesti in alta parte, am uploadat-o aici.

  Sunt mai rapide streamurile decat ma asteptam... Eu am luat mai demult, pe aceeasi idee, 90 cu citire standard. La ONI se va folosi tot g++ 4.2?

LE: Nop, citat de pe site-ul oficial:

5. Linux    g++ 3.2.2    compilator pentru limbajul C++

M-am uitat inca o data peste sursa ta si am vazut ca tu tii o coada de structuri cu nodul si distanta pana la el. Am impresia ca aici complici lucrurile; eu propun urmatoarea varianta: tii un vector dist[ x ] in care retii distanta minima (pana in prezent) pana la nodul x, iar in coada bagi numai indicii nodurilor, nu si distantele. Din nou, bagi un nod in coada numai daca nu este deja acolo.

Asadar, transformarile intr-un pseudo-C ar arata cam asa:

Cod:

coada.push( 1 );
incoada[1] = 1;

while( !coada.empty() ) {
	u = coada.pop(), incoada[u] = 0;
	for( v vecin al lui u )
		if( dist[v] > dist[u] + cost(u,v) ) {
			dist[v] = dist[u] + cost(u,v);
			if( incoada[v] == 0 )
				incoada[v] = 1, coada.push(v);
		}
}

In principiu, bagi un nod in coada numai daca nu este deja acolo. Vad ca tu bagi un nod in coada la fiecare relaxare.
Nu stiu daca WA e de la asta, dar.. pune si conditia asta prin sursa

Poate ca ar trebui sa citesti o parte din discutiile de pe acest thread. Cu siguranta iti vei forma o idee destul de clara asupra algoritmului...

?: este un operator ternar, iar expresia a?b:c intoarce valoarea b daca a este true (sau diferit de 0), altfel intoarce valoarea c.
Spre exemplu:

Cod:

int x = ( 2<3 ) ? 1 : 0;

va pune in x valoarea 1, pentru ca 2<3
Un exemplu mai practic este

Cod:

int MIN( int x, int y ) {
	return x<y ? x : y;
}

Aceasta functie returneaza minimul dintre x si y.

Am editat postul precedent. Cred ca Tiberiu are dreptate, e mai frumos cand gasesti singur o astfel de demonstratie - tin minte ca si eu eram extrem de fericit in momentul respectiv

demonstratia nu prea cred ca o stie nimeni fara sa aiba cartea respectiva.

Pentru cine cunoaste ceva din teoria Sprague-Grundy (are Cosmin un articol bun pe tema asta), o demonstratie simpla si eleganta se poate deduce de aici [...]

Ar merge o intreaga clasa de astfel de probleme, pentru care sa nu existe solutie polinomiala sau solutie exponentiala care s-ar incadra in timp, iar punctarea sa se faca in functie de cea mai buna solutie valida pana la momentul respectiv (care ar lua 100p), restul surselor primind puncte in funtie de o anumita distributie (de exemplu Gaussiana).

Cred ca este totusi destula munca pentru implementarea unei astfel de functionalitati; poate in infoarena 3.0 vom avea si "arhiva de bulaneli", plasata cu o eticheta mai formala sub arhiva de probleme si arhiva educationala

Asta numai el iti poate spune

In sursa din al doilea link, era recomandabil, spre exemplu, ca in loc de

Cod:

#include <string.h>

sa fie folosit

Cod:

#include <cstring>

Cred ca acum intelegi la ce ma refer...

...sau niste random-uri inteligente, in sistem Ciucu 

Mie nu mi se pare deloc alt limbaj. In esenta, modificarile apar asupra primelor directive #include.
Adica trebuie sa modifici doar numele librariilor (dupa regulile pe care le-am precizat in postul trecut), si sa lucrezi in namespace-ul std; astfel nu vei avea niciun fel de problema, limbajul in sine si toate functiile sunt aceleasi, si le poti folosi asa cum le-ai folosit pana acum in Borland.

Cod:

#include <iostream>
#include <fstream>

using namespace std;

Testeaza cateva probleme (adunare, cmmdc etc) pe evaluatorul de aici folosind aceste librarii, si vei intelege exact la ce ma refer.

[.h]

Asa cum ti-a recomandat si wefgef, pentru a fi sigur ca librariile vor functiona asa cum te astepti, foloseste standardul actual: toate numele vor fi fara .h terminal (ex: iostream.h -> iostream, fstream.h -> fstream), iar librariile specifice C vor avea un c in fata (ex: stdio.h -> cstdio, stdlib.h -> cstdlib, ctype.h -> cctype).

Incearca sa scrii sursele dupa aceste modele din standardul ISO, asta te asigura ca vor functiona oriunde si oricand (BorlandC a iesit de mult timp din clasa "oriunde" sau "oricand") 

Imi place proiectul Din cate vad, varianta optimizata a constructiei automatului folosind functia prefix urmareste aceeasi idee din algoritmul Aho-Corasick, in care ei calculeaza o functie "fail" pentru fiecare nod din trie.

O obiectie, totusi, la reprezentarea grafica a trie-ului, din primul exemplu: din cate stiam, un trie ar trebui sa aiba muchiile etichetate cu caractere din sigma, iar tu ai etichetat nodurile; oricum, ideea de baza se pastreaza, insa pentru consistenta definitiei pe care ai enuntat-o si tu in lucrare cu cateva randuri inainte, ma gandesc ca un exemplu ar fi trebuit sa arate in genul asta http://upload.wikimedia.org/wikipedia/commons/thumb/b/be/Trie_example.svg/250px-Trie_example.svg.png 

Atunci nu se poate rezolva in timp polinomial. Daca ai gasi un astfel de algoritm, ai rezolva si problema drumului hamiltonian (cauti drumul dintre doua noduri care sa treaca prin toate celelalte |V|-2 noduri).
Cred ca poti gasi o rezolvare intr-o dinamica pe stari in O(2^N * N^2), similara cu gasirea drumului hamiltonian de cost minim.

Daca nu au voie sa se repete, e NP-completa.

Despre compilatoare si diferentele dintre Borland si gcc, respectiv g++ s-a mai discutat, poti cauta pe forum si in documentatie. In esenta, daca o sursa compileaza pe infoarena, va compila si la ONI. Daca ai folosit pana acum doar Borland citeste postul lui Andrei de aici, referitor la functiile de input/output. Incearca sa rezolvi cateva probleme aici si te vei lamuri singur cum sta treaba cu compilatoarele folosite la ONI.

Cat despre temele si ideile de pregatire, training-path-ul pus la punct de Cosmin este o resursa excelenta. Succes in continuare! 

Cred ca daca se va pastra sistemul prezent de wiki, baza educationala infoarena va creste considerabil. Training-path-ul e extraordinar, si eu sper ca fiecare element al listelor de acolo sa se transforme in articole de sine statatoare. Mai aveam de anul trecut niste proiecte de articole, care au ramas insa la faza de ciorne, tot din lipsa timpului; dupa ONI insa, o sa scriu eu despre Aho-Corasick, am citit acum si ideea mi se pare super.

Multumesc, Cosmin! E exact ce cautam 

Am gasit cateva paper-uri in care este explicata constructia unui "minimal acyclic deterministic finite automata" (de exemplu acesta), in care se prezinta constructia unui automat care poate accepta un dictionar de cuvinte. Metoda e destul de simpla, se porneste de la "reversed trie" (trie-ul cuvintelor inversate) si se inverseaza si acesta, eliminand apoi starile sau lanturile care se regasesc in alte lanturi.

Totusi, un astfel de automat poate accepta orice cuvant dintr-o anumita multime de cuvinte, nu poate fi folosit insa pentru string matching. De exemplu, un automat de potrivire pentru un singur pattern P trebuie sa accepte orice cuvant x astfel incat P este sufix al lui x. Similar, un automat de potrivire pentru a gasi toate aparitiile pattern-urilor P1 si P2 ar insemna sa accepte orice cuvant x astfel incat P1 este sufix al lui x sau P2 este sufix al lui x etc.

Intrebarea mea era legata de constructia automatelor pentru potrivirile "multi-pattern" - se poate asa ceva in timp polinomial (banuiesc ca da), si cum anume?

Am crezut acum cateva zile ca am reusit sa gasesc un algoritm in O(L*|sigma|), unde L este lungimea totala a pattern-urilor, se pare insa ca nu functioneaza asa cum ma asteptam