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.

Java code, as requested

Shweta Jain has requested that I post my Java code. It is, essentially, the same as the C / C++ code posted earlier, with new instead of malloc and Arrays.sort instead of qsort.

import java.io.*;    
import java.util.Arrays;
import java.util.Scanner;

public class tg_ex_9  
{   
	//Assume following return types while writing the code for this question.        
	public static int[] output1;    
	
	public static void BalanceCapability(int policeCount, int stationCount,
			int[] policeCapability)       
	{           
		//Write code here
		int smalli;
		int countMax = (policeCount + stationCount - 1) / stationCount;
		int remainder = policeCount % stationCount;
		int i, j;
		short[] count = new short[stationCount];
		output1 = new int[stationCount];
		
		if(stationCount == 1) {
			j = 0;
			for(i=0; i<policeCount; i++) {
				j += policeCapability[i];
			}
			output1[0] = j;
			return;
		}
		
		Arrays.sort(policeCapability);
		reverse(policeCapability);
		Arrays.fill(output1, 0);
		
		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--;
			}
		}
		
		Arrays.sort(output1);
		reverse(output1);
	}
	
	private static void reverse(int[] arr) {
		int last = arr.length - 1;
		int halfLen = arr.length / 2;
		int t;
		for(int i=0; i<halfLen; i++) {
			t = arr[i];
			arr[i] = arr[last-i];
			arr[last-i] = t;
		}
	}
	
	public static void main(String[] argv) {
		int policeCount;
		int stationCount;
		int i;
		
		Scanner s = null;
		try {
			s = new Scanner(new FileInputStream(argv[0]));
		} catch(Exception e) {
			e.printStackTrace();
			return;
		}
		
		while(s.hasNext()) {
			System.out.println("------------------------------------");
			policeCount = s.nextInt();
			int[] policeCapability = new int[policeCount];
			stationCount = s.nextInt();
			//output1 = new int[stationCount];
			
			System.out.println(policeCount + " " + stationCount);
			for(i=0; i<policeCount; i++) {
				policeCapability[i] = s.nextInt();
				System.out.print(policeCapability[i] + " ");
			}
			System.out.println();
			s.nextLine();
			BalanceCapability(policeCount, stationCount, policeCapability);
			
			System.out.print("Result: ");
			for(i=0; i<stationCount; i++)
				System.out.print(output1[i] + " ");
			System.out.println();
		}
	}
}

Techgig July 2011 Expert level test cases

The expert level test cases were finally revealed today (Oct 4 2011) and I'm glad to see that I was right. The accepted solution was, in fact, sub-optimal. Here's a comparison of the expected output to the output produced by the Karmarkar-Karp algorithm:

#	Test case	Expected (Greedy)	Karmarkar-Karp
1	10:2:{2,3,10,5,8, 9,7,3,5,2}	{27,27}	0(5): {9 8 5 3 2 } : 27 1(5): {10 7 5 3 2 } : 27 Result: 27 27
2	17:2:{223,323,124,58,343, 34,85,73,232,74, 267,278,261,145,284, 447,3}	{1631,1623}	0(8): {447 284 278 261 223 73 58 3 } : 1627 1(9): {343 323 267 232 145 124 85 74 34 } : 1627 Result: 1627 1627
3	24:5:{2,3,10,5,8, 9,7,3,5,6, 2,4,6,3,4, 3,7,9,34,2, 3,5,3,2}	{40,27,26,26,26}	0(4): {34 2 2 2 } : 40 1(5): {8 7 5 4 3 } : 27 2(5): {9 7 5 3 2 } : 26 3(5): {9 6 5 3 3 } : 26 4(5): {10 6 4 3 3 } : 26 Result: 40 27 26 26 26
4	5:3:{10,20,90,200,100}	{200,110,110}	10 20 90 200 100 0(1): {200 } : 200 1(2): {90 20 } : 110 2(2): {100 10 } : 110 Result: 200 110 110
5	11:1:{23,43,10,56,38, 29,67,43,43,52, 22}	{426}	Result: 426
6	10:2:{1,1,1,1,9, 1,1,1,1,1}	{13,5}	0(5): {9 1 1 1 1 } : 13 1(5): {1 1 1 1 1 } : 5 Result: 13 5
7	34:7:{1,2,3,4,5, 6,7,8,9,10, 11,12,13,14,15, 16,21,53,74,346, 347,348,349,500,23, 25,26,27,47,6, 7,8,9,1}	{504,382,381,380,379, 164,163}	0(4): {500 2 1 1 } : 504 1(5): {346 14 8 8 4 } : 380 2(5): {349 12 10 7 3 } : 381 3(5): {348 11 9 7 6 } : 381 4(5): {347 13 9 6 5 } : 380 5(5): {74 27 26 21 16 } : 164 6(5): {53 47 25 23 15 } : 163 Result: 504 380 381 381 380 164 163
8	15:7:{1,2,3,4,5, 6,7,8,9,10, 11,12,13,14,51}	{52,19,17,17,17, 17,17}	0(2): {51 1 } : 52 1(3): {13 3 2 } : 18 2(2): {14 4 } : 18 3(2): {9 8 } : 17 4(2): {10 7 } : 17 5(2): {11 6 } : 17 6(2): {12 5 } : 17 Result: 52 18 18 17 17 17 17
9	25:8:{223,323,124,58,343, 34,85,73,232,74, 267,278,261,145,284, 447,3,1,2,3, 4,5,6,7,8}	{456,452,409,405,401, 397,392,378}	0(3): {232 223 1 } : 456 1(3): {447 2 3 } : 452 2(3): {261 145 4 } : 410 3(3): {323 73 5 } : 401 4(3): {343 58 3 } : 404 5(3): {278 74 34 } : 386 6(3): {267 124 6 } : 397 7(4): {284 85 8 7 } : 384 Result: 456 452 410 401 404 386 397 384

Test case #2 clearly shows, that the results produced by the Karmarkar-Karp algorithm are definitely better than the Greedy algorithm.