ISourceCode

Make the frequent cases fast and the rare case correct

ACM – Variant of Balanced Partition Problem – Python

Problem take from ACM and is a variant of the Balanced Partition Problem

Tug of War

A tug of war is to be arranged at the local office picnic. For the tug of war, the picnickers must be divided into two teams. Each person must be on one team or the other; the number of people on the two teams must not differ by more than 1; the total weight of the people on each team should be as nearly equal as possible.

Sample Input
100
90
200
Sample Output

190 200

CODE:

import math
import random

n=5
arr = [100,100,100,90,200]

total=indexA=indexB=i=j=sideA=sideB=0

for p in range(0,n):
	total = total+arr[p]

split=n/2

a = b = [0]*n
arr.sort()

while indexA< split :
	indexA = indexA+1
	a[indexA] = arr[i]
	
	if(indexA< split):
		indexA=indexA+1
		a[indexA] = arr[n-i-1]
		sideA = sideA+arr[n-i-1]
	sideA =sideA+arr[i]
	i=i+1
	j=i

while indexB < n-split :
	indexB=indexB+1
	b[indexB] = arr[j]
	sideB = sideB+arr[j]
   	j=j+1

t1 = split - 1
t2 = split

sideA = sideA + (b[t2]-a[t1])
sideB = sideB + (a[t1]-b[t2])

if split%2 == 0 :
	print "side A has total of:", sideA
	print "side B has total of:", sideB
else:
	sideA = min(sideA, sideB)
	sideB= max(sideA, sideB)
	print "side A has total of:", sideA
	print "side B has total of:", sideB

OUTPUT:
$ python tug.py
side A has total of: 290
side B has total of: 300

For

n=4
arr = [100,100,90,200]
$ python tug.py
side A has total of: 290
side B has total of: 200

For

n=3
arr = [100,90,200]
$ python tug.py
side A has total of: 190
side B has total of: 200

Thanks for Reading!

2 responses to “ACM – Variant of Balanced Partition Problem – Python

  1. tommy July 14, 2011 at 2:37 pm

    Isn’t this a greedy approach? If so, are you sure it gives optimal output always?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: