"Un palindrom este un număr natural (...)", "Atentie! Un numar natural are cel putin o cifra".

sqrt poate avea erori de precizie. Daca calculezi sqrt(4) poate sa iti rezulte 1.999999 care devine 1 cand ii faci cast la int.

http://www.infoarena.ro/forum/index.php?topic=10164.0

Am gasit pe net o solutie cu Divide et Impera + Z-algorithm. Ideea e asa:

Tu cauti toate substringurile X = YZ, unde Y si Z sunt stringuri nevide si Y = Z.

Cauti toate substringurile de aceasta forma din intervalul [st, dr]. Fie m mijlocul intervalului.
Ai 3 cazuri:
1) X incepe in prima jumatate ([st,m]) si se termina in a doua jumatate ([m+1,dr]).
2) X se afla in intregime in prima jumatate
3) X se afla in intregime in a doua jumatate

Pentru cazurile 2) si 3) mergi recursiv si afli raspunsul pentru intervalele respective.

Ramane cazul 1). Ai 3 subcazuri:
1a) Y se termina exact la m
1b) Y se termina inainte de m
1c) Y se termina dupa m

Cu ajutorul algoritmului Z calculam vectorul Z, Z[i] = cel mai lung prefix al lui [m+1,dr] astfel incat acesta sa fie prefix si pentru [i,m].

Stringurile de la 1a) sunt acele stringuri care respecta proprietatea ca incep la i si i + Z[i] - 1 = m.

Pentru 1b) mai trebuie sa calculam vectorul RZ, RZ[i] = cel mai lung sufix al lui [st,m] astfel incat acesta sa fie sufix si pentru [st,i] (practic algoritmul Z pe sirul inversat).

Impartim stringurile Y is Z in doua parti astfel incat Y = Y₁Y₂, Z = Z₁Z₂, Y₁ = Z₁, Y₂ = Z₂ si Z₂ este prefix al lui [m+1,dr].

[ ... Y₁ Y₂ Z₁ ]   [ Z₂ ... ]
st               m m+1     dr

Incercam toate pozitiile de inceput i pentru Y₂. Y₂ se poate termina cel tarziu la min(i + Z[i] - 1, m - 2). Deci avem un interval de posibilitati pentru Y₂. Incercam sa determinam un astfel de interval si pentru Z₁. Z₁ poate incepe cel mult la max(i + 1, m - RZ[i - 1]). Avand aceste doua intervale, putem calcula cate stringuri intra in acest caz (cand Y₂ incepe la i).

La 1c) luam intervalele invers si se reduce la 1b).

Deci complexitatea e O(NlogN).

Sursa mea: http://ideone.com/vC4bJT

De cand exista Java?  Am ratat vreun anunt? Daca nu, ar trebui sa anuntati.

Se face cam o materie din 6 pe semestru matematica. Si pentru mine a fost cam plictisitor, dar ce sa faci.

Am completat articolul. Spor la invatat.

Citesti N siruri de caractere.

Nu vad care e problema daca nu acoperi tot int-ul. Si daca folosesti std::numeric_limits<int>::max() risti sa faci overflow in unele cazuri.

Singurul avantaj e ca merge combinat cu memset(). Dar putem folosi fill(), deci e cam inutila chestia.

Nu e bun modul de construire al codului.

Cod:

2
3
1 2 0
1 3 1
3
1 2 0
2 3 1

Daca ti se dau muchiile in alta ordine tie iti iese alt cod.

x si y sunt indici in sirul sortat al sufixelor.

S-a mai raspuns la aceasta intrebare.

Cod:

freopen("d.in", "r", stdin);
freopen("d.out", "w", stdout);
scanf("%d %d", &N, &M);
printf("%d %d", N, M);

Apelurile freopen() face ca intrarea/iesirea standard sa fie din fisier.

Legat de doua intrebare, greseala e ca citesti si caracterul '\n' (sfarsit de linie) si trebuie sa te asiguri ca sari peste el.
De exemplu fscanf(f,"%d\n",&n); la inceput si citesti un caracter in plus la sfarsitul fiecarei linii.

Ai rabdare. Se va creea pagina in zilele urmatoare.

Nu am testat, dar probabil iti da gresit pe un test de genul asta.

2 2
-2 3
3 -2

Raspuns: 10

7
4 6 5 7 2 3 1

Raspuns: 3

Leeerooooooy Jeeenkiiiiiins!   Cine e fan Blizzard/Warcraft?
Ar fi util sa vezi scorul potential la probleme ca la codeforces.

Din exemplu se intelege ca S se construieste cu max, nu min. ?!

Faci exact cum ai spus. Bagi totul in coada, setezi distanta pentru acele puncte la 0 si ii dai drumul. Nu e nimic special. Explica ce nu intelegi.

Sirurile pot fi mai lungi decat 30. Se da totul peste cap fiindca depasesti limitele vectorului.

Nu inteleg de ce solutia oficiala e suficient de rapida. Dupa calculele mele ies cam 40000 * 16 * 40 * 10 operatii. E ceva optimizare la parcurgerea subsecventelor? Multumesc!

Succes, va tinem pumnii!

Timpul de executie e prea mare pe ultimul test. Incearca cu integer in loc de longint.

Marsmusic
...
Acum vom incerca sa determinam pentru fiecare melodie timpul mediu de intersectie pe cele doua posturi utilizand dinamica mentionata anterior (din care vom "scoate" melodia curenta, intrucat aceasta nu poate fi folosita) si sume partiale.

Asa am facut si eu, doar ca nu am stiut cum sa "scot" melodia curenta. Deci, am refacut dinamica pentru fiecare melodie si a devenit N * M^3. Poti detalia?