Sage’s Birthday

Given an array A let’s define minima as all an element that is smaller than both its neighbours a[i] < a[i+1] and a[i] < a[i-1].

Problem Statement

Given an Array A find an ordering that gives maximum minima’s.

Link to problem here.

Solution

The maximum number of minimas possible is n/2 — (n%2==0) call this M

Since we are looking at minimas it is optimal to sort the array and pick the first M elements and try to make them the minimas.

A1, A2, A3, A4, A5, A6, …….

Now what would be the ideal position to place these minimas.

A1 > A2 < A3 > A4 < A5 > A6 < A7 > …….

Above will be the most intuitive way. So the position to place the minimas will be in the even positions A2, A4, A6, A8 ……

Now for each minima we need to pick 2 elements that are greater than it.

Take the example 1,2,3,3,4,4,4,5,5,6,7,8,8,8,9,9 (if not sorted, sort it)

M here would be = 7 (16/2-(16%2==0))

We pick the first 7 as minimas (1,2,3,3,4,4,4), place them in all the even positions like we discussed above.

A1>1<A3>2<A5>3<A7>3<A9>4<A11>4<A13>4<A15, A16

note : we dont care about the equalty between A15 and A16

Stop here and convince yourself that this is the best possible ordering for minimas. And that the first M are the best suited minimas. If you are convinced by that then we can conclude that if we cannot make x of the M elements minimas then that is the maximum amount of minimas we can form from this Array of elements.

Since we need two elements for each minima we can pick the odd positions after picking the M maximas from the sorted order. Since the array is in sorted order we know that (first M elements) ≤ (upper n-m) elements. Therefore the ordering of the odd elements in the rest of the sorted elements doesn’t matter. And if we are not able to make some of the M elements minima, we conclude that it is simply impossible. Example

Say 1 2 2 2 3

A1 > 1 < A3 > 2 < A5

now we pick (A1,A3, A5) (2,2,3)

2 > 1 < 2 = 2 < 3 | 3 > 1 < 2 = 2 =2

as you can see the ordering of the odd elements doesn’t matter as long as we pick them after picking the M minimas from the sorted elements.

int main() {
    int n; cin>>n;
    vector<int>a(n,0);
    for(int i = 0; i < n; i++) cin>>a[i];
    sort(a.begin(),a.end());
    int j = 0;
    vector<int>b(n,0);
    for(int i = 1; i < n; i+= 2) {
        b[i] = a[j++];
    }    
    for(int i = 0; i < n; i+= 2) {
        b[i] = a[j++];
    }
    int ans = 0;
    for(int i = 1; i < n-1; i++) {
        if(b[i] < b[i-1] && b[i] < b[i+1]) ans++;
    }
    cout<<ans<<endl;
    for(auto v : b) cout<<v<<" ";
    cout<<endl;
    return 0;
}

You can find my notes here