141 Sortari

[•S7012MY]

am facut operatii pe biti am pus break-uri am parsat dar nu mi-a intrat nici cum in timp. Te poti uita peste surse

[•SebiSebi]

Eu am generat,pentru fiecare test, toate permutarile de n elemente , iar apoi pe fiecare permutare am vazut daca cele m interschimbari au sortat "permutarile" si imi da TLE. Cum as putea face cu generarea submultimilor , am vazut ca asa este indiciul.

[•pauldb]

Se poate demonstra ca o retea de sortare este buna daca sorteaza corect orice multime {0, 1}^N. Demonstratia e in Cormen parca.

[•SebiSebi]

Problema nu intra in O(t*m*n!)?

[•pauldb]

N-ar trebui.

[•SebiSebi]

Cu O(2^N * M) iau TLE pe 3 teste. Ce as putea optimiza?

Am rezolvat . Nu era nevoie decat de un break acolo unde trebuie.

[•repp4radu]

Cred ca ar trebui marita limita de timp la problema asta.
Am complexitate O(T * 2 ^ N * M) si iau TLE pe ultimul test.
Folosesc operatii pe biti, parsez citirea, dau break la primul sir de biti care nu poate fi sortat, preprocesez puterile lui 2 cum a fost sugerat mai sus si tot nu intru.

[•SebiSebi]

Incearca cu back simplu, nu pe biti. 

[•repp4radu]

Am luat 100. Mersi mult!