9
$\begingroup$

I am stuck on this problem:

Given an array $A$ of the first $n$ natural numbers randomly permuted, an array $B$ is constructed, such that $B(k)$ is the number of elements from $A(1)$ to $A(k-1)$ which are smaller than $A(k)$.

i) Given $A$ can you find $B$ in $O(n)$ time?
ii) Given $B$ can you find $A$ in $O(n)$ time?

Here, $B(1) = 0$. For a concrete example: $$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \\ \end{vmatrix}$$

Can anyone help me? Thanks.

$\endgroup$
  • $\begingroup$ I found this: Computing permutation encodings which gives $\mathcal O(n \log n)$ algorithms for these problems. At least I think they are the same problems. $\endgroup$ – Realz Slaw Nov 26 '12 at 0:39
  • $\begingroup$ @Merbs does that Hint you gave mean that you have a solution ? $\endgroup$ – AJed Nov 26 '12 at 3:22
  • 1
    $\begingroup$ @AJed, it means I have an algorithm, though it takes $O(n^2)$ for the simple algorithm without space and $O(n\log n)$ if we are allowed space. At the moment, I'm leaning towards neither being not possible in $O(n)$ and both being the same algorithm. $\endgroup$ – Merbs Nov 26 '12 at 3:38
  • $\begingroup$ @Merbs. I feel your hint can lead to the right track. i m having one solution too (following your hint). I guess there is a trick in the analysis that makes it go to $O(n)$.. I think the trick is the knowledge that $A$ goes from 1:$n$ only. $\endgroup$ – AJed Nov 26 '12 at 3:42
  • 2
    $\begingroup$ This paper also gives a $\mathcal O(n \log n)$ algorithm. Are you sure there exists an $\mathcal O(n)$ algorithm for this? $\endgroup$ – Realz Slaw Nov 26 '12 at 12:46
1
$\begingroup$

The naive algorithm for determining $B$ from $A$:

For $k=1,\dots,n$, determine the value of $B(k)$ by comparing each $A(i)$ to $A(k)$ for $i=1,\dots,k$ and counting those that satisfy $A(i)<A(k)$.

This algorithm compares $A(1)$ to all others ($n-1$ times), $A(2)$ to $n-2$ others, etc. so the total number of comparisons is $\frac{(n-1)(n-2)}{2}$. But that's not the best we can do. For example, looking at $B(n)$, we don't have to do any comparisons! $B(n)=A(n)-1$ because it's the first $n$ natural numbers, and it’s guaranteed (regardless of the permutation) that the $n-1$ lower natural numbers will be there. What about $B(n-1)$? Instead of checking $A(1)$ through $A(n-2)$, we could just check $A(n)$. That is:

For $k=1, \dots,\frac{n}{2}$, use the algorithm above; for $k=\frac{n}{2},\dots,n$ use the reverse algorithm: determine $B(k)$ by setting it initially to $A(n)-1$ and then subtracting $1$ for each entry $A(i)$ for $i=k+1,\dots,n$ that is less than $A(k)$.

This would take $2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$ steps, which is still $O(n^2)$. Note also that in constructing $A$ from $B$, if $B(n)=A(n)-1$ then $A(n)=B(n)+1$.

But now for more finesse. If we’re allowed some additional space or sort in-place, we can sort the numbers as we’re comparing them. For example: $$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & & \\ \end{vmatrix}$$

Instead of checking all of them (or checking them in order), we could use binary search to determine each $B(k)$. However, the sorting still takes time $O(n\log n)$.

$\endgroup$
  • $\begingroup$ This was just my first idea; though I realize the problem is more interesting than I originally gave it credit. And I haven't had an opportunity yet to read Realz Slaw's findings, so the algorithm may be off. $\endgroup$ – Merbs Nov 27 '12 at 1:44
0
$\begingroup$

Rather than determining each $B(k)$ one at a time, we can be forward looking and only go through each number in $A$ once! But we'll use $n$ space:

$$\begin{vmatrix} A & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & & B \\ 8 & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{0} & 1 & & 0\\ 4 & & 0 & 0 & 0 & \color{red}{0} & 1 & 1 & 1 & 1 & 2 & & 0\\ 3 & & 0 & 0 & \color{red}{0} & 1 & 2 & 2 & 2 & 2 & 3 & & 0\\ 1 & & \color{red}{0} & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 & & 0\\ 7 & & 0 & 1 & 1 & 2 & 3 & 3 & \color{red}{3} & 4 & 5 & & 3\\ 2 & & 0 & \color{red}{1} & 2 & 3 & 4 & 4 & 4 & 5 & 6 & & 1\\ 9 & & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & \color{red}{6} & & 6\\ 6 & & 0 & 1 & 2 & 3 & 4 & \color{red}{4} & 5 & 6 & 7 & & 4\\ 5 & & 0 & 1 & 2 & 3 & \color{red}{4} & 5 & 6 & 7 & 8 & & 4\\ \end{vmatrix}$$

We could save even more time by not updating those that have already been determined (that is, there is no point in updating $8$ after the first step), but in the worst case, we still have to update $\frac{(n)(n+2)}{2}$ times

$\endgroup$
0
$\begingroup$

both I and II are solvable using #next_greater_element that i explained here. but its a little harder than just the problem but before solution you need to learn next greater element:

  1. consider we have a vector for every element of $A$ name it $S_i$ for element $i$. now once run the next greater algorithm starting from right to left but except setting element $i$ in $A$ its next greater element index , push in $S_i$ the elements that $i$ is their next greater element.then iterate over the array left to right and then $B[i]=\sum_{j=0}^x (S_i[j]+1)$ where $x$ is the size of vector $S_i$.and its $\Theta(n)$ because each the next greater algorithm is $\Theta(n)$ and also iterating is $\Theta(n)$

second part is also similar noting that we can get the value of the rightest element in $O(1)$ EDIT:my solution is wrong it seems that it dont have any$o(n)$ solution

$\endgroup$

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.