ARRAYSORTING Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

2349

PREREQUISITES:

None

PROBLEM:

Let A be a permutation of \{1,2,3, \dots, N\}.

We define a function f(A) as the minimum number of increasing subarrays into which the permutation A can be partitioned.
For example f(\{5, 1, 4, 2, 3\}) = 3, as the minimum number of increasing subarrays it can be partitioned into is 3. The partitions are: \{5\}, \{1, 4\}, and \{2, 3\}.

Chef has a permutation P of \{1,2,3, \dots, N\}.
Chef wants to sort the permutation P. For that, he can choose any two indices (i, j) (1 \leq i \lt j \leq N) and swap the elements P_i and P_j such that the value of f(P) does not increase after the swap.

Help Chef sort the permutation in at most N^2 swaps.

EXPLANATION:

In order to sort the permutation P we will first take the first two increasing sequences of the array. In case the array has only one increasing sequence then that implies that the array is already sorted. Now after selecting the first two increasing sequences, we will sort them to make it a single increasing sequence. Again we will repeat the operation of selecting first two increasing sequences and sorting it till the whole array is sorted.

Now let’s talk about how we will sort the first two increasing sequences, say L and R. We will select the largest element from R, say r that is smaller than the largest element of L, then using binary search we find the smallest element in L that is larger than r and swap the two. By repeatedly following this operation we can sort L and R into a single increasing sequence without increasing f(P) and in atmost N^2 swaps.

TIME COMPLEXITY:

O(N^2log(N))

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

1 Like
2

Weak Testcases! Some people simply submitted simple bubble sort and it passed lol
https://www.codechef.com/viewsolution/66933868

3 Likes
3

why would bubble sort not be correct? As long as you move the minimum-, non-sorted-value left, you are doing it right.
If anything I thought this problem was far too easy

1 Like
4

Why should bubble sort fail? :thinking:

1 Like
5

for this tc I think
5
4 5 1 2 3

2 Likes
6

@master_mind14 @termii how would you apply bubble sort on the permutation “3 4 1 2”? Bubble sort would swap 1 and 4. Initially, there are 2 subarrays (34 and 12), after swapping, we get (3, 14, 2) which violates the condition.

3 Likes
7

Hi, sorry there was issue in the checker.
One condition was missing in the judge while dealing with adjacent swaps. I have corrected the judge. Bubble sort will now get WA.

1 Like
8

Bubble sort approach is not correct. There was some issue in the judge. I have corrected the judge. You can resubmit your solution

1 Like
9

There is one nice and easy solution to this problem:

Read my code first (Code is self explainatory) : https://www.codechef.com/viewsolution/66969887

Now why it’s working?
Reason : There can be atmax nC2 inversion <= n^2, and in each step we are decreasing the count by atleast 1.

But won’t it increase the count of increasing subarrays?
Ans: No, because I am swapping the consecutive numbers since, the condition was k+1 should be placed before k then we will swap. You can take some examples to understand it better, I will try to explain why it’s working :slight_smile: :
The elements before k will not be affected as we are placing k+1 instead of k. If k is the last element of its increasing subarray, then also placing k+1 will not affect the total count. Now, we are left with just one case, i.e, k is not the last element in its increasing subarray, so let the element after k be x.

x>k
k+1 is already to the left of k, so we can say that x>k+1
Therefore, in this case, as well, it won’t be increasing the total count of increasing subarrays.
You can do similar reasoning for the k+1 element.

4 Likes
10

Bubble sorting is clearly wrong, the min. no of increasing sequences exactly equals no of pairs (i,i+1) such that Ai>Ai+1. (Call these bad pairs)

Let there be 4 adjacent numbers, A B C D having C as the minimum and A<B and D<B and then bubble sort will involve swapping B and C, which increases the no. of pairs such that Ai>Ai+1

Anyways, there’s a simpler O(N^2) solution. Suppose my subarray [i+1, N] is already sorted (with correct elements, i.e. at index j>i, A(j) = j).

