Bug in judge: TLE vs Accepted comparison


  • 1
    E

    Solution below is a correct n^2 without any obvious problems, it is rejected as TLE:

    class Solution(object):
        def numberOfBoomerangs(self, points):
            """
            :type points: List[List[int]]
            :rtype: int
            """
            import collections
            dist = collections.defaultdict(int)
    
            count = 0
            for i in xrange(len(points)):
                (ax, ay) = points[i]
                for ii in xrange(i+1, len(points)):
                    (bx, by) = points[ii]
                    d = (ax-bx)**2 + (ay-by)**2
                    A = (ax, ay, d)
                    B = (bx, by, d)
                    dist[A] += 1
                    dist[B] += 1
    
            for n in dist.itervalues():
                count+=n*(n-1)
    
            return count
    

    The same solution, but reorganized so that the dict is emptied after each outer-loop iteration (I guess preventing the dict from growing too large?) and accumulating the count on each iteration, is accepted:

    class Solution(object):
        def numberOfBoomerangs(self, points):
            """
            :type points: List[List[int]]
            :rtype: int
            """
            import collections
            import itertools
    
            count = 0
            for i in xrange(len(points)):
                dist = collections.defaultdict(int)
                (ax, ay) = points[i]
                for ii in xrange(len(points)):
                    (bx, by) = points[ii]
                    d = (ax-bx)**2 + (ay-by)**2
                    dist[d] += 1
    
                for n in dist.itervalues():
                    count+=n*(n-1)
    
            return count
    

    The 1st, TLE solution actually makes n fewer iterations than the Accepted, since the first has n*(n-1) + n*(n-1) = 2n*(n-1) = 2n^2-2n iterations, whereas the second one has n^2 + n*(n-1) = 2n^2-n iterations. Either way, the time complexity is the same and both should be accepted.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.