matricea respectiva se calculeaza in O(n^3).

Nu sunt puse neaparat in ordinea dificultatii. Pentru majoritatea ai articole cu rezolvari. (fiind date la concursuri gazduite de infoarena)

Pietre
Obj
Xerox
Curse de cai
Pioni2
Pawns
Joc pe grid

Si, evident, cele 7 din 8 jocuri de pe infoarena

Joc
Joc2
Joc3
Joc4
Joc5
Joc6
Joc8

Inca o problema interesanta ar fi Cartonase, data la .campion 2008, runda a 6a.

Spor! 

s-ar fi putut parsa citirea si pusa limita de timp astfel incat sa iei 80-90 cu citire normala. cred ca ar fi fost un exercitiu ultil.

e declarat global? daca e declarat global, ai grija sa nu faci multe apeluri recursive.

functia scanf are mai multi parametrii care se efectueaza mai incet decat o adunare si o inmultire, plus ca ea intoarce numarul de variabile (din cele solicitate de tine) citite "cu succes". pentru mai multe detalii despre cum functioneaza scanf citete aici.

  daca suma fiilor e mai mare decat 0
   suma nodului = v[nod] +suma fiiloor

nu e bine cu suma fiilor.

wtf?!?!?

de ce? au invatat php? 

mai bine nu o faci functie separata. atunci sigur va fi mai rapid. nu stiu care e treaba cu 'inline'. pe unele evaluatoare mi-a mers mai repede, pe altele nu. 

faci un arbore de intervale. pentru fiecare nod ce deserveste intevalul [p.q] vei tine 3 informatii:

1. lungimea celui mai mare interval de camere libere pentru nodul respectiv (l_curr).
2. lungimea celui mai mare interval de camere libere care incepe in p (l_left).
3. lungimea celui mai mare interval de camere libere care se termina in q (l_right).

cand faci update ai 2 cazuri:

1. daca nodul tau este inclus in intervalul pe care faci update, atunci modifici cele 3 valor.
2. daca nodul tau nu este inclus in intervalul pe care faci update, atunci ii modifici valorile in functie de l_curr, l_left si l_right ai fiilor sai. este clar ca poti unii cei doi fii daca exista un interval liber care se termina in capatul din dreapta al fiului stang si un alt interval liber care incepe in capatul stanga al fiului drept.

Cod:

10 10
1 3 3
1 2 3
3 5 1
3 8 1
5 8 2
5 4 1
5 6 1
5 7 1
8 9 1
8 10 1
8
2 3 4
2 3 1
3 2 1
4 5 6
5 4 1
4 5 7
8 6 3
2 10 1

Cod:

13
13
11
11
11
11
11
11
11

Cod:

10 10
1 3 4
1 2 4
3 5 1
3 8 1
5 8 2
5 4 1
5 6 1
5 7 1
8 9 1
8 10 1
7
2 3 3
1 3 4
2 5 4
2 3 1
2 3 2
6 7 1
7 3 1

Cod:

15
14
14
14
12
12
12
12

fa-ti generator de teste si apoi .bat care sa ruleze generatorul si sursa ta, de 1000 de ori. trebuie sa nimeresti un test pe care sa-ti iasa din timp

tine o matrice P[i,j] = i*j. in loc sa aduni k*A[i,j] in back, aduni P[k, A[i,j] ]. k poate sa fie maxim pana la 32, deci ar trebui sa intre. de obicei folosesc astfel de optimizari cand imi iese din timp cu foarte putin. sper sa te ajute.

incearca urmatorul test

Cod:

7 6
1 2 2
1 3 2
3 7 2
2 4 2
4 5 3
4 6 3
8
2 7 1
3 7 3
1 7 1
4 2 1
6 7 4
6 7 1
5 6 3
5 7 1

raspunsul ar trebui sa fie:

Cod:

14
13
13
12
11
11
9
9
7

sper sa nu fi gresit

trimite-mi sursa pe mail ([email protected]). poate reusesc sa te ajut

si (p1*q2+p2*q1)=B?
verifica sa nu fi dimensionat gresit vreun vector.
daca ecuatiile de mai jos iti merg pentru orice k, inseamna ca ai o greseala in implementare, nu in idee.

ai cateva mici scapari:

1) linia 103:

Cod:

for (i=1;i<=n&&ok;i++)

in vectorul sum ai introdus l (l>=n) elemente.

2) linia 133:

Cod:

if (sum[mij][0]>caut) b=mij-1;  
if (sum[mij][0]<caut) a=mij+1; 

fie pui si evalitatea la unul din if-uri, fie in loc de al doilea if pui else

3) sumele din sirul tau pot fi mai mari decat S, deci o sa iterezi for-ul de la 103 pana cand S devine mai mica dacat suma curenta. (altfel diferenta o sa fie negativa, deci nu se va gasi in sirul tau, si vei face niste cautari inutile)

ca sa te lamuresti mai bine poti sa consulti sursa cu modificarile de mai sus.

spor in continuare. 

scuze, nu citisem pana la capat 
afisezi bine? (de exemplu, cand ai determinat raspunsul verifica sa fie corect, iar daca nu e corect fa-ti programul sa cicelze. trimite pe infoarena. daca iei tle, atunci ai descoperit cauza)

iti merg si testele de mai sus? (10 post-uri mai sus)

ah, am ramas cu impresia ca e invers. scuze

de ce la .campion limita era 0.2 si aici e 0.5? 

http://youtube.com/watch?v=G3lD6fBLjbQ&feature=related tot asta rupe capu :p

editat de moderator:

[...] Eu de obicei nu prea citesc enunturile dar stiu ca am incercat si asa si nu luam 100

nu este o atitudine corecta. daca vrei sa ajungi la ONI anul viitor, ar trebui sa citesti pana la ultima virgula.
si un sfat offtopic... n-ar strica sa nu te mai grabesti si sa scrii mai ingrijit. 

Asadar, muzicalitatea reprezinta dimensiunea celei mai lungi succesiuni formata din caractere ce apar in ordinea din succesiune atat in primul rand, cat si in cel de al doilea, pe pozitii nu neaparat consecutive.

cu alte cuvinte, muzicalitatea a doua randuri este lungimea cel mai lung subsir comun al acestora.

poti sa folosesti. teoretic merge mai repede cu streamuri.

Din contra, streamurile merg mai repede. Lui victor ii ia foarte mult afisarea pentru ca foloseste 'endl'. Acesta din urma goleste bufferul dupa fiecare numar afisat. In locul lui ar trebui folosit '\n'. Lui wefgef cred ca ii merge incet pentru ca foloseste obiectele 'cin' si 'cout', care probabil nu sunt optimizate pentru citirea si respectiv scrierea in fisiere (posibil sa aibe un buffer mai mic sau deloc).

uite-te peste sursele de care vorbeste Filip ca sa te lamuresti