Then I have to place correct element at ith position. If A(i) = i, then we’re done, otherwise, A(i)<i (A(i) can’t be greater than i because I have already placed all the greater elements at their correct positions!)

So loop through index 1 to i-1, and find the index k such that A(k) = A(i)+1, simply swap A(k) and A(i). Keep on doing this, until you eventually place element i at index i.

Why this works? Well, proof is left as an excercise to the reader (i love saying this :P)

My Code: CodeChef: Practical coding for everyone

1 Like
11

There is also an O(n^2) solution.
We will use two pointers, a left pointer from 0 to n-1 and a right pointer from n-1 to 0.
If val[left]>val[right] we swap.

This approach works, because we are swapping the left pointer with a smaller value.
If [a, b, c] is an increasing subarray then [x, b, c] will also be an increasing subarray, if x<=a.
Similarly, for the right pointer we are swapping it with a greater value, if [x, y, z ] is an increasing subarray, then [x, y, k] will also be an increasing subarray, if k>=z.

for(ll l = 0;l<n;l++){
        ll r = n-1;
        while(l<r){
            if(arr[l]>arr[r]){
                swap(arr[l], arr[r]);
                moves.push_back({l+1, r+1});
            }
            r--;
        }
    }
12

Solved using one pass and O(n2) complexity.

https://www.codechef.com/viewsolution/66872101

13

One nice O(n^2) approach-
Starting from n to 1. At index i keep swapping arr[i] and arr[i]+1, until arr[i] becomes i.

Code

14

I tried selection sort, basically swapping the highest element to the last of the array each time.
Like for example 5 1 4 2 3,
steps : 5 1 4 2 3 → 3 1 4 2 5 → 3 1 2 4 5 → 2 1 3 4 5 → 1 2 3 4 5
f(P) : -----3-------------3---------------2----------------------2---------1
my solution: CodeChef: Practical coding for everyone
I am getting AC for 4 test cases and WA for 4 test cases, some chef please help my find my mistake

15

u cant do that. Consider 1 4 5 2 3 → 1 4 3 2 5 . f(P) increased from 2 to 3. Instead swap 3 with 4 first and then 4 with 5.

16

Repeat this block n times
[
swap the elements that have values n and n-1 (if needed)
then n-1 and n-2
then n-2 and n-3
.
.
.
then 2 and 1
]

Solution: 66982178 | CodeChef

17

Can you explain your approach?

18

Another Approach can Be :
Combine the last two increasing subarrays as one increasing subarray.
Like For : 4 1 5 2 3, we take last increasing subarray s1 = [2, 3] and second last increasing subarray s2 = [1, 5] and combine to make then [1, 2, 3, 5], by

Taking ith index from the start of s1 and finding index( j ) in s2 from last such that

  • s2[j] < s1[i]
  • j > i.

Then swap these indexes as after the operation the number of increasing subarray can only decrease or remain same.

Code 
#define ll long long
#define V vector

void solve(){
    ll n;
    cin >> n;
    V<ll> v(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];
    ll k = n-1, i = n-1;
    V<pair<ll,ll>> res;
    while(k > 0){
        if(v[k] > v[k-1]){
            k--;
            continue;
        }
        if(i >= k){
            i = k-1;
            while(i > 0 && v[i] > v[i-1])
                i--;
        }
        ll j = n-1;
        while(j > i && v[j] > v[i]){
            j--;
        }
        if(j == i)
            i++;
        else if(j > i){
            res.pb({i,j});
            swap(v[i], v[j]);
        }
    }
    cout << res.size() << '\n';
    for(auto [i,j] : res)
        cout << i+1 << ' ' << j+1 << '\n';
}
19

Will it recheck the submissions too?

20

We will not rejudge any contest submissions (As it will affect the ranklist).

We have rejudged all the submissions made after the end of the contest