|
Titlul: Sortare 2 Scris de: Popa Andrei din Ianuarie 27, 2017, 14:59:04 Aici se pot pune întrebări legate de problema Sortare 2 (http://www.infoarena.ro/problema/sortare2) de la concursul PreOJI 2017 (http://www.infoarena.ro/preoji2017).
Titlul: Răspuns: Sortare 2 Scris de: Nedelcescu Radu Costin din Ianuarie 27, 2017, 16:49:18 Cred ca explicatia este eronata:
Explicaţie: În cazul primului exemplu putem forma 3 subşiruri: (4), (1, 2), (3). Putem pune subşirul (3) la finalul subşirului (4) şi rămân subşirurile: (1, 2), (3, 4). Apoi, punând şirul (3, 4) la finalul şirului (1, 2) obţinem permutarea sortată. Corectie: Punem subsirul (4) la finalul subsirului (3)****** Titlul: Răspuns: Sortare 2 Scris de: Marius Nicoli din Ianuarie 27, 2017, 16:56:02 S-a corectat!
Titlul: Răspuns: Sortare 2 Scris de: Victor Teodor Stoian din Ianuarie 31, 2017, 13:49:13 Salut, am o dilema legata de rezolvarea mea. Am luat 40 de puncte cu WA pe celelalte teste si nu imi gasesc contra-exemplu, eu m-am gandit sa numar inversiunile permutarii (ca la matematica, daca k<j si f[k]>f[j] se considera inversiune) doar ca am facut asta pentru secvente, nu pentru fiecare numar si zic ca asta ar fi numarul minim de pasi
Titlul: Răspuns: Sortare 2 Scris de: Mihai Calancea din Ianuarie 31, 2017, 18:30:55 Numărul de inversiuni poate fi de ordinul lui n^2. Ai vreodată nevoie de atâtea operații?
Titlul: Răspuns: Sortare 2 Scris de: Victor Teodor Stoian din Ianuarie 31, 2017, 18:53:49 Sunt n^2 in cazul in care luam luam toate combinatiile de (k,j) cu k,j<=n. Dar eu le-am considerat doar pe cele vecine spunand ca daca k<j f[k]<f[j] nu o consider inversiune pentru ca e ori in ordinea corecta, ori dupa urmeaza ceva mai mic si mi se va calcula la pasul urmator.
|