Vreau sa felicit organizatorii olimpiadei nationale de programare dinamica pentru conditiile foarte bune de cazare(comparabile cu cele de la hotel) si mancarea care a fost foarte buna.

Despre subiecte nu pot spune acelasi lucru.   .
Vreau sa felicit in primul rand pe cei care au redus barajul la o singura proba. Sigur masura asta selecteaza mult mai  bine lotul, adica daca faci bine la oni sau daca ai punctaj apropiat de primul loc tu clar esti foarte bun si meriti sa intrii in lot   .
In al doilea rand doresc sa felicit comisia de la 11-12 si baraj care a dat dovada de o originalitate iesita din comun. Cine s-ar fi gandit ca din 9 probleme 6 se vor rezolva cu programare dinamica.

Un mic rezumat:

Search: A[ i ][j][k] = prima apariţie a literei k în cuvântul i, începând cu poziţia j.
Urat: Problema asta mi s-a parut absolut geniala. Pentru a rezolva problema bagai un back in 5 minute, te uitai peste numere si te prindeai de recurenta din dinamica. Imi place ca totusi autorul a incercat de unde vine recurenta aia.
Zlego: functia prefix + programare dinamica. Ca sa nu fie doar dinamica s-a adaugat functia prefix ca sa nu fie dinamica pura.

Drumuri: singura problema cu grafuri din tot oni-ul. Problema imposibila din pacate deci nu prea rezolvabila in 4 ore. Totusi singura problema de la ONPD care mi-a placut.
Minerale: problema asta a fost foarte foarte originala. Teoria: http://en.wikipedia.org/wiki/Chomsky_normal_form si http://en.wikipedia.org/wiki/CYK_algorithm . Felicitari autorului pentru originalitatea de a cauta pe wikipedia. E foarte greu in zilele noastre sa faci asta.
Tarabe: aici nu comentez nimic

Insula: Se calculeaza in dp[ i ][j] suma distantelor pentru toate punctele care au ordonata mai mica sau egala cu al j-lea punct de pe lantul convex, folosind i laturi. Foarte tare, la fel ca la problema zlego, mai adaugam un algoritm ca sa nu fie doar dinamica.
Kmalloc: asta mi s-a parut foarte interesanta. Felicitari autorului.   Singura problema care mi-a placut din tot concursul desi n-am fost in stare sa o rezolv.
Teroristi: Banuiesc ca nu are rost sa zic ca se face tot cu dinamica deoarece majoritatea s-au prins. Interesanta totusi ideea de dinamica pe biti pe graf orientat aciclic.

Chiar nu inteleg cum 15 oameni din comisie nu sunt in stare sa alcatuiasca un set variat de probleme la fel ca si in anii trecuti si ce se doreste sa se reflecte prin rezultatele astea? Eu nu inteleg cum o mana de oameni poate da subiecte incomparabil mai bune la algoritmiada si comisia oni nu poate sa aleaga 9 probleme care sa selecteze cum trebuie participantii? O fi din cauza ca subiectele se finalizeaza inainte de probe si ca nu sunt pregatite din timp propabil ?
Sa inteleg ca daca vreau sa obtin un rezultat bun anul urmator trebuie sa rezolv doar probleme de programare dinamica sau anul urmator se schimba subiectul si trebuie sa invat doar structuri de date sau grafuri? Sa nu uitam ca si la oji selectia concurentilor a fost foarte buna   . Imi place ca si acolo am avut o dinamica.

In ultimul rand vreau sa-i felicit pe cei din bistrita pentru rezultatele exceptionale pe care le-au obtinut la oni dar in special pentru puterea vocii lor care se auzea foarte bine in camere in ziua de dinaintea probei de baraj. Vreau sa le multumesc frumos pentru cuvintele frumoase adresate cand i-am rugat sa nu mai faca galagie.

La celelalte clase cum au fost subiectele ?

Ei, lasa ca se putea si mai rau, macar a fost frumos orasul 

Ce are mai special testul 4?
ma incadrez destul de bine in restul testelor(maxim 752ms, pe ultimul test).
Folosec un algoritm asemanator BFS cu coada(in care introduc toate elementele care sunt inconjurate in toate cele 4 parti de maxime, dupa care aplic BFS).

LE: Am parsat citirea, s-au imbunatatit timpurile(332 ms), dar pe testul 4...acelasi lucru:|

LE2: Am inlocuit BFS cu un DFS (cu stack) si am luat 100

Am facut un back pentru a gasi ciclul eulerian intr-un graf. Merge bine pana la 16... pentru 17,18,19,20 ia mult prea mult timp. Cum as mai putea optimiza?

Cod:

	cat timp exista elemente in stiva
	{	
		nod=ultimul nod din stiva;	
		daca nu am mai trecut prin muchia cu valoarea zero
		{adaug nodul respectiv la stiva}
		altfel daca nu am mai trecut prin muchia cu valoarea unu
		{adaug nodul respectiv la stiva}		 
		altfel {adaug nodul la ciclu}
	}	

cineva care a facut problema de 100p, nu ar putea pune un test mai mare/bun decat cel din exemplu, sa imi gasesc greseala
mersi

Later Edit:am rezolvat(pacat ca nu am facut-o in timpul concursului )

e problema de la oji din 2006...originala era cu
•   1<=n<=150
•   1<=k<=100
astfel o puteai face cu multimi:)