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

Вы можете использовать операции над множествами более эффективно:

Для повышения эффективности читайте все входные данные одновременно.

Используйте словари для хранения ограничений и наборов для представления групп.

Эффективно проверяйте ограничения, перебирая каждую группу и обновляя счетчик нарушений.

Так:

import sys

input = sys.stdin.read
data = input().splitlines()

index = 0

# Read must constraints
must_constraint_count = int(data[index])
index += 1
must_constraints = []
for _ in range(must_constraint_count):
    must_constraints.append(set(data[index].split()))
    index += 1

# Read not constraints
not_constraint_count = int(data[index])
index += 1
not_constraints = []
for _ in range(not_constraint_count):
    not_constraints.append(set(data[index].split()))
    index += 1

# Read groups
group_count = int(data[index])
index += 1
groups = []
for _ in range(group_count):
    groups.append(set(data[index].split()))
    index += 1

# Check constraints
satisfied = 0
violated = 0

# Check must constraints
for must in must_constraints:
    in_same_group = False
    for group in groups:
        if must.issubset(group):
            satisfied += 1
            in_same_group = True
            break
    if not in_same_group:
        violated += 1

# Check not constraints
for not_c in not_constraints:
    for group in groups:
        if not_c.issubset(group):
            violated += 1
            break

print(violated)

Обработка ввода: для повышения эффективности весь ввод считывается одновременно с использованием sys.stdin.read.

Хранение ограничений. Ограничения хранятся в списках наборов для удобства проверки.

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

Проверка ограничений:

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

Для каждого не-ограничения проверьте, является ли набор ограничений подмножеством какой-либо группы. Если да, то оно нарушено.

Производительность:

Использование множеств и метода issubset() делает проверку ограничений эффективной.

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

Дополнительную помощь по сложным общим операциям можно найти в Шпаргалке Big-O.

Кроме того, Временная сложность Python очень хорошо объясняет характеристики производительности встроенных типов данных Python.

Два решения, оба легко проходят все тесты.

Решение 1. Минимальные изменения

Замените большие внутренние петли крошечными петлями над тремя парами группы, т. е. измените

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

к этому:

    a, b, c = group
    for pair in {a, b}, {a, c}, {b, c}:
        if pair in mustConstraint:
            satisfied += 1
        if pair in notConstraint:
            violated += 1

Решение 2. Всего две операции над набором

Все три раздела определяют набор пар. Помогает поместить это в функцию. Затем найдите/подсчитайте нарушения:

• Пары, которые должны быть, но не являются.
• Пары, которых не должно быть, но которые есть.

from itertools import combinations

def pairs():
    return {
        frozenset(pair)
        for _ in range(int(input()))
        for pair in combinations(input().split(), 2)
    }

must = pairs()
must_not = pairs()
are = pairs()

print(len(must - are) + len(must_not & are))