**Problem:**

Please find the problem here.

**Solution:**

When greedy works, it is the best algorithm, once again we get a proof in this problem. The problem can have huge search space. But if greedy is used it is easy.

The idea is to greedily satisfy the demand (the wish to sell or buy) greedily with minimal cost from left to right. In the sample problem.

5 -4 1 -3 1

The first inhabitant wanted to buy 5 wine, so it buy from its nearest neighbor 4 bottles, and then 1 more bottle from far away, result at a cost of 4 + 3 = 7.

```
```

The next inhabitant sold all his stock already, so no need to handle him.

```
```

`The next inhabitant want 1 bottle, so he buys from its neighbor, his neighbor now have just 1 bottle left to sell, so it sell to its neighbor again.`

```
```

`The overall cost is 9.`

```
```

`The problem is - why this method work? At any point we are focusing on optimizing the current person, but the overall cost is reduced to minimal. It is because the greedy algorithm always stay ahead in the partial sum.`

```
```

`To see that, it is obvious that the cost for the first person is minimized. There is no way for any algorithm to do better than that.`

```
```

Suppose the first k persons are planned using the greedy algorithm, and that the partial sum of the first k people is minimal (as an induction hypothesis) and the k+1 person comes. We use the same method to plan him so that the overall partial sum of the first (k+1) people is smaller?

```
```

`Suppose there is - now because the k+1 person is already pulling the nearest - in order for the partial sum to improve, the only possibility is that we forgo the optimality of the first k people and leave some closer people for the k + 1 people to consume. The reduction in cost must cover the increase in cost above. `

```
```

`One can argue that the above is impossible, the reduction of cost must come from the the increase of previous costs. The contradiction shows the greedy algorithm works!`

```
```

`From an implementation perspective, in order to quickly access to the opposites (buyer find sellers, seller find buyers), we maintain the queues of (quantity/index) pair. That avoids scanning the whole array.`

```
```

**Code:**

```
```

#include "stdafx.h" // http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1995 #include "UVa11054.h" #include <iostream> #include <queue> #include <map> using namespace std; typedef long long int64; int UVa11054() { while (true) { int num_inhabitants; cin >> num_inhabitants; if (num_inhabitants == 0) { break; } queue<pair<int, int> > positive_quantities; queue<pair<int, int> > negative_quantities; for (int i = 0; i < num_inhabitants; i++) { int quantity; cin >> quantity; if (quantity > 0) { positive_quantities.push(pair<int, int>(quantity, i)); } else if (quantity < 0) { negative_quantities.push(pair<int, int>(quantity, i)); } } // Greedy algorithm - satisfy demand with lowest cost from left to right int64 cost = 0; while (positive_quantities.size() > 0 && negative_quantities.size() > 0) { int positive_index = positive_quantities.front().second; int negative_index = negative_quantities.front().second; if (positive_index < negative_index) { int positive_demand = positive_quantities.front().first; positive_quantities.pop(); // Pulling negative supply to satisfy positive demand while (positive_demand > 0) { int negative_supply = negative_quantities.front().first; if (positive_demand + negative_supply < 0) { // Case 1: The current negative supply can satisfy the demand without depleting negative_quantities.front().first += positive_demand; cost += (negative_quantities.front().second - positive_index) * positive_demand; positive_demand = 0; } else { // Case 2: The current negative supply is depleted positive_demand += negative_quantities.front().first; cost += (negative_quantities.front().second - positive_index) * -negative_quantities.front().first; negative_quantities.pop(); } } } else if (negative_index < positive_index) { int negative_demand = negative_quantities.front().first; negative_quantities.pop(); // Pulling positive supply to satisfy negative demand while (negative_demand < 0) { int positive_supply = positive_quantities.front().first; if (negative_demand + positive_supply > 0) { // Case 1: The current positive supply can satisfy the demand without depleting positive_quantities.front().first += negative_demand; cost += (positive_quantities.front().second - negative_index) * -negative_demand; negative_demand = 0; } else { // Case 2: The current positive supply is depleted negative_demand += positive_quantities.front().first; cost += (positive_quantities.front().second - negative_index) * positive_quantities.front().first; positive_quantities.pop(); } } } else { // It is impossible to have duplicate indexes throw 0; } } cout << cost << endl; } return 0; }

Can you please explain your proof in detail?

ReplyDeleteI am not able to understand reasoning. If possible with an example.

Suppose houses have wine like this -1,-1,2,-1,1. In this case if House with 2 wine bottles requirement chooses greedily, we get cost to be 2 plus cost to transfer wine bottle from left edge to right edge. (2+4 =6). But we can see if the approach you outlined gives 2+1+1 = 4. Why greedy approach from one end succeeds while choosing arbitrarily fails. Can you please explain?

ReplyDelete