Techgig Expert Level Problem - July 2011

This is my solution to the expert level problem posted on Techgig in July 2011. The problem was difficult, not because the algorithm was complicated, but because there was a hidden requirement, that one had to figure out what approximation algorithm the judges must have used, to come up with their solutions.

First, a Greedy solution

This solution is based purely on the Greedy algorithm. This is definitely not the best possible solution to this problem. But it does clear all the judges' test cases.

/*
* tg_ex_8.cpp
*
*  Created on: Jul 20, 2011
*      Author: akshay
*/

#include <iostream>
#include <cstdlib>
#include <cstring>

using namespace std;

//Assume following return types while writing the code for this question.
int output1[100];

int cmpFn(const void* v1, const void* v2);

void BalanceCapability(int policeCount,int stationCount,int policeCapability[])  
{
	int smalli;
	int countMax = (policeCount + stationCount - 1) / stationCount;
	int remainder = policeCount % stationCount;
	int i, j;
	short* count = (short*)malloc(sizeof(short)* stationCount);
	
	if(stationCount == 1) {
		j = 0;
		for(i=0; i<policeCount; i++) {
			j += policeCapability[i];
		}
		output1[0] = j;
		return;
	}
	
	qsort(policeCapability, policeCount, sizeof(int), cmpFn);
	
	for(i=0; i<stationCount; ++i) {
		output1[i] = policeCapability[i];
		count[i] = 1;
	}
	
	while(i < policeCount) {
		smalli = -1;
		for(j=0; j<stationCount; ++j) { 
			if(count[j] < countMax && (smalli == -1 ||
					output1[j] < output1[smalli])) {
				smalli = j;
			}
		}
		
		output1[smalli] += policeCapability[i++];
		++count[smalli];
		if(count[smalli] == countMax) {
			--remainder;
			if(remainder==0)
				countMax--;
		}
	}
	
	qsort(output1, stationCount, sizeof(int), cmpFn);
	
	free(count);
}

int cmpFn(const void* v1, const void* v2) {
	return *(int*)v2 - *(int*)v1;
}

#include <fstream>

int main(int argc, char** argv) {
	int policeCount;
	int stationCount;
	int policeCapability[100];
	char buffer[32];
	int i;
	
	ifstream fin(argv[1]);
	while(!fin.eof()) {
		cout<<"------------------------------------"<<endl;
		fin>>policeCount>>stationCount;
		if(fin.eof())
			break;
		cout<<policeCount<<" "<<stationCount<<endl;
		for(i=0; i<policeCount; i++) {
			fin>>policeCapability[i];
			cout<<policeCapability[i]<<" ";
		}
		cout<<endl;
		fin.getline(buffer, 32);
		BalanceCapability(policeCount, stationCount, policeCapability);
		
		cout<<"Result: ";
		for(i=0; i<stationCount; i++)
			cout<<output1[i]<<" ";
		cout<<endl;
	}
	
	return EXIT_SUCCESS;
}

Now, a solution based on the Karmarkar-Karp algorithm

This solution probably has bugs, but produces better results than the greedy algorithm. It uses the Karmarkar-Karp algorithm to improve the greedy solution sets pair-wise. However, it clears fewer test cases than the Greedy algorithm.

/*
* techgig_expert_4.cpp
*
*  Created on: Jul 19, 2011
*      Author: akshay
*/

#include <iostream>
#include <cstring>
#include <cstdlib>

using namespace std;

int output1[1000];   //	Corrected: 1000 stations possible

struct Station {
	short count;
	short *cap;
};

int cmpFn(const void* v1, const void* v2) {
	return *(int*)v2 - *(int*)v1;
}

class KarmarkarKarpSolver {
private:
	
	struct Node {
		short value;
		Node* left;
		Node* right;
		Node* parents[2];
		int lnum;
	};
	
	int maxSize;
	int bufferSize;
	Node* nodeBuffer;
	int nodeIdx;
	
	Node* first;
	Node* last;
	Node* curr;
	Node* temp;
	
	Node* head[2];
	Node* tail[2];
	int sum[2];
	int count[2];
	
	void reset() {
		nodeIdx = sum[0] = sum[1] = count[0] = count[1] = 0;
		tail[0] = tail[1] = head[0] = head[1] = first = last = NULL;
		memset(nodeBuffer, 0, bufferSize * sizeof(Node));
	}
	
	Node* newNode() {
		//cout<<nodeIdx<<" / "<<bufferSize<<endl;
		return nodeBuffer + nodeIdx++;
	}
	
	static int shortCmpFn(const void* v1, const void* v2) {
		return *(short*)v2 - *(short*)v1;
	}
	
