infoarena

Am o problema care imi da batai de cam de 3 zile.
Se da un sir de n numere intregi. Sa se toreasca spre stanga cu k pozitii fara a se folosi un sir suplimentar.
exemplu: [1,2,3,4,5,6,7] rotire cu 3 pozitii -> [4,5,6,7,1,2,3].
Si ca indicatie am sa nu fac k rotiri a cate un element deoarece e ineficient.

Am tot incercat sa gasesc un algoritm, insa nu am reusit doar pe cazuri particulare.

Ca sa rotesti un sir cu K pozitii la stanga poti face asa:

• inversezi pozitiile 1 -> K => K, K-1, ..., 1, K+1, K+2, ..., N
• inversezi pozitiile K+1 -> N => K, K-1, ..., 1, N, N-1 ..., K+1
• inversezi tot sirul => K+1, K+2, ..., N, 1, ..., K

Sau poti sa mai concatenezi sirul inca o data la sfarsit
1 2 3 4 5 6 7 1 2 3 4 5 6 7

Acum orice rotatie a sirului initial este o subsecventa de lungime N al acestui sir.

L.E @Gabi Dap, scuze. N-am vazut.

Concatenand sirul la sfarsit mi se pare ca se foloseste un fel de sir suplimentar :)

Poti sa nu faci asta cu concatenarea, faci tot pe sirul V, te duci cu primul for de la K + 1 pana la N, si apoi de la 1 -> K :).

pai e ca si cu un sir suplimentar asa.
@SpiderMan cum zici tu e doar parcurgerea. eu nu vreau sa il parcurg ci sa ii rotesc elementele. la final daca afisez tot sirul sa am elementele rotite.

cum zicea gabitzish1 am gasit si eu o solutie, insa nu prea am inteles cum ziceai acolo.
tot interschimband valorile repetat din k in k pana ajungi de unde ai pornit e cea mai optima solutie.

Nu stiu cum sa'ti explic mai pe inteles... faci reverse la subsecventa [1 -> K], reverse la subsecventa [K+1 -> N], si reverse la tot sirul apoi (subsecventa [1 -> N]);

Pai faci ce-o zis Mihai, doar faci cum am zis eu, in loc de pozitia N + 1 .... 2N pui pozitiile din sirul initial :), teoretic nu e un sir suplimentar, ca nu-l declari (daca la asta se refera).

[LE] Cum a zis gabitzish1, e foarte bine si asa, ai chiar o functie in STL reverse care face asta lejer :).

@gabitzish1, acum am inteles, cred ca e cel mai simplu asa, la complexitate e la fel ca solutia care am gasit-o ultima data, ca se fac n interschimbari.

@SpiderMan cum zici tu inca raman pe pozitiile 1..k elemente care mie nu imi trebuie si cam sa le sterg trebuie facuti mai multi pasi si deja devine ineficient.

merge si cu hash-uri :-'

Nu prea.

ouch scuze, nu am citit bine, credeam ca trebuie aflat daca un sir e rotirea altuia, asa mergea cu hash-uri...  :oops:

Poti face permutari circulare la dreapta de k ori.
iata codul:
for(int i=1;i<=k;++i)
{
          aux=V[n];
      for(int j=2;j<=n;++j)   
{     
 V[1]=aux;
V[j]=V[j-1];
  }           
 }

complexitatea este insa de O(n*k)

la stanga nu le dreapta. Scuze! Greseala mea.