5
$\begingroup$

Let $A[1...N]$ be an Array of size $N$ with maximum element $\max$.

I want to transform array $A$ such that after transformations all elements of $A$ contain $\max$, i.e. after transformation $A = [\max,\max,\max,\max,\dots,\max]$.

In one step, I can apply the following operation to any consecutive sub-array $A[x..y]$:

Assign to all $A[i]$ with $x \leq i \leq y$ the median of subarray $A[x..y]$.

We consider as median always the $\left\lceil \frac{n+1}{2} \right\rceil$-th element in an increasingly sorted version of $A$.

What is the minimum number of steps needed to transform $A$ as desired? If it helps, assume that $N\leq 30$.


Example 1:

Let $A = [1, 2, 3]$. We need to change it to $[3, 3, 3]$. The minium number of steps is two, first for subarray $A[2..3]$ (after that $A$ equals to $[1, 3, 3]$), then operation to $A[1..3]$.

Example 2:

$A=[2,1,1,2]$.The min step is two. The median of subarray $A[1..4]$ is $2$ (3rd element in $[1,1,2,2]$. Apply the operation to $A[1..4]$ once and we get $[2,2,2,2]$.

$\endgroup$
  • 2
    $\begingroup$ It seems the upper bound is $\lceil \log_2 n \rceil$. It's tight when the max element is unique. $\endgroup$ – Wu Yin May 9 '12 at 7:16
  • $\begingroup$ @ Wu Yin : Sorry i didn't get you.Can You please share your Approach? Thanks! $\endgroup$ – Jack May 9 '12 at 7:23
  • $\begingroup$ I can only find the upper bound. I means, the answer cannot exceed $\lceil \log_2 n \rceil$ whatever the sequence is. Since $n \leq 30$ in your problem, I guess you can try to enumerate all possible operations. But it's not a polynomial algorithm when $n$ is larger. $\endgroup$ – Wu Yin May 9 '12 at 7:29
  • $\begingroup$ @WuYin :: The Max size of N is 30 only .How can i enumerate all possible operations? $\endgroup$ – Jack May 9 '12 at 7:33
  • 1
    $\begingroup$ The upper bound is 5 when $n = 30$. You can enumerate all 5 intervals and check whether they can achieve your goal. Though the number of possible operations can be O(n^10), most of them are useless and can be pruned easily, so it can run much faster than its theoretical worst running time. $\endgroup$ – Wu Yin May 9 '12 at 7:40
4
$\begingroup$

In the comments, Wu Yin claimed an upper bound of $\lceil \log_2 n \rceil$, although I think this is only true if the position of the maximum is known. In fact, consider the following argument. Assume $A$ is filled with $N-1$ ones and one maximal element $\max$. Any first step on a subarray $A[x,y]$ of more than 2 elements will necessarily set the subarray to all $1$'s. In particular, if we don't know the position of $\max$, we can only apply a step to subarrays of length 2, or otherwise we run the risk of "destroying" our maximum element. Hence, without knowing the position of our maximimal element, we can only probe the array by consecutively applying the operation to $A[i,i+1]$ for all $i$. This will necessarily create a subarray of length 2 that is filled with $\max$. Recurring leads to a linear time algorithm, which I think is optimal.

Algorithm:

Let $step(x,y)$ denote an operation on the subarray $A[x,y]$ as is defined in the question.

  • Perform $step(i,i+1)$ for all $0\leq i < N$. After that, there is some 2-length subarray containing only $\max$.

  • Perform $step(i,i+3)$ for all $0\leq i < N-3$. After that, there is some 4-length subarray filled with $\max$.

  • Generally, we double in each such iteration the array size in each step. After that, the original array $A$ contains only $\max$.

Running Time:

In the first iteration, we perform $N/2$ steps, in the subsequent one, $N/4$, then $N/8$, etc. The sum over all this is smaller than $N$. I think this is optimal, since without looking at all elements (or at least $N/2$ elements), we don't know where $\max$ is, and can not use any step on any subarray larger than $2$.

$\endgroup$
  • $\begingroup$ You can compute the maximum without using any "steps"; looking at an entry in the array doesn't count as a "step". So without loss of generality, the position of the maximum is known. $\endgroup$ – JeffE May 19 '12 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.