Regarding a problem in Timus online judge - reg

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
Post Reply
gnanasenthil654321
Posts: 5
Joined: Sat Nov 05, 2011 6:36 pm

Regarding a problem in Timus online judge - reg

Post by gnanasenthil654321 » Tue Mar 26, 2013 10:28 am

Hello,
I tried to solve a problem from timus online judge.
(http://acm.timus.ru/problem.aspx?space=1&num=1005)

I wrote the following program in python, i donot know why this algorithm fails. Atleast can you give a test case where my algorithm breaks. Also i get a right answer for the sample test case given in the page.

Code: Select all

#timus 1005
import sys,math
class Timus1005:
	def __init__(self):
		pass
		
	def minimumDiffrence(self,weights):
		weights.sort()
		if (len(weights) == 1):
			return weights[0]
			
		if (len(weights) == 2):
			return (weights[1] - weights[0])
			
		weights.reverse()
			
		pile1 = 0
		pile2 = 0
		
		for stone in weights:
			added = False
			if (pile1 < pile2) and added == False:
				pile1 = pile1 + stone
				added = True
				
			if (pile1 > pile2) and added == False:
				pile2 = pile2 + stone
				added = True
				
			if (pile1 == pile2) and added == False:
				pile1 = pile1 + stone
				added = True
		
		return int(math.fabs(pile1 - pile2))
		
if __name__ == "__main__":
	w = []
	for i in raw_input().split(' '):
		w.append(i)
			
	p = Timus1005()
	print p.minimumDiffrence(w[1:])

User avatar
jaap
Posts: 528
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Regarding a problem in Timus online judge - reg

Post by jaap » Tue Mar 26, 2013 10:38 am

The greedy algorithm is not good enough. Try it on the weights 3,3,2,2,2 where the actual answer should be 0 because 3+3=2+2+2.

Post Reply