Tuesday, October 28, 2014

UVa Problem 410 - Station Balance

Problem:

Solution:

Today I started the new subsection on competitive programming - greedy algorithms. The book covers surprising little about greedy algorithm. To me - the greedy paradigm is hard. Come up with some greedy approximation is easy, but I often don't know for certain if a greedy algorithm would work.

This problem, for example, at the first glance, I wouldn't even try greedy to start with.

So I cheated - I spent some time thinking about how would I solve this problem using greedy, but I failed, I read the algorithm in the book and implemented it.

The algorithm state in the book is quite simple as this. Add to the list a bunch of object with 0 mass so that the number of object is exactly twice the number of chambers. Pair up the largest with the smallest and so on.

The book does not cover why this algorithm is optimal. I thought I would try to do it here, but turn I also can't. This only show greedy is really hard. In my attempts, I tried to follow the approaches taught in Algorithm Design (PDF)chapter 4, this is the best book I have found so far about greedy algorithms.

To be honest, I haven't tried very hard, but at the face of it, I don't even know what is the local, myopic criterion that is being optimized, so it is hard to apply the greedy stay ahead trick. For exchange arguments, since we are optimizing a sum that involve non-linearity (you don't know for sure if it is bigger than A or not), there are difficulties there too. Exchange arguments seems more promising but I am not there yet. Yet another idea? I think we might want to show sum of square instead of that sum of imbalance, sum of squares is probably easier to show, but does minimizing sum of squares lead to minimizing sum of imbalance, um, not sure.

Maybe someday I will have the Eureka moment, but well, not now. I will update this post by then.

Code:

#include "stdafx.h"

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

#include "UVa410.h"

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

int UVa410()
{
int case_number = 1;
while (true)
{
int number_of_chambers;
int number_of_elements;
cin >> number_of_chambers;
if (cin.eof())
{
break;
}
cin >> number_of_elements;
vector<int> masses;
for (int i = 0; i < number_of_elements; i++)
{
int mass;
cin >> mass;
masses.push_back(mass);
}

// I have read the book - to be honest - I wouldn't be able to come up
// with this greedy algorithm myself now

sort(masses.begin(), masses.end());

int large_index = masses.size();
int small_index = large_index - 2 * number_of_chambers;

double mean = 0;

for (vector<int>::iterator mi = masses.begin(); mi != masses.end(); mi++)
{
mean += *mi;
}
mean = mean / number_of_chambers;

cout << "Set #" << case_number << endl;
double imbalance = 0;
for (int i = 0; i < number_of_chambers; i++)
{
double chamber_sum = 0;
cout << i << ":";
if (small_index >= 0)
{
chamber_sum += masses[small_index];
cout << " " << masses[small_index];
}
if (large_index > 0)
{
cout << " " << masses[large_index - 1];
chamber_sum += masses[large_index - 1];
}
double diff = chamber_sum - mean;
imbalance += (diff > 0 ? diff : -diff);
small_index++;
large_index--;
cout << endl;
}
std::cout << std::setprecision(5) << std::fixed;
cout << "IMBALANCE = " << imbalance << endl;
cout << endl;

case_number++;
}

return 0;
}