4
$\begingroup$

This problem probably falls under some category of algorithms but I don't know which.

A given restaurant has $b_1..b_n$ branches around the world. A food critic has to travel all of the branches.

  1. When the critic finishes visit to the branch $1 \le j\le n$ he gets paid $m_j$ money by his employer for the job.
  2. For branch $j \le n-1$ he takes a flight to the next branch $b_{j+1}$ while the flight costs $c_j$ money. From the last branch $b_n$ a flight goes out to the first branch $b_1$ for the cost of $c_n$.

It is also given that the total amount of money the critic received equals the total cost of flights so: $$ \sum_{j=1}^n m_j=\sum_{j=1}^n c_j $$ At any given point the critic can only pay for the next flight out of the money he currently has.

Lastly, the critic can choose any branch which he will visit first and the first trip will be free.

Prove that the branch $j$ exists such that the critic will be able to start from $b_j$ and visit all branches and suggest an algorithm which will find such a $j$ in $\Theta(n)$ time.

The hint which was given to us is to use queue data structure.

I thought of the following algorithm:

1) Add all branches to a queue.

2) Check if we can travel to the next branch that is if $m_j \ge c_{j+1}$.

  1. If no, that means we don't have enough money so push the branch to the tail of the queue.
  2. If yes, check if $m_j+m_{j+1} \ge c_{j+1}+c_{j+2}$ that is if the critic does travel to the next branch will he have enough money to continue from that branch?

    --If yes then advance one branch in the queue.

    --If no push the next branch to the tail of the tail of the queue

After one traversal of the queue we should have branches in such an order that the critic can complete the journey and branch $j$ will be at the head of the queue.

I'm on the right track? I'm not sure this proves formally enough that a $j$ indeed exists so the critic can complete the journey.

$\endgroup$
  • 1
    $\begingroup$ Try to prove that your solution works. If it does, great. If not, you'll have to think of a different idea. $\endgroup$ – Yuval Filmus Jun 12 '17 at 21:45
  • $\begingroup$ That's the problem I'm not sure how to formally prove that such a $j$ exists. $\endgroup$ – hitchhiker Jun 13 '17 at 5:49
  • $\begingroup$ Strange that the cost of travelling to the next branch would only depend on that branch and not the previous branch. $\endgroup$ – gnasher729 Jun 15 '17 at 11:13
1
+100
$\begingroup$

The algorithm that you suggested using a queue does not seem to be linear-time with respect to $n$, because you did not prove that each restaurant gets pushed in the queue only once (or at most a constant number of times). I suppose there are cases where a restaurant gets pushed into the queue nearly $n$ times.