	Node* insertSorted(short value);
	Node* insertSorted(Node*& first, Node*& last, Node* curr);
	void solve(int nNodes);
	void prepare(Node* start, Station* s);
	void print(Node* start, ostream& out);
	void printSolution(ostream& out);
	
public:
	
	KarmarkarKarpSolver(int maxSize) {
		this->maxSize = maxSize;
		bufferSize = 4 * maxSize;
		nodeBuffer = new Node[bufferSize];
		reset();
		//cout<<"Creating solver: "<<nodeBuffer<<" "<<*(((int*)nodeBuffer) - 1)
		//		<<": "<<sizeof(Node)<<endl;
	}
	
	virtual ~KarmarkarKarpSolver() {
		//cout<<"Deleting solver: "<<nodeBuffer<<" "<<*(((int*)nodeBuffer) - 1)
		//				<<": "<<sizeof(Node)<<endl;
		delete[] nodeBuffer;
	}
	
	void improve(Station* s1, Station* s2);
};

KarmarkarKarpSolver::Node* KarmarkarKarpSolver::insertSorted(short value) {
	curr = newNode();
	curr->value = value;
	
	return insertSorted(first, last, curr);
}

KarmarkarKarpSolver::Node* KarmarkarKarpSolver::insertSorted(
		KarmarkarKarpSolver::Node*& first,
		KarmarkarKarpSolver::Node*& last,
		KarmarkarKarpSolver::Node* curr) {
	short value = curr->value;
	curr->left = curr->right = NULL;
	
	if(first) {
		for(temp = first; temp != NULL && temp->value > value;
				temp = temp->right);
		if(temp) {
			if(temp->left) {
				curr->left = temp->left;
				curr->left->right = curr;
			} else {
				first = curr;
			}
			curr->right = temp;
			temp->left = curr;
		} else {
			last->right = curr;
			curr->left = last;
			last = curr;
		}
	} else {
		first = last = curr;
	}
	
	return curr;
}

void KarmarkarKarpSolver::improve(Station* s1, Station* s2) {
	for(int i = 0; i < s1->count; ++i) {
		insertSorted(s1->cap[i]);
	}
	
	for(int i = 0; i < s2->count; ++i) {
		insertSorted(s2->cap[i]);
	}
	
	//print(first, cout);
	
	solve(s1->count + s2->count);
	prepare(head[0], s1);
	prepare(head[1], s2);
	
	reset();
}

void KarmarkarKarpSolver::prepare(KarmarkarKarpSolver::Node* start, Station* s) {
	s->count = 0;
	for(temp = start; temp != NULL; temp = temp->right) {
		s->cap[s->count++] = temp->value;
	}
}

void KarmarkarKarpSolver::solve(int nNodes) {
	if(nNodes == 1) {
		head[0] = tail[0] = first;
		tail[0]->left = tail[0]->right = head[0]->left = head[0]->right = NULL;
		head[0]->lnum = 0;
		sum[0] = first->value;
		count[0] = 1;
		//printSolution(cout);
		
		return;
	}
	
	Node* savedFirst = first;
	short diff = first->value - first->right->value;
	first = first->right->right;
	if(first)
		first->left = NULL;
	Node* n = insertSorted(diff);
	n->parents[0] = savedFirst;
	n->parents[1] = savedFirst->right;
	
	//print(first, cout);
	
	solve(nNodes - 1);
	
	int l1 = n->lnum;
	int l2 = n->lnum ^ 1;
	int pid = 0;
	if(sum[l1] - n->value > sum[l2]) {
		pid = 1;
	}
	
	//cout<<"Replacing "<<n->value<<" in list "<<l1<<" with "<<n->parents[0]->value
	//			<<" and "<<n->parents[1]->value<<endl;
	
	if(head[l1] == n)
		head[l1] = n->right;
	if(tail[l1] == n)
		tail[l1] = n->left;
	if(n->left)
		n->left->right = n->right;
	if(n->right)
		n->right->left = n->left;
	
	Node* p = n->parents[pid];
	insertSorted(head[l1], tail[l1], p);
	sum[l1] = sum[l1] - n->value + p->value;
	p->lnum = l1;
	
	if(count[l2] == maxSize) {
		temp = tail[l2];
		tail[l2] = temp->left;
		tail[l2]->right = NULL;
		insertSorted(head[l1], tail[l1], temp);
		count[l1]++;
	} else
		count[l2]++;
	p = n->parents[pid ^ 1];
	insertSorted(head[l2], tail[l2], p);
	sum[l2] += p->value;
	p->lnum = l2;
	
	//printSolution(cout);
}

void KarmarkarKarpSolver::printSolution(ostream& out) {
	out<<"0 ["<<count[0]<<"]("<<sum[0]<<"): ";
	print(head[0], out);
	out<<"1 ["<<count[1]<<"]("<<sum[1]<<"): ";
	print(head[1], out);
}

