Знакомства в лагере «Кыргызчыл»


Отправить решение Решать в редакторе

Сложность: 80%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В летнем лагере «Кыргызчыл» на Иссык-Куле вожатые составили отчёт: для каждого из n школьников записали, со сколькими другими школьниками он познакомился за смену, — это числа d[1], …, d[n]. Знакомства взаимные, с самим собой знакомиться нельзя, а два школьника либо знакомы, либо нет.

Директор подозревает ошибку в отчёте. Для каждого отчёта ответьте на два вопроса:

  1. может ли вообще быть, что школьник i знаком ровно с d[i] другими (для всех i сразу)?
  2. может ли при этом ещё и оказаться, что через цепочки знакомств связаны все школьники (любые двое — знакомые, знакомые знакомых и так далее)?

Рисунок

Входные данные

В первой строке — число T (1 ≤ T ≤ 10⁴) — количество отчётов. Каждый отчёт задан двумя строками: в первой — n (1 ≤ n ≤ 2 · 10⁵), во второй — n чисел d[i] (0 ≤ d[i] ≤ n − 1). Сумма всех n не превосходит 2 · 10⁵.

Выходные данные

Для каждого отчёта выведите в отдельной строке два слова YES или NO — ответы на первый и второй вопросы.

Пример 1

Вход:

4
4
3 3 1 1
4
1 1 1 1
4
2 2 2 2
1
0

Выход:

NO NO
YES NO
YES YES
YES YES

Пояснение

Отчёт 3 3 1 1 невозможен: двое школьников знакомы со всеми тремя остальными, а значит, и у каждого из двух других хотя бы два знакомства. Отчёт 1 1 1 1 возможен (две пары знакомых), но тогда школьники не связаны в одну компанию. Отчёт 2 2 2 2 — это четыре школьника по кругу.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов n ≤ 6.

Подсказка

Теорема Эрдёша — Галлаи: невозрастающая последовательность d[1] ≥ … ≥ d[n] с чётной суммой реализуема простым графом тогда и только тогда, когда для каждого k выполнено d[1] + … + d[k] ≤ k(k − 1) + Σ_{i > k} min(d[i], k).


Комментарии

Еще нет ни одного комментария.