
In primul rand trebuie sa remarc ca nici unul dintre programe nu a
depasit timpul de rulare de o secunda. Cele care nu au mers au dat
raspunsuri gresite, dar s-au incadrat in timp.
Varianta de rezolvare pe care am ales-o eu este urmatoarea: Se
genereaza combinari de N*N luate cate K pentru a genera toate
configuratiile posibile de gauri. Pentru fiecare configuratie
obtinuta, se afla configuratia simetrica si se vede daca configuratia
originala este mai mica (in sens alfabetic). Daca da, ea este
tiparita. Daca nu, ea este respinsa.
Cateva observatii:
1) Generarea combinarilor poate fi facuta in asa fel incat
backtracking-ul sa nu mai "dea rateuri", ci sa umple de fiecare data
stiva cu valori care pot conduce la o solutie. Generarea functioneaza
chiar in O(Comb[N*N, K]).
2) In cazul unui backtracking care cere toate solutiile unei probleme,
nu prea are sens sa inchideti si sa redeschideti fisierul de iesire
dupa tiparirea fiecarei solutii. Avantajul este ca, daca programul nu
apuca sa se termine in timp, fisierul de iesire nu va fi gol, ci va
contine o parte din solutii. Insa in general pentru solutii partiale
nu se acorda punctaje partiale, asa ca de fapt mai mult se pierde
timpul cu executia secventei Close - Append.
Daca au existat si variante diferite de abordare a problemei, va rog
nu ezitati sa le postati.
|
|