Блог пользователя shah_entrance

Minimum number of operation to sort an array
Автор shah_entrance, история, 5 лет назад, По-английски

Given an array. Find the minimum number of operation to sort the array. Operation: Take element from any position of the array and put it to end.

  • Проголосовать: нравится
  • -7
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For each element of the array, calculate what would its position be if we sort the array (let pos[i] be the position of element i in a sorted array). Then, find the maximum value x such that all the elements which have pos <= x are sorted (for example, let the array be [3, 4, 1, 2, 5]. Maximum x = 2 because 1 and 2 are sorted (2 is behind 1), but 3 is before 1 and 2 (so 1, 2 and 3 are not sorted)). In the end you just put all the other elements to the end of the array (in the correct order, of course). So, minimum number of operations is N (number of elements in the array) — x.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can u explain to me for this example [6,1,3,2,5,4] ?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      For that example, x = 2 because numbers 1 and 2 are "sorted" (1 is before 2 in the array), but 3 is before 2 so 1, 2 and 3 are not "sorted". So the answer is 4 (you put 3, 4, 5 and 6 to the end of the array).

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 
solve(vector<int>arr){
int st=0;
vector<int>v;
v=arr;
int ans=0;
int n=v.size();
sort(v.begin(),v.end());
for(int i=0;i<n;i++){
int req=v[i];
while(st<n && arr[st]!=req){
st++;
ans++;
}
st++;
if(st>=n){
break;
}
}
return ans;
}
→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I had made this question for a round on CodeChef. Here is the editorial.

→ Ответить
  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    recently i have given an Online Assessment in which i have been asked same question with a little change Given an array of distinct elements, you need to sort it in non-decreasing order using only two operations:

    Take an element and move it to the start.
Take an element and move it to the end.

    please help. thank you

    → Ответить
    • »
      »
      »
      5 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится 
      Im not sure, but that could work:

the solution is similar for [this comment](https://mirror.codeforces.com/blog/entry/68102?#comment-524186), but in this comment you count sort pref in a

in my solution for each 0<=i<=n you count:

pref_ans - sort in a[0:i]

suf_ans - sort in a[i+1:n], but we starting with i(suf_sort(3) [1 3 5 4]=2)

and ans=n-pref_ans-suf_ans;

for example:

[3 1 4 2]

for i=0: pref_ans=0; suf_ans=2; ans=2;

for i=1: pref_ans=0; suf_ans=0; ans=4;

for i=2: pref_ans=1; suf_ans=0; ans=3;


for i=3: pref_ans=1; suf_ans=0; ans=3;

for i=4: pref_ans=2; suf_ans=0; ans=2;

final_ans=min(all ans)=2
      → Ответить