In a row is a class of N students. You need to photograph the students, but for aesthetic reasons you want them to be ordered in order of growth. To achieve this, you can tell an adjacent group of students to change their positions. Your goal is to find the minimum number of students in an adjacent group who, after rearranging their positions, will result in the entire series being ordered in height.

The current location of students is given by array A, in which the element A K records the height of the student in position K. After the permutation, the students must be sorted in the order in which the height does not decrease. Those. A P ≤ A P + 1 for any 0 ≤ P <N-1.

For example, if array A has the following form:

A [0] = 1 A [1] = 2 A [2] = 6 A [3] = 5 A [4] = 5 A [5] = 8 A [6] = 9

The smallest group of students that need to be rearranged is A [2..4], length 3. After regrouping this group, we obtain [1,2,5,5,6,8,9], which is in the correct order. Any other permutation involving a contiguous group of less than three students will not result in the correct sorting of the resulting string.

The solution must contain a function that receives array A, containing the difference in height between the student and the photographer, and returns the minimum number of students in an adjacent group, after sorting which the entire array will be sorted. If the student array is already ordered, the function should return 0.

For example, for array A described above, the function should return 3.

 Предположим, что: 1. N - целое число в диапазоне [1. 100 000] 2. каждый элемент массива А является целым числом в диапазоне [1. 100 000 000].

I would like to see your solution, preferably on JS (I am studying it).

Closed due to the fact that the essence of the question is not clear to the participants vp_arth , Nicolas Chabanovsky ♦ Mar 16 '17 at 10:11 .

Try to write more detailed questions. To get an answer, explain what exactly you see the problem, how to reproduce it, what you want to get as a result, etc. Give an example that clearly demonstrates the problem. If the question can be reformulated according to the rules set out in the certificate , edit it .

  • The first thought - stupidly in the forehead - we sort; The desired range is between the first and last mismatches of an unsorted and sorted array ... But this is O (n log n) + O (n) memory. - Harry
  • @vp_arth The question is clear, and I have another solution. Please reopen. - Yuri Negometyanov
  • @Nicolas Chabanovsky The question is clear, and I have a different solution. Please reopen. - Yuri Negometyanov
  • @YuriNegometyanov, you have enough reputation to rule the question. In the current form - this is offtopic. There is no place for ready-made solutions to the problems. The question is not that incomprehensible - there is no question. - vp_arth
  • @vp_arth thanks for the advice, edit made. And to solve an interesting puzzle is not a sin, even here. Moreover, there are almost no questions on the algorithms - Yuri Negometyanov

1 answer 1

The first thought - stupidly in the forehead - we sort; The desired range is between the first and last mismatches of an unsorted and sorted array ... But this is O (n log n) + O (n) memory. Although n times to 100,000 is very little.

C ++ Code:

 #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { constexpr int N = 100000; vector<int> A(N); for(size_t i = 0; i < N; ++i) A[i] = rand(); for(int i = rand(); i >= 0; --i) A[i] = i; for(int i = N - rand(); i < N; ++i) A[i] = i; vector<int> B(A); sort(B.begin(),B.end()); int b, e; for(b = 0; b < N && A[b]==B[b]; ++b); if (b == N) { cout << "0\n"; return 0; } for(e = N-1; e >= 0 && A[e]==B[e]; --e); cout << (e-b+1) << "\n"; }

Well, to really see, check - here:

 int main() { srand(time(0)); constexpr int N = 10; vector<int> A(N); for(size_t i = 0; i < N; ++i) A[i] = rand()%10; for(int i = rand()%4; i >= 0; --i) A[i] = i; for(int i = N - rand()%4; i < N; ++i) A[i] = i; vector<int> B(A); sort(B.begin(),B.end()); int b, e; for(b = 0; b < N && A[b]==B[b]; ++b); if (b == N) { cout << "0\n"; return 0; } for(e = N-1; e >= 0 && A[e]==B[e]; --e); cout << (e-b+1) << "\n"; for(auto i: A) cout << i << " "; cout << endl; for(auto i: B) cout << i << " "; cout << endl; }

Results like

 7 0 1 5 6 6 4 1 5 1 9 0 1 1 1 4 5 5 6 6 9