2
$\begingroup$

I have this problem where I need to design a greedy algorithm. The problem is as follows:

A chocolate factory owns $n$ stores, which are connected by a single road. Each store has a limited supply $c_i$ of chocolates. Furthermore, the factory would like to have the same amount of chocolate in each store. Therefore, they hired a truck driver to haul chocolates between the stores, but the driver eats two chocolate bars for each kilometer he drives.

Calculate the largest amount of chocolate $C$ they can have at each store.

Input: The position $p_i$ and chocolate supply $c_i$ of each store. The positions are in increasing sorted order.

Output: The largest amount $C$, such that each store can have a chocolate supply of at least $C$ after the truck driver has hauled between the stores.

I have a problem with identifying the greedy choice property for the problem. So far I came up with the following:

The greedy choice can be the minimum arithmetic mean of two neighbouring stores minus the delivery cost divided by $C$, but it has to be larger or equal to 1. I came up with the following equation: $$\min\{\frac{\frac{1}{n} \cdot (c_i + c_{i_{neighbour}} - delivery_{cost})}{C}\}$$

Where the delivery cost is $2\cdot |p_i - p_{i-1}|$.

I am not sure if this approach is the right one. I am open for hints and partial solutions.

$\endgroup$
7
  • $\begingroup$ Can we assume that the truck has infinite capacity, we have an arbitrarily long amount of time to haul between stores, and that the truck driver eats nothing when his truck is empty? $\endgroup$
    – orlp
    Mar 2, 2019 at 16:55
  • $\begingroup$ @orlp Yes. Furthermore, we can use as many trucks as possible starting at arbitrary places. $\endgroup$
    – Winston Smith
    Mar 2, 2019 at 19:34
  • $\begingroup$ @Apass.Jack Which original problem are you talking about? $\endgroup$
    – Winston Smith
    Mar 2, 2019 at 19:35
  • $\begingroup$ @Apass.Jack It was a homework problem. $\endgroup$
    – Winston Smith
    Mar 2, 2019 at 19:51
  • $\begingroup$ The example you are proposing here is not possible, since the $p_1$ is the location of the first store and the distance to itself is zero. However, I tested formula and it gave a negative value for $c_1$, but I am making the choice if the value is $\geq 1$. $\endgroup$
    – Winston Smith
    Mar 2, 2019 at 22:59

1 Answer 1

Reset to default
1
$\begingroup$

It looks like a greedy algorithm cannot do it alone.

Here is an approach based on binary search.

Suppose we have a subroutine to determine that if it is possible to have a chocolate supply of $s$ after the truck driver has hauled between the stores, given $s$. Note that if $s$ is possible, than $t$ is possible for any $t<s$.

Let $m$ be the maximum among $c_i$. Let us check if $m/2$ is possible. If yes, let us try $(m/2 + m + 1)/2$. (+1 to ensure we will try $m$ just in case). If no, check $m/4$. I believe you can see the rest of binary search algorithm. Be careful with various boundary cases.

Now the problem is how to build that subroutine? We can think recursively. Let $s$ be given. If $c_1>s$, we will use a truck to move $c_1-s$ chocolates to $p_2$. Whatever is left when the the truck has reached $p_2$ will be added to $c_2$. So we got $c_2'$. If $c_1=s$, $c_2'=c_2$. If $c_1<s$, compute $d_2$, the least amount of the chocolate needed to be carried on a truck that starts from $p_2$ can reach $p_1$ to increase $c_1$ to $s$. Subtract that amount from $c_2$ and get $c_2'$, which might be negative. We can see that $s$ is possible initially if and only if $s$ is possible for $c_2', c_3, \cdots, c_n$ at $p_2,p_3,\cdots, p_n$ respectively.

There should be enough hint above. I will let you finish the rest of work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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