Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Sortare 2  (Citit de 2561 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
andreiiii
Echipa infoarena
Client obisnuit
*****

Karma: 23
Deconectat Deconectat

Mesaje: 86



Vezi Profilul
« : Ianuarie 27, 2017, 14:59:04 »

Aici se pot pune întrebări legate de problema Sortare 2 de la concursul PreOJI 2017.
Memorat
birotx
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #1 : 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)******
Memorat
mariusn01
Strain


Karma: 4
Deconectat Deconectat

Mesaje: 16



Vezi Profilul
« Răspunde #2 : Ianuarie 27, 2017, 16:56:02 »

S-a corectat!
Memorat
Vicktor
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #3 : 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
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #4 : 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?
Memorat
Vicktor
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 8



Vezi Profilul
« Răspunde #5 : 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.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines