Overview

This problem asks you to determine whether the current permutation \(p\) can be made equal to the target permutation \(q\) by performing exactly one interval reversal operation.

Analysis

Key Insight

For \(p\) to match \(q\) after reversing the interval \([L, R]\), the following two conditions must hold:

1. Outside the interval: For the parts that are not reversed, \(p_i = q_i\) must hold
2. Inside the interval: The reversed part must match \(q\)

In other words, the positions where \(p\) and \(q\) differ must form a contiguous interval, and reversing that interval must make it match \(q\).

Concrete Example

For \(p = [1, 5, 4, 3, 2, 6]\) and \(q = [1, 2, 3, 4, 5, 6]\):

• The positions where \(p\) and \(q\) differ are \(i = 1, 2, 3, 4\) (0-indexed)
• The elements of \(p\) in the interval \([1, 4]\) are \([5, 4, 3, 2]\)
• Reversing this gives \([2, 3, 4, 5]\), which matches the same interval \([2, 3, 4, 5]\) in \(q\)
• Therefore the answer is Yes

Problem with the Naive Approach

If we try all pairs \((L, R)\) and check whether the reversal results in a match, it takes \(O(N^2)\), which will TLE for \(N \leq 10^6\).

Solution

If we find the leftmost position \(L\) and rightmost position \(R\) where \(p\) and \(q\) differ, the interval to reverse is uniquely determined as \([L, R]\). Then we only need to verify that interval.

Algorithm

1. Compare \(p\) and \(q\), and let \(L\) be the minimum \(i\) where \(p_i \neq q_i\), and \(R\) be the maximum such \(i\)
2. If \(p_i = q_i\) at all positions (i.e., \(L\) is not found), they already match without any reversal, so output Yes (the operation with \(L = R\) changes nothing)
3. Otherwise, check whether reversing \(p[L..R]\) results in a match with \(q[L..R]\)
   • Specifically, verify that \(p[L + R - i] = q[i]\) for all \(i\) (\(L \leq i \leq R\))
4. If they match, output Yes; otherwise, output No

Complexity

• Time complexity: \(O(N)\) — we only scan the array at most twice
• Space complexity: \(O(N)\) — needed to store the input

Implementation Notes

• The search for \(L\) and \(R\) can be done simultaneously in a single scan (the first mismatch found is \(L\), and the last mismatch found is \(R\))

• For the reversal verification, there is no need to actually reverse the array; simply compare \(p[j]\) (with \(j\) decreasing from \(R\) to \(L\)) with \(q[i]\) (with \(i\) increasing from \(L\) to \(R\))

• When \(p = q\), the operation of “choosing \(L = R\) and changing nothing” is permitted, so we output Yes

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<int> p(N), q(N);
    for(int i=0;i<N;i++) cin >> p[i];
    for(int i=0;i<N;i++) cin >> q[i];
    
    int L = -1, R = -1;
    for(int i=0;i<N;i++){
        if(p[i]!=q[i]){
            if(L==-1) L=i;
            R=i;
        }
    }
    
    if(L==-1){
        cout << "Yes" << endl;
        return 0;
    }
    
    // Check if reversing p[L..R] gives q
    for(int i=L, j=R; i<=R; i++, j--){
        if(p[j]!=q[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    return 0;
}

---

This editorial was generated by claude4.6opus-thinking.