PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given a permutation P.
You can pay one coin to perform the following move:
- Choose a non-empty subsequence of P that isn’t the whole of P.
- Sort all the elements in this subsequence in ascending order, then sort all elements outside the subsequence in descending order.
After the operations, you receive one coin for every i such that P_i = i.
Find the maximum possible profit.
EXPLANATION:
Since we’re allowed to choose any subsequence in our moves, with no constraint on length (other than it not being 0 or N), it’s always possible to obtain a pretty high profit.
In particular, consider the following sequence of moves:
- Let x be the index such that P_x = 1. Choose the subsequence \{1, x\} for the first move (note that it’s possible x = 1 so the subsequence will have length 1; that’s ok).
After this move, it’s guaranteed that P_1 = 1. - Next, choose the subsequence \{2, 3, 4, \ldots, N\}.
This will sort the elements at positions 2 to N in ascending order, and the element at position 1 in descending order (meaning P_1 won’t change).
But P_1 = 1, so P[2\ldots N] contains all the elements from 2 to N.
So, after the second move, the permutation will be [1, 2, 3, \ldots, N], i.e, it’ll be sorted.
We’ll receive N coins from this, and spent two, for an overall profit of N-2.
Since we can’t receive more than N coins, the only way to make a profit larger than N-2 is if the profit is N or N-1.
A profit of N is simple to check: we can’t make any moves at all, so P_i = i should hold for all i from the beginning.
As for a profit of N-1, there are two possibilities to achieve it:
- The initial P has exactly N-1 indices i such that P_i = i, and we make no moves.
- We use one move and make P_i = i for all i, obtaining N coins and spending one.
The first case is in fact impossible (if one element is out of place, then at least one more element must also be out of place), so only the second needs to be checked.
That is, we need to check if we can make one move that sorts a subsequence in ascending order and its complement in descending order, have P_i = i for all i.
P_i = i for all i means that P is sorted, so really we want to sort P.
In particular, note that if the subsequence we choose has size \lt N-1, then the remaining subset of size \geq 2 will be sorted in descending order - and because elements are distinct, this can never result in a sorted array.
So, our only hope is to choose to sort some subsequence of size N-1, since it’ll sort a single element in descending order (and hence not move this one element).
Suppose i is the single index excluded from the subsequence.
Then, if P_i = i the remaining elements will be sorted into their places; while if P_i \neq i then it’s not possible.
This gives us a rather simple check for when the answer can be N-1: at least one index should satisfy P_i = i.
Putting all the cases together, we obtain the following:
- If P_i = i for every i, the answer is N.
- Otherwise, if P_i = i for at least one i, the answer is N-1.
- If both above checks fail, the answer is N-2.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
in_place = 0
for i in range(n):
in_place += p[i] == i+1
if in_place == n: print(n)
elif in_place > 0: print(n-1)
else: print(n-2)