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