CF Maximum Distance

Problems and Contests
#1

I was working through the Bronze pathway and got to the section on Basic Complete Search, where I attempted the focus problem.

I wrote the following code, which failed on the 10th test when submitting with Pypy.

import itertools

def read():
    input()
    x_values = input().split()
    y_values = input().split()
    return list(zip(x_values, y_values))

def distance(points: tuple) -> float:
    x0, y0 = points[0]
    x1, y1 = points[1]
    return (int(x0) - int(x1))**2 + (int(y0) - int(y1))**2

def main():
    points = read()

    max_distance = 0

    combinations = list(itertools.combinations(points, 2))

    for combo in combinations:
        max_distance = max(max_distance, distance(combo))

    print(round(max_distance))


if __name__ == "__main__":
    main()

I was just wondering what made my solution worse than the guide’s example solution. I remember reading that the itertools library is supposed to be more performant than pure python loops.

#2

You’re getting memory limit exceeded because you’re using O(N^2) memory.

    combinations = list(itertools.combinations(points, 2))

You’ll get AC if you remove list(...) from this line.

Do you have a source for this? I doubt that’s true (at least for this use case).

#3

Thank you so much!

As for the itertools claim, the official documentation suggests it and I’ve seen it on various forums, e.g., here. I think it should be faster because it’s written in C. That being said, I’m a complete beginner and you probably would know more than me.