Оптимизация кода Python быстрее, чем за 4 секунды ⇐ Python

[Anonymous]

Я написал код для решения онлайн-проблемы.

Код: Выделить всё

mustConstraint = set()
notConstraint = set()
violated = 0
satisfied = 0

for i in range(0, int(input(''))):
constraint = input('')
mustConstraint.add(frozenset(constraint.split()))

for i in range(0, int(input(''))):
constraint = input('')
notConstraint.add(frozenset(constraint.split()))

for i in range(0, int(input(''))):
group = input('')
group = set(group.split())

for x in mustConstraint:
if x & group == x:
satisfied +=1

for y in notConstraint:
if y & group == y:
violated += 1

violated += len(mustConstraint) - satisfied

print(violated)

Подводя итог проблемы, первая строка входных данных содержит положительное целое число X, где X => 0. Следующие X строк входных данных будут содержать два слова, разделенных пробелами. Эти два слова должны находиться в одной группе. следующая строка ввода будет содержать еще одно положительное целое число Y, где Y => 0. Следующие строки ввода Y будут содержать два слова, разделенные пробелом. эти два слова не должны находиться в одной группе. следующая строка входных данных будет содержать целое положительное число G с G >= 1. Каждая следующая строка входных данных G будет состоять из трех разных слов, разделенных одинарными пробелами. Эти три слова были помещены в одну группу.
Выведите целое число от 0 до X+Y, которое представляет собой количество нарушенных ограничений.
Я настоятельно рекомендую вам посетить проблемный сайт здесь, поскольку проблему гораздо легче понять с помощью предоставленных примеров случаев и их объяснений.
К сожалению, поскольку последний пакет содержит ~ 300 000 входных данных. , мои вложенные циклы for работают слишком медленно и не укладываются в лимит времени в 4 секунды. Может ли кто-нибудь помочь мне оптимизировать мой код?

[img]https:/ /i.sstatic.net/1aGVpz3L.png[/img]

Большая часть задержки происходит из-за этого блока:

Код: Выделить всё

for i in range(0, int(input(''))):
group = input('')
group = set(group.split())

for x in mustConstraint:
if x & group == x:
satisfied +=1

for y in notConstraint:
if y & group == y:
violated += 1

каждый вложенный цикл for выполняет 100 000^2 итерации, что в общей сложности составляет 20 миллиардов итераций для формирования этого блока кода (2*100 000^2)
если бы кто-то мог найти способ сократить количество итераций, это имело бы существенное значение.


Подробнее здесь: https://stackoverflow.com/questions/787 ... -4-seconds