REVMX - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Prefix sums, sorting, (optional) binary search

PROBLEM:

You’re given a permutation. You can reverse at most one subarray.
Maximize the number of indices with P_i = i.

EXPLANATION:

Let x_i denote the position of the value i in the permutation, i.e. P_{x_i} = i.

Suppose we decide to reverse the range [L, R].
Let’s analyze which indices will be fixed afterwards.

There are two possible cases:

  1. i \lt L or i \gt R
    These indices are outside the reversed subarray, and hence aren’t modified at all.
    They will satisfy P_i = i if and only if it was initially the case.
  2. L \le i \le R
    Due to reversal, the element that was initially at index j will move to index R - (j-L).
    So, if P_i = i after the reversal, then value i must have been present at position R - i + L beforehand.
    That is, we must have had x_i = R - i + L, or x_i + i = L+R.

Because of the second point, we can group elements by their (x_i + i) values; and then whenever we choose some (L, R) it’s easy to tell which elements will be fixed: everything that satisfies x_i + i = L+R and L \le i \le R, as well as all existing fixed points outside the range.
Note that any fixed points in the range that don’t satisfy the condition will become non-fixed points after the reversal, so it’s not always optimal to make [L, R] as large as possible.

The next question is, which choice of (L, R) should we test? There are \mathcal{O}(N^2) of them, so clearly not every one.

However, note that if we choose to reverse [L, R], and neither L nor R are fixed by it, then we could just as well have reversed [L+1, R-1] instead and gotten the same result (potentially even a better result, if L and/or R were fixed before the reversal.)

Thus, we only need to focus on reversals that fix at least one endpoint.

Let’s now fix an element i.
There is only one subarray reversal that both has i as an endpoint and will fix element i - namely the subarray with endpoints i and x_i.

The score when reversing this subarray is not hard to compute:

  • Everything outside the the subarray that was already fixed, will remain fixed.
    This count can be computed using prefix sums on the fixed positions.
  • All elements within the subarray that were initially fixed, will become not-fixed after the reversal (except maybe the center.)
    Again, this count can be found using the aforementioned prefix sums.
  • Then, we also need to add in elements that become fixed by the reversal.
    As seen earlier, this is exactly those elements j that satisfy both:
    • x_i + i = x_j + j, and
    • \min(i, x_i) \le j \le \max(i, x_i)
      This can be easily counted using binary search for example, after grouping elements based on x_j + j and sorting them beforehand.

Thus, for a fixed i we can compute the resulting score in \mathcal{O}(\log N) after some precomputation.

Do this for every element to obtain a solution in \mathcal{O}(N\log N) which is fast enough.

Alternately, you can fix the value of x_i + i and then go over elements in increasing order of \max(i, x_i), which will remove the need for binary search entirely since it acts like starting with the center of a subarray and continually expanding both sides simultaneously.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    p = list(map(int, input().split()))
    
    pref = [0]
    events = [ [] for _ in range(2*n + 10) ]
    for i in range(n):
        pref.append(pref[-1] + (p[i] == i+1))
        events[i + p[i]-1].append(max(i, p[i]-1))
    
    ans = pref[-1]
    
    best = 0
    for i in range(2*n + 10):
        profit = 0
        for r in sorted(events[i]):
            l = i - r
            profit += 1
            best = max(best, profit - (pref[r+1] - pref[l]))
    print(ans + best)
1 Like