Official

C - Sort Subarray Editorial by en_translator Editorial for printing


Let \(X=(X _ 1,X _ 2,\ldots,X _ N)\) be the sequence obtained by sorting \(A _ 1,A _ 2,\ldots,A _ N\) in ascending order.

Suppose \(A\) became sorted in ascending order (i.e. coincided with \(X\)) by choosing some \(i\) to perform the operation. The values of \(A _ 1,A _ 2,\ldots,A _ {i-1}\) and \(A _ {i+K},A _ {i+K+1},\ldots,A _ N\) do not change by the operation, these must be equal to \(X\).

Conversely, if it holds for some \(i\) that \(A _ 1=X _ 1,A _ 2=X _ 2,\ldots,A _ {i-1}=X _ {i-1}\) and \(A _ {i+K}=X _ {i+K},A _ {i+K+1}=X _ {i+K+1},\ldots,A _ N=X _ N\), then performing the operation for such \(i\) makes \(A\) equal to \(X\).

Therefore, the following approaches, for example, can decide the answer:

  • Find the minimum \(i\) and maximum \(i\) such that \(A _ i\ne X _ i\), and check if their difference is strictly less than \(K\).
  • Perform the operation for the minimum \(i\) with \(A _ i\ne X _ i\), and check if \(A=X\).

Directly finding \(X\) requires sorting, which costs \(O(N\log N)\) time. While this is fast enough, but a clever reinterpretation of “the minimum \(i\) such that \(A _ i\ne X _ i\)” helps solving the problem in just \(O(N)\) time.

The following is sample code.

#include <iostream>
#include <vector>
#include <ranges>

int main() {
    using namespace std;
    unsigned N, K;
    cin >> N >> K;
    vector<unsigned> A(N);
    for (auto&& a : A) cin >> a;

    // The maximum i with A[i] != X[i] is the maximum i such that there exists j < i such that A[j] > A[i]
    unsigned prefix_max{}, max_i{};
    for (const auto& [i, a] : A | views::enumerate) {
        prefix_max = max(a, prefix_max);
        if (prefix_max > a) max_i = i;
    }

    // The minimum i with A[i] != X[i] is the minimum i such that there exists j > i such that A[i] > A[j]
    unsigned suffix_min{N}, min_i{N};
    for (const auto& [i, a] : A | views::enumerate | views::reverse) {
        suffix_min = min(a, suffix_min);
        if (suffix_min < a) min_i = i;
    }

    cout << (K + min_i > max_i ? "Yes" : "No") << endl;
    return 0;
}

posted:
last update: