To count number of quadruplets with sum = 0
n00m
n00m at narod.ru
Thu Mar 15 18:42:03 EDT 2007
http://www.spoj.pl/problems/SUMFOUR/
3
0 0 0 0
0 0 0 0
-1 -1 1 1
Answer for this input data is 33.
My solution for the problem is
======================================================================
import time
t = time.clock()
q,w,e,r,sch,h = [],[],[],[],0,{}
f = open("D:/m4000.txt","rt")
n = int(f.readline())
for o in range(n):
row = map(long, f.readline().split())
q.append(row[0])
w.append(row[1])
e.append(row[2])
r.append(row[3])
f.close()
for x in q:
for y in w:
if h.has_key(x+y):
h[x+y] += 1
else:
h[x+y] = 1
for x in e:
for y in r:
sch += h.get(-(x+y),0)
q,w,e,r,h = None,None,None,None,None
print sch
print time.clock() - t
===============================================================
Alas it gets "time limit exceeded".
On my home PC (1.6 GHz, 512 MB RAM) and for 4000 input rows it
executes ~1.5 min.
Any ideas to speed it up say 10 times? Or the problem only for C-like
langs?
More information about the Python-list
mailing list