Подсчет количества квадратных уравнений с заданными корнями

#алгоритм

Задача заключается в том, чтобы посчитать количество возможных квадратных уравнений
при заданных корнях.

В программу поступает список длина списка и список с возможными корнями, к примеру
[1,1,2,3]
Нужно посчитать количество различных квадратных уровненный которые можно составить
с парами из этого списка. В этом случае пары будут выглядеть так [(1, 1), (1, 2), (1,
3), (2, 3)]. Если хотя бы один коэффициент различается уравнения считаются разными.
В этом примере максимальное количество 4.

Максимальная длина входящего списка 2*10^5. А числа содержащиеся в списке по модулю
не превышают 10^9. Время ограничено в 1 секунду. Память в 256 мегабайт.

Очевидно, что для решения этой задачи не нужно в лоб строить все возможные уравнения.
Достаточно посчитать количество не повторяющихся пар.

Моё решение:

import itertools
N=int(input())
tmp=[int(i) for i in input().split()]
lst=sorted(set(list(itertools.combinations(tmp, 2))))
print(len(lst))


Вроде бы компактно и просто, но по времени и памяти укладывается далеко не всегда. 

Результат тестировщика: 

AAAAAAAAAAAAAAAAWWWWAAAAAWWWWWAAATWWTTTMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM

 A = ACCEPTED = решение засчитано как верное
 W = Wrong Answer = неверный ответ на тесте
 T = Time limit exceeded = решение не уложилось в отведенное процессорное время
 M = Memory limit exceeded = решение не уложилось в отведенное ограничение по памяти


Подскажите как можно более оптимально решить задачу. 

p.s. Вариант Harry, дал следующий результат:

N=int(input())
tmp=[int(i) for i in input().split()]
N = len(sorted(set(tmp)))
M = (sum(tmp.count(x) - 1 for x in tmp) // 2)
print(int(N*(N-1)/2+M))

AAWAAAAAAAAAWAWWWWWAAWAWWWWWWAWWWAWWWAAWWWAWWWAAWTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

    

Ответы

Ответ 1

Ну, если я верно понял вашу задачу - из множества вам надо выбрать все различные пары.

Сортируем (самая длинная операция, но сортировка 200000 элементов - дело очень быстрое...),
и, линейно проходя, смотрим


сколько есть разных значений корней - N  
сколько есть корней, которых одинаковых хотя бы 2 - M


В вашем случае N=3, M=1.

Все, искомое число - N*(N-1)/2+M (в вашем случае 3*2/2+1 = 4).

Думаю, напишете сами? Потому как я в Python не сведущ... Но уверен - встроенная быстрая
сортировка в Python есть :) Если же корни поступают так, как у вас - отсортированными
- то вообще проблем нет.

P.S. Если это общедоступный ресурс - дайте URL поиграться...

P.P.S. Попробуйте этот код:

#include 
#include