Sortarea prin oglindiri (o problema)

[•baTTLe4u_15]

Am gasit urmatoarea problema:

Se citeşte de la tastatură un şir de n numere naturale cuprinse între 1 si 60000. Se cere ordonarea crescătoare a acestui şir folosind următoarea operaţie: se fixează un element al şirului şi apoi se oglindesc secvenţele din stânga şi din dreapta lui. De exemplu, dacă în şirul (6 5 7 8 9 4 6 5) se fixează elementul de pe poziţia 4 se va obţine şirul (7 5 6 8 5 6 4 9) adică se oglindeşte şirul (6 5 7) şi şirul (9 4 6 5), şiruri aflate în stânga şi respectiv în dreapta elementului de pe poziţia 4. Se pot fixa şi elementele fictive de pe poziţiile 0 si n+1.
Să se afişeze toate poziţiile care s-au fixat pentru a ajunge la soluţie. Numărul acestor poziţii fixate trebuie să nu fie mai mare decât 3n.
   Exemplu. Pentru ÅŸirul (4,20,5,50,25) poziÅ£iile fixate sunt (4,5,5,6,4, 5,5,6,5,6).

Asta am lucrat eu pana acum
http://pastebin.com/YKSawJze 

Trebuie sa-mi mai dau seama in ce mod se alege pozitia pentru oglindire 

[•cristiavra]

pot sa te intreb unde ai gasit problema?

[•baTTLe4u_15]

Mi-a dat doamna profesoara sa lucrez, dar nici dansa nu stie s-o rezolve...

[•mihaipopa12]

Cred ca problema este si pe infoarena :
http://www.infoarena.ro/problema/order2

[•baTTLe4u_15]

Interesant 
Nu stiam , n-am mai intalnit-o. Si totusi, are 0.1 sec limita de timp, merge cat de cat oglindirea facuta de mine ? Sau sunt complet paralel cu problema...?

[•mihaipopa12]

Solutia problemei e O(n^2). Functia de oglindire e buna dar trebuie sa vezi cum folosesti oglindirile incat sa sortezi sirul. Nu e corecta abordarea ta cu citirea x-ului la care sa oglindesti 

[•baTTLe4u_15]

Stiu, am pus chestia cu citirea pozitiei pentru a testa mai rapid exemplele date de mine si sincer sa fiu nici exemplele nu le pot duce pana la capat.. din momemnt ce nu le-am inteles matematic nici n-am ce implementa. (as crede ca trebuie un if ceva.. sa caut o secventa crescatoare/descrescatoare sau nu stiu.... inca n-am gasit o idee care sa mearga pe caz general).

[•mihaipopa12]

http://probleme.francu.com/arhiva/R0028/enunt.html

De aici e luata problema, vad ca e si rezolvarea acolo.
Bafta!

[•baTTLe4u_15]

Multumesc pentru sursa. O sa studiez cu atentie sa vad care-i faza cu pozitiile acelea pe acolo.