## Regarding a problem in Timus online judge - reg

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

### Regarding a problem in Timus online judge - reg

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

if (len(weights) == 2):
return (weights - weights)

weights.reverse()

pile1 = 0
pile2 = 0

for stone in weights:
if (pile1 < pile2) and added == False:
pile1 = pile1 + stone

if (pile1 > pile2) and added == False:
pile2 = pile2 + stone

if (pile1 == pile2) and added == False:
pile1 = pile1 + stone

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:])

jaap
Posts: 540
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Regarding a problem in Timus online judge - reg

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.
Jaap's Puzzle Page 