However, there is a simple algorithm for this problem and I got the idea based on a similar question in `Introduction to Algorithms' by Cormen et al. The main idea is to start from the first restaurant and fly as much as possible, until we run out of money. If we reached the end, then that was the starting point, otherwise, we can start from the place where we run out of money. It is easy to see that the next starting point is exact the place where we run out of money (because previous restaurants did not pay enough money for sustaining).

  1. Let $i \gets 1$;
  2. While ($i \leq n$)
  3. $~~~~$ Let $money \gets m_i$;
  4. $~~~~$ Let $starting \gets i$;
  5. $~~~~$ While ($money \geq 0$)
  6. $~~~~~~~~$ Let $money \gets money - c_i$;
  7. $~~~~~~~~$ Let $i \gets i + 1$;
  8. $~~~~$ EndWhile;
  9. EndWhile;
  10. Output $starting$;

The main idea behind the proof is mentioned in my second paragraph. Once you start from a restaurant $b_i$ and run out of your money in a restaurant $b_j$, you can make sure that none of the restaurants $b_i$ to $b_{j-1}$ are not good starting points.

How to prove that such $starting$ exist? It is possible to show that by contradiction. We know that:

$$\sum_{1 \leq i \leq n} m_i = \sum_{1 \leq i \leq n} c_i,$$

which is equivalent to:

$$\sum_{1 \leq i \leq n} m_i - c_i = 0.~~~~(Eq. X)$$

Let us assume that there is no such $starting$ for which the person can start from restaurant $b_{starting}$ and visit all restaurants maintaining a positive amount of money in his pocket. We know that starting from restaurant $b_i$, if we run out of money in restaurant $b_j$, this means that for every restaurant $b_k$ ($i \leq k < j$) there is no way to pass restaurant $b_j$ (because we will definitely run out of money). Given our assumption that no such $starting$ exist, this means that we will have a bunch of pairs $(b_{i_1}, b_{j_1}), \cdots, (b_{i_m}, b_{j_m})$ ($i_{x+1} = j_{x}$) that all result in running out of money. This means that for every pair $(b_{i_x}, b_{j_x})$ we have,

$$\sum_{i_x \leq y \leq j_x} m_{i_y} - c_{i_y} \leq 0,$$

which results in either of the following two cases: (1) The money becomes zero and the critic does not have money to catch up with the next flight and cannot continue flying, (2) The overall summation becomes negative, which is in clear contradiction with our very initial assumption in Eq. (X).

$\endgroup$
  • 1
    $\begingroup$ @hitchhiker Good question. The algorithm can actually determine that. But I will update my answer to include that proof, if possible. $\endgroup$ – orezvani Jun 15 '17 at 6:51
  • 1
    $\begingroup$ @hitchhiker "If we reached the end, then that was the starting point, otherwise, we can start from the place where we run out of money." let's say you start from the place where you run out of money and meet the same fate again, and again, and again, and you aren't able to reach the end without a positive sum. That could only happen if summation of $d_j$ is negative. But we know that summation of $d_j$ is zero, which means we'll find at least one $j$ for which we can reach the last branch without running out of money (and then loop over and travel all other branches from 0 to $j$) $\endgroup$ – Peeyush Kushwaha Jun 15 '17 at 7:00
  • 1
    $\begingroup$ @hitchhiker I added a sketch of the proof in the question. $\endgroup$ – orezvani Jun 15 '17 at 9:01
  • 1
    $\begingroup$ @hitchhiker Initially, I planned to write the algorithm based on $d_i=m_i-c_i$, where we are looking for a $d_{starting}$ from which we can start summing up $d_i$s and we traverse all restaurants. But later I found that there is no need for that. It may seem more simple with $d_i$ though. But I removed it. $\endgroup$ – orezvani Jun 15 '17 at 15:13
  • 1
    $\begingroup$ @hitchhiker I didn't mention this detail, because I assumed that your condition can be satisfied and $\sum m_i = \sum c_i$.. When you get $starting==len$, you need to check whether the trip is feasible or not. This is still $O(n)$. $\endgroup$ – orezvani Jun 15 '17 at 15:35
0
$\begingroup$

This is a classic question in extremal combinatorics. The idea is very simple. Run the journey from the first branch and assume you have enough money saved. Find the branch in your journey where you had the minimum money. If you start the journey from that branch, you do not need the extra money!

$\endgroup$
  • $\begingroup$ I expect an exhaustive answer for the question. You're just floating an idea. Can you offer formal proof that your solution works? $\endgroup$ – hitchhiker Jun 15 '17 at 6:23
  • $\begingroup$ The proof is very straightforward. Think of an array of your money along the journey. The difference between two consecutive element of this array is independent of the starting branch. Based on what branch you just add or subtract a value from ALL elements. By starting from the branch with the minimum value in that array, you will make the minimum number equal to zero. Hence, all the elements will be non-negative. $\endgroup$ – Mohemnist Jun 15 '17 at 6:50
  • $\begingroup$ I don't see what this has to do with extremal combinatorics. Extremal combinatorics deals with questions of the form "what's the least/greatest number of edges a graph can have without having property P?" This question doesn't seem to be anything like that. $\endgroup$ – David Richerby Jun 15 '17 at 7:45
  • $\begingroup$ @DavidRicherby As an outsider, I can confirm that this solution is actually correct. But the OP is looking for a more detailed answer, backed up with a mathematically sound proof. $\endgroup$ – orezvani Jun 15 '17 at 15:19

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.