void KarmarkarKarpSolver::print(Node* start, ostream& out) {
	for(temp=start; temp!=NULL; temp=temp->right) {
		out<<"[";
		if(temp->left)
			out<<temp->left->value;
		out<<" <"<<temp->value<<"> ";
		if(temp->right)
			out<<temp->right->value;
		out<<"] ";
	}
	out<<endl;
}

void BalanceCapability(int policeCount,int stationCount,int policeCapability[])  
{
	int smalli = stationCount - 1;
	int smalli2 = stationCount - 2;
	int countMax = (policeCount + stationCount - 1) / stationCount;
	int i, j;
	Station *stations = new Station[stationCount];
	short* caps = new short[countMax * stationCount];
	
	qsort(policeCapability, policeCount, sizeof(int), cmpFn);
	
	for(i=0; i<stationCount; ++i, caps += countMax) {
		output1[i] = policeCapability[i];
		stations[i].cap = caps;
		stations[i].cap[0] = policeCapability[i];
		stations[i].count = 1;
	}
	
	while(i < policeCount) {
		output1[smalli] += policeCapability[i];
		stations[smalli].cap[stations[smalli].count++] = policeCapability[i++];
		
		if(stations[smalli].count == countMax || 
				output1[smalli] > output1[smalli2] ||
				(output1[smalli] == output1[smalli2] && 
						stations[smalli].count < stations[smalli2].count)) {
			smalli = smalli2;
			for(j=0; j<stationCount; ++j) {
				if(j != smalli && stations[j].count < countMax) {
					smalli2 = j;
					break;
				}
			}
			
			for(++j; j<stationCount; ++j) {
				if(j != smalli && stations[j].count < countMax &&
						(output1[j] < output1[smalli2] ||
							(output1[j] == output1[smalli2] && 
								stations[j].count > stations[smalli2].count))) {
					smalli2 = j;
				}
			}
		}
	}
	
	//	Improve using Karmarkar-Karp
	KarmarkarKarpSolver kks(countMax);
	for(i=0; i<stationCount - 1; ++i) {
		for(j=i+1; j<stationCount; ++j) {
			kks.improve(stations + i, stations + j);
		}
	}
	
	int sum;
	for(i=0; i<stationCount; ++i) {
		countMax = stations[i].count;
		sum = 0;
		cout<<i<<": {";
		for(j=0; j<countMax; j++) {
			sum += stations[i].cap[j];
			cout<<stations[i].cap[j]<<" ";
		}
		cout<<"} : "<<sum<<endl;
		output1[i] = sum;
	}
	
	delete[] stations[0].cap;
	delete[] stations;
}

#include <fstream>

int main(int argc, char** argv) {
	int policeCount;
	int stationCount;
	int policeCapability[100];
	char buffer[32];
	int i;
	
	ifstream fin(argv[1]);
	while(!fin.eof()) {
		cout<<"------------------------------------"<<endl;
		fin>>policeCount>>stationCount;
		if(fin.eof())
			break;
		cout<<policeCount<<" "<<stationCount<<endl;
		for(i=0; i<policeCount; i++) {
			fin>>policeCapability[i];
			cout<<policeCapability[i]<<" ";
		}
		cout<<endl;
		fin.getline(buffer, 32);
		BalanceCapability(policeCount, stationCount, policeCapability);
		
		cout<<"Result: ";
		for(i=0; i<stationCount; i++)
			cout<<output1[i]<<" ";
		cout<<endl;
	}
	
	return EXIT_SUCCESS;
}

Here's a comparison of the results produced by the two algorithms

Problem	Greedy Solution	Karmarkar-Karp Solution
24:7:{13, 12, 12, 11, 11, 10, 10, 9, 9, 8, 7, 7, 6, 6, 6, 5, 4, 3, 3, 3, 2, 2, 1, 1}	24 23 23 23 23 23 22	0: {10 8 3 2 } : 23 1: {11 9 3 } : 23 2: {11 7 5 } : 23 3: {12 9 2 } : 23 4: {13 7 3 } : 23 5: {12 6 4 1 } : 23 6: {10 6 6 1 } : 23 Result: 23 23 23 23 23 23 23
8:2:{5, 10, 20, 90, 100, 150, 200, 250}	445 380	0: {250 150 10 5 } : 415 1: {200 100 90 20 } : 410 Result: 415 410

Although both these algorithms produce fair approximations, the Partition problem is NP-complete. Therefore, the only known algorithm that is guaranteed to produce the optimal solution is Brute Force, provided, of course, that the phrases "balanced as much as possible" and "nearly equal as possible" are precisely defined. Brute force, however, will obviously, always time out.