MEDIANT - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You have an array A.
In one move, you can choose an odd-length subarray, and delete the leftmost occurrence of its median from it.
Find a sequence of operations that sorts A, or claim that this is impossible.

EXPLANATION:

Let \text{mn} denote the minimum element of A.
Observe that no matter which subarray you operate on,

  • If the median is \gt \text{mn}, obviously \text{mn} doesn’t get deleted from the array.
  • If the median is \text{mn}, then every element before the median (in sorted order) must also be equal to \text{mn}.
    The length of the subarray being \gt 1 means that at least one such element exists.
    So, even if one copy of \text{mn} gets deleted, A will still contain at least one more copy of \text{mn}.

This tells us that no matter how we perform the operations, at least one copy of \text{mn} will remain in A in the end.
In particular, since we delete the leftmost occurrence of A in a subarray, the rightmost occurrence of \text{mn} in A will never be deleted.

The exact same reasoning can be applied to the maximum element of A (call it \text{mx}).
That is, the rightmost occurrence of \text{mx} will not be deleted.

Let x be the largest index such that A_x = \text{mn}.
Let y be the largest index such that A_x = \text{mx}.

If x \gt y, then A can never be sorted - there will always be an occurrence of \text{mn} after \text{mx}.

On the other hand, if x \leq y, A can always be sorted.
The proof of this is in fact quite simple: you can perform literally any sequence of operations! (that reduces the array to length 2).

That is, while the array has length \gt 2, choose some subarray and operate on it.
This will reduce the length of the subarray by 1 - but as noted at the start, the rightmost occurrences of the minimum and maximum will remain.

So, when the array reaches length 2, the only remaining elements will be the rightmost occurrences of the minimum and maximum.
However, we’re in the case where the minimum appears before the maximum - so this 2-element array is certainly sorted!

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    last_mn = last_mx = 0
    for i in range(1, n):
        if a[i] >= a[last_mx]: last_mx = i
        if a[i] <= a[last_mn]: last_mn = i
    
    if last_mn > last_mx: print(-1)
    else:
        import random
        print(n-2)
        for i in range(n-2):
            # make a random valid move since it does not matter
            while True:
                l, r = random.randint(1, n-i), random.randint(1, n-i)
                if l == r or l%2 != r%2: continue
                print(min(l, r), max(l, r))
                break
2

Too much of cheating in unmedian problem with leaked YouTube code and changed variable names.

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

int32_t main() {
int test_cases;
cin >> test_cases;

while (test_cases--) {
    int array_size;
    cin >> array_size;

    vector<int> numbers(array_size);
    for (int i = 0; i < array_size; i++) {
        cin >> numbers[i];
    }

    vector<pair<int, int>> operations;
    bool is_sorted = false;

    while (true) {
        vector<int> temp_array = numbers;
        sort(temp_array.begin(), temp_array.end());

        if (numbers == temp_array) {
            is_sorted = true;
            break;
        }

        if (numbers.size() <= 2) {
            break;
        }

        operations.push_back({1, 3});
        vector<int> current_segment(numbers.begin(), numbers.begin() + 3);
        vector<int> sorted_segment = current_segment;
        sort(sorted_segment.begin(), sorted_segment.end());

        int median_value = sorted_segment[1];
        int position = find(current_segment.begin(), current_segment.end(), median_value) - current_segment.begin();

        numbers.erase(numbers.begin() + position);
    }

    if (is_sorted) {
        cout << operations.size() << endl;
        for (int i = 0; i < operations.size(); i++) {
            cout << operations[i].first << " " << operations[i].second << endl;
        }
    } else {
        cout << -1 << endl;
    }
}
return 0;

}

3

Submitted the following code during the contest for problem https://www.codechef.com/START157B/problems/MEDIANT:

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

It is showing wrong answer for the below input:
1
50
44 2 86 52 95 5 15 37 5 6 11 34 88 41 27 30 11 46 58 4 37 22 75 88 66 4 77 70 54 61 19 85 50 5 88 70 39 75 95 85 4 8 35 63 4 80 19 62 16 91

The array after performing the operations given by my code is: 2 95 95. Is the code accepted only when array size is reduced to 2 (i.e. K = n-2 in the output)? I am checking the array to be sorted instead of performing all n-2 operations to reduce the size to 2. Please help me identify the issue here?

4

Ae yo so much cheating happened in this problem, after the contest, I even saw a person live-streaming the answers on yt

5

++
same issue with my code too
https://www.codechef.com/viewsolution/1100970652

6 
else {
        ans.pb({1, a.size() - 1});
        int med = b[(a.size()-1)/2];
        //cout << "med " << med << endl;
        auto it = find(a.begin(), prev(a.end()), med);
        a.erase(it);
}

You aren’t computing the median correctly in this case.
b[(a.size()-1)/2]; is the median of the entire array, but the operation you perform is not on the entire array - it’s excluding the last element. This can change the median, so you might end up deleting the wrong element by mistake and then all future steps will be wrong.

For a simple example, run your code on

1
4
1 3 3 2
7

You aren’t computing indices correctly.

1
4
1 2 1 2
8

Thanks for replying,
how about this one
https://www.codechef.com/viewsolution/1101084752

9

It fails on the case I provided in the previous comment,

1
4
1 3 3 2
10

Got it
thanks

11

can some one explain it in better way , i am not able to understand the editorial or guide me what are the topic/things i need to improve to become able to solve 4th question of div3
i am constantly struggling at 4th question of div 3 .
can some guide me how to improve from this point