AOI Study Hub

Appearance

Nelward ​

Written by Redhouane Abdellah.

Problem Statement ​

Solution ​

  • Let such that:

    • . Notice that has to be moved in front of if we want to sort the permutation, meaning every element in front of also has to be moved.

  • Let be the smallest index such that for all .

    The previous observation tells us that all elements before have to be moved, i.e.Âthe answer is at least

  • Notice how it is possible to move an element into any position when performing an operation on it.

    We can do the following times: move the first element into a new position such that the suffix starting at stays sorted.

    Notice that after all operations the permutation is guaranteed to become sorted, hence the answer is always .

Implementation ​

  • We can implement this in time and space by doing the following:

    Traverse the array backwards starting from the th element, and set .

    As long as we keep traversing the array while decrementing each time.

    As soon as the condition isn't met we stop decrementing and traversing the array.

cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    vector<int> p(n);
    for (auto &i : p) cin >> i;
    int k = n;
    for (int i = n-2; i >= 0; --i) {
        if (p[i] < p[i+1]) --k;
        else break;
    }
    cout << k-1;
}

  • We can reduce the space complexity to by doing the following:

    Set , let .

    Then for all : let .

    If , we set (because now the left endpoint of the longest increasing suffix is guaranteed to be ), and then set before moving to .

    Here's the code for it:

cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    int a, b;
    cin >> a;
    int k = 1;
    for (int i = 2; i <= n; ++i) {
        cin >> b;
        if (a > b) k = i;
        a = b;
    }
    cout << k-1;
}