array median transformation minimum steps

Question

Given an array A with n integers. In one turn one can apply the following operation to any consecutive subarray A[l..r] : assign to all A i (l <= i <= r) median of subarray A[l..r] . Let max be the maximum integer of A . We want to know the minimum number of operations needed to change A to an array of n integers each with value max. For example, let A = [1, 2, 3] . We want to change it to [3, 3, 3] . We can do this in two operations, first for subarray A[2..3] (after that A equals to [1, 3, 3] ), then operation to A[1..3] . Also,median is defined for some array A as follows. Let B be the same array A , but sorted in non-decreasing order. Median of A is B m (1-based indexing), where m equals to (n div 2)+1 . Here 'div' is an integer division operation. So, for a sorted array with 5 elements, median is the 3rd element and for a sorted array with 6 elements, it is the 4th element.

Since the maximum value of N is 30.I thought of brute forcing the result could there be a better solution.

Answer 1

You can double the size of the subarray containing the maximum element in each iteration. After the first iteration, there is a subarray of size 2 containing the maximum. Then apply your operation to a subarray of size 4, containing those 2 elements, giving you a subarray of size 4 containing the maximum. Then apply to a size 8 subarray and so on. You fill the array in log2(N) operations, which is optimal. If N is 30, five operations is enough.

This is optimal in the worst case (i.e. when only one element is the maximum), since it sets the highest possible number of elements in each iteration.

Update 1: I noticed I messed up the 4s and 8s a bit. Corrected.

Update 2: here's an example. Array size 10, start state:

[6 1 5 9 3 2 0 7 4 8]

To get two nines, run op on subarray of size two containing the nine. For instance A[4…5] gets you:

[6 1 5 9 9 2 0 7 4 8]

Now run on size four subarray that contains 4…5, for instance on A[2…5] to get:

[6 9 9 9 9 2 0 7 4 8]

Now on subarray of size 8, for instance A[1…8], get:

[9 9 9 9 9 9 9 9 4 8]

Doubling now would get us 16 nines, but we have only 10 positions, so round of with A[1…10], get:

[9 9 9 9 9 9 9 9 9 9]

Update 3: since this is only optimal in the worst case, it is actually not an answer to the original question, which asks for a way of finding the minimal number of operations for all inputs. I misinterpreted the sentence about brute forcing to be about brute forcing with the median operations, rather than in finding the minimum sequence of operations.

Answer 2

This is the problem from codechef Long Contest.Since the contest is already over,so awkwardiom ,i am pasting the problem setter approach (Source : CC Contest Editorial Page).

"Any state of the array can be represented as a binary mask with each bit 1 means that corresponding number is equal to the max and 0 otherwise. You can run DP with state R[mask] and O(n) transits. You can proof (or just believe) that the number of statest will be not big, of course if you run good DP. The state of our DP will be the mask of numbers that are equal to max. Of course, it makes sense to use operation only for such subarray [l; r] that number of 1-bits is at least as much as number of 0-bits in submask [l; r], because otherwise nothing will change. Also you should notice that if the left bound of your operation is l it is good to make operation only with the maximal possible r (this gives number of transits equal to O(n)). It was also useful for C++ coders to use map structure to represent all states."

The C/C++ Code is::

#include <cstdio>
#include <iostream>
using namespace std;

int bc[1<<15];
const int M = (1<<15) - 1;

void setMin(int& ret, int c)
{
    if(c < ret) ret = c;
}

void doit(int n, int mask, int currentSteps, int& currentBest)
{
    int numMax = bc[mask>>15] + bc[mask&M];
    if(numMax == n) {
        setMin(currentBest, currentSteps);
        return;
    }
    if(currentSteps + 1 >= currentBest)
        return;
    if(currentSteps + 2 >= currentBest)
    {
        if(numMax * 2 >= n) {
            setMin(currentBest, 1 + currentSteps);
        }
        return;    
    }  

    if(numMax < (1<<currentSteps)) return;

    for(int i=0;i<n;i++) 
    {
        int a = 0, b = 0;
        int c = mask;
        for(int j=i;j<n;j++)
        {
            c |= (1<<j);
            if(mask&(1<<j)) b++;
            else a++;
            if(b >= a) {
                doit(n, c, currentSteps + 1, currentBest);
            }
        }
    }
}

int v[32];
void solveCase() {
    int n;
    scanf(" %d", &n);
    int maxElement = 0;
    for(int i=0;i<n;i++) {
        scanf(" %d", v+i);
        if(v[i] > maxElement) maxElement = v[i];
    }
    int mask = 0;
    for(int i=0;i<n;i++) if(v[i] == maxElement) mask |= (1<<i);
    int ret = 0, p = 1;
    while(p < n) {
        ret++;
        p *= 2;
    }
    doit(n, mask, 0, ret);
    printf("%d\n",ret);
}

main() {
    for(int i=0;i<(1<<15);i++) {
        bc[i] = bc[i>>1] + (i&1);
    }
    int cases;
    scanf(" %d",&cases);
    while(cases--) solveCase();
}

Answer 3

The problem setter approach has exponential complexity. It is pretty good for N=30. But not so for larger sizes. I think, it's more interesting to find an exponential time solution. And I found one, with O(N⁴) complexity.

This approach uses the fact that optimal solution starts with some group of consecutive maximal elements and extends only this single group until whole array is filled with maximal values.

To prove this fact, take 2 starting groups of consecutive maximal elements and extend each of them in optimal way until they merge into one group. Suppose that group 1 needs X turns to grow to size M, group 2 needs Y turns to grow to the same size M, and on turn X + Y + 1 these groups merge. The result is a group of size at least M * 4. Now instead of turn Y for group 2, make an additional turn X + 1 for group 1. In this case group sizes are at least M * 2 and at most M / 2 (even if we count initially maximal elements, that might be included in step Y). After this change, on turn X + Y + 1 the merged group size is at least M * 4 only as a result of the first group extension, add to this at least one element from second group. So extending a single group here produces larger group in same number of steps (and if Y > 1, it even requires less steps). Since this works for equal group sizes (M), it will work even better for non-equal groups. This proof may be extended to the case of several groups (more than two).

To work with single group of consecutive maximal elements, we need to keep track of only two values: starting and ending positions of the group. Which means it is possible to use a triangular matrix to store all possible groups, allowing to use a dynamic programming algorithm.

Pseudo-code:

For each group of consecutive maximal elements in original array:
  Mark corresponding element in the matrix and clear other elements
  For each matrix diagonal, starting with one, containing this element:
    For each marked element in this diagonal:
      Retrieve current number of turns from this matrix element
      (use indexes of this matrix element to initialize p1 and p2)
      p2 = end of the group
      p1 = start of the group
      Decrease p1 while it is possible to keep median at maximum value
      (now all values between p1 and p2 are assumed as maximal)
      While p2 < N:
        Check if number of maximal elements in the array is >= N/2
          If this is true, compare current number of turns with the best result \
               and update it if necessary
          (additional matrix with number of maximal values between each pair of
            points may be used to count elements to the left of p1 and to the
            right of p2)
        Look at position [p1, p2] in the matrix. Mark it and if it contains \
            larger number of turns, update it
        Repeat:
          Increase p1 while it points to maximal value
          Increment p1 (to skip one non-maximum value)
          Increase p2 while it is possible to keep median at maximum value
        while median is not at maximum value

To keep algorithm simple, I didn't mention special cases when group starts at position 0 or ends at position N, skipped initialization and didn't make any optimizations.