## Saturday, September 20, 2014

### a bit of greedy: UVa 10026 - Shoemaker's Problem

Problem Statement:
UVa 10026 - Shoemaker's Problem

Summary:
Given a list of jobs, we can only work on one job each day. Each job $$i$$ takes $$t_i$$ days to complete and for each day of not starting on the job, we must pay $$s_i$$ fine. Once we start on a job, we will finish it before starting the next job. We are to find the best permutation/arrangement of the jobs that minimizes the total fine incurred.

Solution:
A great application of exchange argument that establishes the relationship that must hold in an optimal arrangement amongst all permutation. This optimization problem reduces to sorting problem.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

/*
The correct greedy algo and its proof: sort by fine/time
Proof:
s is fine, t is days
Suppose that (s_1,t_1), (s_2,t_2), ..., (s_n,t_n) is the optimal
arrangement such that the total fine is the lowest. Hence we have
O = s_1 (0) + s_2 (t_1) + s_3 (t_1 + t_2) + ...
+ s_i (t_1 + t_2 + ... + t_{i-1})
+ s_{i+1} (t_1 + t_2 + ... + t_{i-1} + t_i)
+ ...
Since O is optimal, by exchange argument, if we exchange the position of
s_i,t_i and s_{i+1},t_{i+1}, we will have total fine O' which will cannot be lower
than O:
O' = ... + s_{i+1} (t_1 + t_2 + ... + t_{i-1})
+ s_i (t_1 + t_2 + ... + t_{i-1} + t_{i+1})
+ ...

hence
O' - O >= 0
<=> s_{i+1} (-t_i) + s_i (t_{i+1}) >= 0
<=> s_i/t_i >= s_{i+1}/t_{i+1}

Hence in the optimal arrangement, s_i comes before s_{i+1} iff s_i/t_i >= s_{i+1}/t_{i+1}
*/

vector<int> arr, s, t;

bool comp(const int& L, const int& R){
if(s[L] * t[R] == s[R] * t[L]) return L < R;
return s[L] * t[R] < s[R] * t[L];
}

int main(){
int TC;
cin >> TC;
bool flag = false;
while(TC--){
if(flag) printf("\n");
flag = true;
int N;
cin >> N;
arr.clear();
s.clear();
t.clear();
for(int i=0;i<N;++i){
int u,v;
cin >> u >> v;
s.push_back(u);
t.push_back(v);
arr.push_back(i);
}
sort(arr.begin(), arr.end(), comp);
for(int i=0;i<N;++i){
if(i != 0) printf(" ");
printf("%d", arr[i]+1);
}
printf("\n");
}
return 0;
}