Однажды один рассеянный профессор дал задание студентам: произвести выборку без повторений случайного непустого подмножества объектов из набора данных. Результат выполнения…

Давайте разберемся с условием задачи и решим ее пошагово.

Условие задачи (подробное объяснение)

есть несколько подтестов, для каждого из них даны:

• N — длина объединенного списка объектов, полученного студентами.
• M — количество объектов в исходном наборе (нумерация объектов от 1 до M).
• K — число студентов.

На входе — длинный список из N элементов, каждый из которых — номер объекта из множества 1..M. Этот список — объединение списков, которые студенты могли подготовить, выбирая непустые подмножества объектов (без повторений внутри каждого подмножества). Пусть каждый студент выбрал своё непустое подмножество, и их объединение дает итоговый список.

Задача: определить, существует ли набор таких подмножеств (по одному для каждого студента), что объединение их элементов дает исходный объединенный список без пропусков и лишних элементов. То есть, можно ли разбить исходный список на K частей так, чтобы каждая часть — непустое подмножество, и объединение всех этих частей — первоначальный список.

Если да, нужно вывести YES, иначе — NO.

Что нужно понять и проверить?

• В исходном списке a каждый элемент может встречаться несколько раз.
• Эти повторения можно "распределить" по студентам так, чтобы каждое студенческое подмножество было непустым, и сумма всех этих подмножеств дала исходный список.
• Важное ограничение: каждый элемент может принадлежать только одному студенту, потому что списки студентов — не пересекаются внутри, но могут пересекаться по одинаковым объектам? В условии указано, что "выборка без повторений", так что внутри одного подмножества — уникальные элементы. В списке после объединения эти подмножества «склеены» вместе, и элементы могут повторяться.

Основное правило:

• Для каждого уникального номера объекта из a, ему соответствуют несколько вхождений.
• Эти вхождения нужно "распределить" по разным студентам, так чтобы у каждого студента было хотя бы одно вхождение этого объекта, если он есть в списке.

Ключевой момент:

• Чтобы представить исходный список как объединение непустых подмножеств — у каждого уникального элемента в списке a должно быть не меньше, чем число его встреч: count[a_i].
• Если количество встреч одного элемента больше K — это невозможно, потому что в каждой группе (подмножестве студента) он может быть только один. Тогда есть смысл, что каждый студент может взять этот объект только один раз, и total count[a_i] должно быть не больше K, иначе нельзя распределить его по студентам.

Но так как элементы могут встречаться несколько раз, и мы не знаем, как именно студенты собирали свои списки (они могли выбрать один и тот же объект, и его встречается много — в этом случае нужно понять, можно ли так разбить).

Обоснование и решение:

• Для каждого элемента x подсчитаем количество вхождений count[x].
• Если существует какой-то x, для которого count[x] > K, значит один студент не сможет "включить" все встречающиеся x в свой список, а остальные студенты — нет, значит, ответ NO.
• Иначе, ответ YES.

Пошаговое решение:

1. Прочитать количество подтестов.
2. Для каждого подтеста:
   • Прочитать N, M, K.
   • Прочитать список a.
   • Подсчитать частоты появления каждого уникального элемента.
   • Проверить, есть ли элемент x, у которого count[x] > K.
     • Если есть — выводим NO.
     • Иначе — YES.

Это — достаточно эффективный и логичный способ проверки.

Реализация на Python:

Q = int(input())
for _ in range(Q):
    N, M, K = map(int, input().split())
    a = list(map(int, input().split()))

    # Подсчет частот
    freq = {}
    for num in a:
        freq[num] = freq.get(num, 0) + 1

    # Проверка ограничений
    answer = "YES"
    for count in freq.values():
        if count > K:
            answer = "NO"
            break
    print(answer)

Итог:

• Если у какого-либо числа количество встреч больше K, то распределить его невозможно → NO.
• Иначе возможно → YES.

Этот подход работает за O(N) — достаточно беглого подсчета частот.

Если нужны дополнительные разъяснения или пример, я с радостью помогу!