RBGM - Editorial

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:

  1. 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.
  2. 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:

  1. The initial P has exactly N-1 indices i such that P_i = i, and we make no moves.
  2. 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:

  1. If P_i = i for every i, the answer is N.
  2. Otherwise, if P_i = i for at least one i, the answer is N-1.
  3. 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)

Good problem. If you read it initially, then it looks daunting. But with some time and observation, its doable.

1 Like

[5,4,3,2,1]
can you explain how above array can be sorted in 1 move and
array [5,4,2,3,1] in 2 moves?

Same Question, Here it should be N-3 as we can’t choose the length of N which the editorial is choosing.
Please reconsider this Solution !

@iceknight1093
Please check the condition when :

  • No element is at its right position such that Pi != i ( for all, 1 <= i <= N).

  • N element is at position 1.

  • 1 is at position N.

If all the above conditions are true, then the answer would be N - 3.

For e.g: {5, 4, 2, 3, 1}

It’s all explained in detail in the editorial.

[5, 4, 3, 2, 1]: Choose S = \{1, 2, 4, 5\} and it’ll become [1, 2, 3, 4, 5].

[5, 4, 2, 3, 1]: Choose S = \{1, 5\} and it’ll become [1, 4, 3, 2, 5], now choose S = \{2, 3, 4, 5\} and it’ll become [1, 2, 3, 4, 5].

Where is a length of N being chosen?

1 Like

When we sort the array finally why did we stop doing operations? for 1,2,3,4,5 cant I choose 2,3,4,5 and perform operation again to get profit of 4. And cant this be done forever?
“Here, profit means the number of coins you receive, minus the number of coins you spent on operations.” According to this statement we can do that right.

From the statement: “After performing all the operations you wish to perform, you will receive one coin for every index i such that P_i = i.”

You receive coins only once, at the end after all operations - not after each operation.

Ohhh, thanks got it.

@iceknight1093
For a test-case like 4 3 2 1 6 5, can’t we pick indices 0, 1, 2, 3 sort them in ascending order and remaining 4, 5 in descending order so our final coins become 5 (because we performed only one operation and the array becomes sorted) but instead your solution code shows 4 coins ?
Or am I approaching it in a wrong way ?

If you sort two indices(4 and 5) in descending order, how will the array be sorted in ascending order? :slightly_smiling_face:

1 Like

Now I know why I am 2*