|
Titlul: 1229 Secvmin Scris de: Andrei Grigorean din Ianuarie 22, 2012, 14:26:00 Aici puteți discuta despre problema Secvmin (http://infoarena.ro/problema/secvmin).
Titlul: Răspuns: 1229 Secvmin Scris de: galbenu dorin din Ianuarie 23, 2012, 07:12:01 As vrea sa aflu si eu ce complexitate a avut algoritmul membrilor infoarena la aceasta problema si daca se poate o sugestie sau doua pentru rezolvarea optima a problemei. Eu unul am salvat pozitiile in care se gasesc elementele din sirul 2 in sirul 1 intr-o lista,mai bine spus:
In L[2]-> sunt pastrate toate pozitiile unde apare elementu cu numarul de ordine l 2 din sirul B in sirul A,intr-o ordine anumita.(crescator) L[3]->toate pozitiile unde apare elementul cu numarul de ordine 3 din sirul B in sirul A s.a.m.d. Un prim dezavantaj al abordarii mele este faptul ca pentru fiecare element din al doilea sir parcurgem toate elementele din primul , la final obtinandu-se o complexitate nu-tocmai-frumoasa de O(N*M). Folosind aceasta lista am determinat secventele sirului A ce il au pe B drept subsir,insa nu cred ca solutia mea este tocmai buna,dovada fiind punctajul de 40 puncte si limita de timp depasita pentru 5-6 teste. Tl;dr : Se poate gasi o rezolvare ce sa aiba o complexitate mai mica de O(N*M) si daca da,care este aceasta? (indicii :D ) Titlul: Răspuns: 1229 Secvmin Scris de: Eugenie Daniel Posdarascu din Ianuarie 23, 2012, 09:42:10 Da, se poate O(N). Iti zic solutia private daca vrei ca poate unii vor sa se mai gandeasca pana sa se posteze solutiile.
Titlul: Răspuns: 1229 Secvmin Scris de: Ion Vlad-Doru din Februarie 23, 2012, 23:01:37 Am reusit sa obtin 85 de puncte cu o complexitate de O(m+n) .. Exista vreo posibilitate sa intre si solutia aceasta in timp? Merita sa incerc sa optimizez implementarea?
Titlul: Răspuns: 1229 Secvmin Scris de: Mihai Calancea din Februarie 23, 2012, 23:15:24 Pai cum ai putea sa obtii mai putin de O(n + m)?
Da, inceaca sa scrii unele lucruri mai ingrijit si sa faci optimizari minore. |