Ma bucur ca problema a fost rezolvata aproape perfect de toti concurentii.
Nu a fost deosebit de dificila, dar mi s-a parut interesanta deoarece
existau mai multe metode de rezolvare pentru ea.
Multumesc celor care mi-au respectat dorinta in legatura cu descrierea
algoritmului de rezolvare. Este mult mai simplu sa citesc primele 5 randuri
ale sursei, decat sa ma apuc sa descifrez for-urile din program :-)
Acum pe scurt despre rezolvare:
I. Punctul a):
1) o solutie constituia in retinerea unui vector V de 32000 de elemente,
in V[i] retinandu-se de cate ori aparea elementul i in matrice
(bineinteles, ignorand multiplele aparitii pe o linie). Aceasta
solutie este cea mai "urata", deoarece este mare consumatoare de
memorie. Ce faceati daca elementele matricii erau intre 1 si
maxlongint ? (greseala mea ca nu am dat astfel limitele ! :-) )
2) o alta solutie constituia in liniarizarea matricii urmata de sortarea
vectorului obtinut. O solutie interesanta, dar clar nepotrivita
acestei probleme. De ce ? Deoarece exista solutia 3) :-)
3) solutia optima (aplicabila pentru orice limite ale elementelor si
de complexitate optima) constituia in liniarizarea matricei prin
interclasarea liniilor acesteia. Trebuia folosit si faptul ca
liniile erau sortate crescator nu ? Aceasta solutie a fost data
doar de Baicu Ciprian pe care il felicit !
II. Punctul b)
Punctul b) se rezolva bineinteles prin programare dinamica. Nu mai
descriu detailiat metoda, deoarece toti concurentii "s-au prins" de
ea. Complexitatea de rezolvare era de O(n^4) (mai precis O(n^2 * m^2)),
dar constanta se putea micsora mult folosind si de data asta faptul ca
liniile erau sortate crescator. Las concurentii care nu au folosit
acest fapt in rezolvarea lor, sa se gandeasca un pic. Optimizarea
este foarte simpla.
Cam asta. Imi cer inca o data scuze pentru intarzierea afisarii
rezultatelor. Dar motivele sunt totusi foarte solide (examene, colocvii,
referate etc.)
|
|