Folosim solutia  lui Bogdan numai ca in loc de multimi disjucte folosim o padure de arbori direct. Nodurile sunt numerotate folosind indicii vectorului.
Practic cand ajungem la un numar cautam in Hash indicele numarului v[ i ]-1 si v[ i ]+1
si daca  le gasim(pe oricare dintre ele, nu neaparat pe amandoua) trasam o muchie de la  i la indicele/indicii valorilor gasite.
La final putem face un DFS in care determinam numarul de elemente din fiecare arbore(lant) si minimul sau maximul ceea ce este suficient pentru a afisa numerele.
DFS-ul este O(N) fiindca avem maxim N-1 muchii.  

Trebuie sa stim vreun limbaj anume sau orice altceva inainte de inceperea cursului?


PS: Eu m-am inscris dar nu vad unde e formularul pentru logare.

Nu se poate face cu ridicare la putere in timp logaritmic de matrice?
Ca la problema iepuri http://infoarena.ro/problema/iepuri


L.E.: Nu citisem comentariul lui Vlad.

Totusi metoda asta cu cross product mi se pare mai dificila. E mult mai usor cu pantele sau teorema cosinusului.

Da dar cross product e destul de folosit in probleme. Adica cu el poti afla ariile poligoanelor, poti sa afli daca 2 segmente se intersecteaza, poti sa afli infasuratoarea convexa si multe altele(vezi topcoder). Sa fiu sincer, e prima data cand folosesc teorema cosinusului la o problema de informatica.

Este buna si solutia cu tangenta unghiului format de cele 2 drepte! Poti aplica ce a zis Silviu si in cazul cand unghiul este ACB. Dar nu cred ca este nevoie sa calculezi arctangenta. Adica pe (0,pi/2) e pozitiva  si crescatoare iar pe (pi/2,pi) e negativa si crescatoare si la imagini egale ai argumente egale(in afara de 0 si pi) deci nu e nici o problema sa-ti dai seama daca unghiul x are masura mai mare ca unghiul y daca le stii tangentele.

Cel mai simplu merge cu teorema cosinusului.
Cum stii coordonatele afli lungimile laturilor cu Th Pitagora si cosinusul unghiului cu Th cosinusului. In cazul in care vrei sa afli cel mai mare unghi sub 180^o acesta va avea cosinusul minim, iar daca vrei pentru unghiurile mai mare de 180^o acesta are cosinusul maxim.(pe [0,pi] cosinusul este strict descrescator).


O metoda mai grea ar fi cu cross product prin care putem afla sinusul. Dar nu este de ajuns deoarece sinusul nu este monoton pe [0, PI].
Deci trebuie sa aflam si daca unghiul trece in cadranul 2 sau nu.
Fie d' perpendicular pe dreapta AC in punctul B', B apartine d', daca B' apartine (AC) atunci masura unghiului este mai mica de pi/2, iar daca nu apartine este mai mare.
Pentru a afla daca B' apartine (AC) trebuie sa-i aflam coordonatele.
Scriem ecuatia dreptei AC si aflam panta. Cum d' perp. pe AC produsul pantelor este -1 => panta lui d' este (-1/(panta lui AC)).
Acum stim ca (y-y_B)=panta(d')*(x-x_B) si o putem rescrie sub forma ax+by+c=0.
Putem afla astfel coordonatele lui B' din cele 2 ecuatii pe care le verifica(ecuatia dreptei d' si a dreptei AC).
Pentru a afla daca B' apartine (AC) verificam daca coordonatele lui B sunt in interiorul celui mai mic dreptunghi determinat de A si C cu laturile paralele cu axele de coordonate. Daca apartine acestui dreptunghi atunci apartine si segmentului (AC).(segmentul AC este intersectia punctelor din interiorul dreptunghiului cu axa AC pe care B' se afla din ipoteza).


Sper ca am scris bine. Daca gasiti greseli va rog sa ma corectati.

Mie mi-ar placea cel mai mult sa  scrii despre 1), 12), 11) in ordinea aceasta, desi majoritatea mi se par interesante.

[anumite]

Nu. Vorbeam in general. Ma gandesc ca un arbore binar de cautare e mult mai folosit decat programarea dinamica nu? Poate si arborii de intervale sau heapurile.

Vreau doar sa stiu daca se foloseste multa programarea dinamica in practica pentru nu vad cum anumite probleme de programare dinamica pot fi folosite pentru a ajuta pe cineva. Problema rucsacului cred ca apare si in practica. Dar o problema de genul "cate siruri de N numere dintre care K au o anumita proprietate" nu stiu daca apare.

Apropo, cat de utila este programarea dinamica in lumea reala, fata de grafuri sau fata de arborii binari de cautare.

Legat de faptul ca a fost dus in spate doar de ingineri: Mark spune in acest video din 2005 ca el cauta sa angajeze "raw inteligence". Asta spune multe de "spiritul" si adaptabilitatea companiei.

