1
$\begingroup$

We have a cake of length $n$ and we have two arrays $A$ and $B$ of size $n$. The two arrays have order like below. $A[0]<A[1]<\dots <A[n]$, $B[0]>B[1]>\dots >B[n]$. We define a envyless location as a cut in the cake where it satisfies $A[i]=B[i]$. For example, $A=[1,2,3,4,5,6,7]$ and $B=[7,6,5,4,3,2,1]$, $A[3]=B[3]=4$, therefore, cutting the cake at length 4 makes the cut envyless. If the algorithm finds an envyless location it returns it's location, and if the envyless location does not exist, it returns null. I am trying to use divide and conquer to solve this problem with worst-case runtime of $O(\log n)$.

I have tried the following procedure and failed. First, divide the cake in half. Find the mid point of the splitted cake and compare $A[mid]$ and $B[mid]$. If found, terminate and return the location. If not found, keep on dividing and comparing.
I expected this to run on $O(\log n)$ time but it cannot because for example, if $A=[1,2,3,4,5,6]$ and $B=[20,11,9,8,7,6]$, the envyless location is at location 6, and the algorithm needs to do $n$ comparison, making the algorithm to run at $O(n\log n)$.

Any help will be very helpful.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

If $A[\text{mid}] < B[\text{mid}]$ then you can recurse on $A[\text{mid}+1, \dots, n]$ and $B[\text{mid}+1, \dots,n]$ since, if an envyless cut exists, it must be after location $mid$.

The situation $A[\text{mid}] > B[\text{mid}]$ is symmetric and you can recurse on $A[0, \dots, \text{mid}-1]$ and $B[0, \dots, \text{mid}-1]$.

The resulting algorithm takes time $T(n) \le T(\lfloor n/2 \rfloor) + O(1)$, which has solution $T(n) = O(\log n)$.

$\endgroup$
1
  • $\begingroup$ Shouldn't the algorithm recurse on $A[0,…,mid−1]$ and $B[0,…,mid−1]$ when $A[mid] > B[mid]$? For example, when $A=[98,99,100,101,102]$ and $B=[98,4,3,2,1]$, $A[mid] > B[mid]$ and the envyless point can exist only on before mid. $\endgroup$
    – Andrew Kim
    May 22 at 3:02

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.