TLE in PRO

[e_noether]

For solving problem PROMOTION I am using 2 heaps and a dictionary. The following is my code giving TLE
please suggest optimizations

import sys
from heapq import heappush,heappop
def main():
	all=sys.stdin.readlines()
	n=int(all[0])
	lno=1
	hpmin=[]
	hpmax=[]
	dic={}
	ans=0
	for i in xrange(n):
		for s in all[i+1].split()[1:]:
			p=int(s)
			if p in dic and dic[p]>0:
				dic[p]+=1
			else:
				dic[p]=1
				heappush(hpmin,p)
				heappush(hpmax,-p)
		minimum=heappop(hpmin)
		while dic[minimum]<1:
			minimum=heappop(hpmin)
		dic[minimum]-=1
		if dic[minimum]!=0:
			heappush(hpmin,minimum)
		maximum=-heappop(hpmax)
		while dic[maximum]<1:
			maximum=-heappop(hpmax)
		dic[maximum]-=1
		if dic[maximum]!=0:
			heappush(hpmax,-maximum)
		ans+=(maximum-minimum)
	print ans
if __name__=='__main__':
	main()
		

[numerix]

please suggest optimizations

After some experiments with my own AC code from 2009, that uses the no longer available psyco (as all the other AC submissions do as well - you can conclude that by looking at the memory usage), I firstly found out, that it is possible to get AC even with actual "pure Python" versions (Python 3 as well).

Then I compared the runtime of my code to your code using some random generated data with the result, that your code is about 1.5-2 times slower than my AC code. I tried some minor approvements (there was not much to do) to your approach, but that also let to TLE.

So I conclude, that the builtin heap-functions are either not fast enough or - that's what I observed in other cases - the import of the needed module is too expensive, independend from its usage. So, local comparisons not always match the SPOJ results.

[e_noether]

Is there any other way to do this problem using some other data structure?
Is there a library for balanced trees in python?
Or does one have to code it to get AC?

[numerix]

Is there a library for balanced trees in python?

No.
My AC code consists of 25 short lines (not more than 30 chars per line) and has no import except stdin.

[e_noether]

here is a simple code:

import sys
def main():
	all=sys.stdin.readlines()
	t=int(all[0])
	dic={}
	ans=0
	for i in xrange(t):
		for p in all[i+1].split()[1:]:
			s=int(p)
			if s in dic:
				dic[s]+=1
			else:
				dic[s]=1
		a=min(dic)
		dic[a]-=1
		if dic[a]==0:
			del dic[a]
		b=max(dic)
		dic[b]-=1
		if dic[b]==0:
			del dic[b]
		ans+=b-a
	print ans
if __name__=='__main__':
	main()

here I have tried to optimize it:

import sys
def main():
	all=sys.stdin.readlines()
	t=int(all[0])
	dic={}
	ans=0
	findmin=True
	findmax=True
	for i in xrange(t):
		for p in all[i+1].split()[1:]:
			s=int(p)
			if s in dic:
				dic[s]+=1
			else:
				dic[s]=1
				if not findmin and s<a:
					a=s
				elif not findmax and s>b:
					b=s
		if findmin:
			a=min(dic)
		dic[a]-=1
		if dic[a]==0:
			del dic[a]
			findmin=True
		else:
			findmin=False
		if findmax:
			b=max(dic)
		dic[b]-=1
		if dic[b]==0:
			del dic[b]
			findmax=True
			if a==b:
				findmin=True
		else:
			findmax=False
		ans+=b-a
	print ans
if __name__=='__main__':
	main()

[e_noether]

please tell me if my approach is right.

[Verdie]

I will send very soon.

http://www.checkerplagiarism.net/