Dar inteligenta costa( chiar 10.000 de dolari pe luna). Chiar asa de multi bani a facut la 1 an de la lansarea facebook sau in America tinerii antreprenori sunt avantajati de banci sa faca credite?

Cred ca s-ar putea sa mai fie nevoie de niste tipuri de teste.
De exemplu sursa http://infoarena.ro/job_detail/601818?action=view-source  ia 100 de puncte desi este gresita linia 62: low[ x]=min(low[ x],low[ y]);. Corect: low[ x]=min(low[ x],def [y]);

Pe testul

Cod:

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

sursa gresita afiseaza

Cod:

1
1 2 3 4 5 6 7 8 

in loc de

Cod:

2
2 6 7 8 
1 2 3 4 5 

.

Si la afisare cred ca intra la: "(*) Se acordă punctajul chiar dacă soluŃia propusă nu prezintă elemente de eficienŃă sau afisează numerele cifră cu cifră." deci e ok.

Multumesc de completare. Eu nu vazusem aceasta nota.

La partea I, 2 b) minimu era 31 si maximul 35? ca in barem "b. Pentru răspuns corect 6p. Se acordă câte 3p. pentru fiecare valoare corectă."

E bun 31 si 35.

Apropo de barem. Voua nu vi se pare ca este o mica greseala la ultimul algoritm din barem? Nu trebuia pusa o conditie ca S1-c1<10 si s2-c2<10? Adica daca S1=13, c1 nu are cum sa fie 1 pentru ca S1-c1=12 care nu e cifra.

Si afisarea cum ati facut-o? Eu am afisat direct cifrele pentru ca nu scria nicaieri ca trebuie salvat sau calculat efectiv numarul. Ci doar sa se gaseasca in fisierul text.

La varianta 8,ultima problema de la subiectul al III-lea, functia sub se poate scrie si fara a folosi programare dinamica?
Si unde trebuie sa justificam eficienta ce scriem?

Am vorbit de la ultima postare si cu alti absolventi si ei mi-au spus ca trebuie pseudocod.
Cum vine asta?

E o gluma?

La subiectele la care trebuie sa despriem algoritmul in "limbaj natural" folosim pseudocod in limba romana nu?

Depinde dupa ce cauti, dar e buna idea .

Ok.
Dar eu ma gandisem la un algoritm euristic care ca sa fixeze valoarea ***********  si afla coordonatele unui punctul si verifica apoi daca chiar este punct comun... cu o anumita eroare, si practic timpul de executie depinde de cat de exact vreau sa fie rezultatul meu.

Punctul din output se da prin coordonatele sale?
Cat de mare trebuie sa fie acuratetea solutiei(cate zecimale exacte)?
Se dau coordonatele vreunui varf al dreptunghiului mic? Daca da, care din ele?
Punctul (0,0) este situat in coltul stanga jos al dreptunghiului mare?

Da ai dreptate.

Eu asa am gandit, nu stiu daca este mai complicat dar asta mi-a venit in minte.

La problema cu minimul si maximul nu ar merge si o solutie recursiva gen:
Comparam elementele vecine 2 cate 2 => N/2 comparatii, N/2 maxime, N/2 minime
Comparam maximele, si minimele din fiecare perechi 2 cate 2=> N/4+N/4=N/2 comparatii si raman N/4 maxime si N/4 minime
Comparam din nou maximele si minimele din fiecare cvadrupluri=> N/8 comparatii la maxime + N/8 la minime=N/4 camparatii si raman N/8 maxime si N/8 minime
Comparam grupurile de maximele si minimele din grupurile de cate 8=>N/16 +N/16 = N/8 comparatii si raman N/16 maxime si N/16 minime si tot asa.
Ar veni N/2+N/2+(N/4+N/8+N/16+...+1)=3N/2

pair functie(int st,int dr)
{
   pair ret;
   if(st==dr)
   { ret.min=a[st];
     ret.max=a[st];
   }
   else
   {m=(st+dr)/2;
   pair pst=functie(st,m);
   pair pdr=functie(m+1,dr);
   
   ret.min=min(pst.min,pdr.min);
   ret.max=max(pst.max,pdr.max);}
   
   return ret;
   
}

Am luat 100  . Multumesc.

Intre [1...5*p] da

Asa mersi de asta aveam nevoie.
+ la karma

Da.
Dar nu  stiu intervalul.
Nu ar trebuie sa fie [0....5*10^8]?
Sau ma rog [0....5*p]?

Tu nu cauti N! ci il cauti pe N.
PS: Ai o formula ca sa vezi cate 0-uri are N! plecand de la N. Ti-am spus...citeste tot topicul.

Numarul acela suficient de mare este cum il aflu?

L.E. : 5*10^8 imi ajunge?