1229 Secvmin

[•wefgef]

Aici puteți discuta despre problema Secvmin.

[•galbenu]

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 )

[•eudanip]

Da, se poate O(N). Iti zic solutia private daca vrei ca poate unii vor sa se mai gandeasca pana sa se posteze solutiile.

[•vlad.doru]

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?

[•klamathix]

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.