Saturday, November 1, 2014

UVa Problem 10670 - Work Reduction

Problem:

Solution:

There are a few interesting things I found in the problem.

1. At any time - one only consider one agency - I thought I can use different agencies at different time, it wasn't the case.
2. One must be exactly on target, not just less than or equal to it.

Initially I didn't know the first constraint (due to not careful reading of the output section maybe), so I moved on to use the Dijkstra algorithm I tried in my last problem.

It turn out worked fine, but during debugging I find out one interesting thing - if I choose to reduce half now, I will never choose to reduce by one anymore later in the algorithm because reduce half is always better. Otherwise is the same, if I reduce one by now, reduce half will never be a feasible solution.

So it become a simple, even more myopic, greedy algorithm to reduce cost as much as possible algorithm. At any point of time before reaching target, evaluate whether reduce by half is feasible (not reduce less than target) and profitable (reaching the point cheaper than reducing one by one), if so, choose reduce by half, otherwise, reduce by one all the way to target.

That yield the simple code below!

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1611

#include "UVa10670.h"

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct Agency
{
string s;
int reduce_one_price;
int reduce_half_price;
int min_cost;
};

bool less_agency(Agency first, Agency second)
{
if (first.min_cost != second.min_cost)
{
return first.min_cost < second.min_cost;
}
else
{
return first.s < second.s;
}
}

int UVa10670()
{
int num_cases;
cin >> num_cases;
for (int c = 0; c < num_cases; c++)
{
cin >> target;
cin >> num_agencies;

vector<Agency> agencies;
for (int i = 0; i < num_agencies; i++)
{
Agency agency;
char c = cin.get(); // Consume the endline
while (true)
{
c = cin.get();
if (c != ':')
{
agency.s.push_back(c);
}
else
{
break;
}
}
cin >> agency.reduce_one_price;
cin >> c;
cin >> agency.reduce_half_price;
agencies.push_back(agency);
}

for (vector<Agency>::iterator ai = agencies.begin(); ai != agencies.end(); ai++)
{
ai->min_cost = 0;
while (remaining_work > target)
{
if (remaining_work / 2 >= target)
{
int work_done = remaining_work - remaining_work / 2;
int reduce_one_plan_price = ai->reduce_one_price * work_done;
int reduce_half_plan_price = ai->reduce_half_price;
if (reduce_half_plan_price < reduce_one_plan_price)
{
remaining_work -= work_done;
ai->min_cost += reduce_half_plan_price;
}
else
{
// If half prices is not better than one price now, it will never be.
ai->min_cost += ai->reduce_one_price * (remaining_work - target);
remaining_work = target;
}
} else
{
// If reducing half is doing more than target, it will always be
ai->min_cost += ai->reduce_one_price * (remaining_work - target);
remaining_work = target;
}
}
}

sort(agencies.begin(), agencies.end(), less_agency);
cout << "Case " << (c + 1) << endl;
for (vector<Agency>::iterator ai = agencies.begin(); ai != agencies.end(); ai++)
{
cout << ai->s << " " << ai->min_cost << endl;
}
}

return 0;
}