online advertising

Saturday, November 1, 2014

UVa Problem 11054 - Wine trading in Gergovia

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;
}

1 comment :

  1. Can you please explain your proof in detail?
    I am not able to understand reasoning. If possible with an example.

    ReplyDelete