Как приручить Polygon или обратная сторона олимпиад

[yeputons]

Фатальные для задачи проблемы:

1. В вашем условии потерялось требование x <= n. Валидатор его тоже не требует (в соответствии с условием), но в тестах этого нет. А зря.

2. В вашем условии потерялось требование "связный подграф размера x". А чекер его при этом требует.

3. Чекер верит файлу с ответом на слово и не проверяет его в случае YES. Всегда надо проверять оба поданных файла (с ответом участника и с ответом жюри), смотри секцию "readAns paradigm" вот тут (там вообще много полезного про testlib): заводите функцию для чтения файла с ответом и запускаете её и для файла жюри, и для файла участника. И только если оба ответа верны — можно начинать сравнивать. Если у жюри ответ лучше — Wrong Answer, если у участнкиа — Jury Error. Иначе можно случайно сгенерировать все тесты с ответом NO и участники будут получать Wrong Answer.

4. Непонятно зачем в чекере константа maxN. Вы так добавляете ещё одно место (помимо валидатора и условия) которое надо менять. А чекеру эта константа не нужна.

5. В ошибках чекера вершины нумеруются с нуля, а не с единицы, как в условии задачи.

6. Зря используете gcc-специфичный __gcd. Напишите свой (у std::gcd в C++17 свои проблемы, с ним осторожно). В решениях на контесте использовать специфичные конструкции ещё приемлемо, там решение живёт не больше нескольких часов, но в пакете задачи надо всё-таки писать код, который будет работать и через десять лет. Задачи живут очень долго.

7. Ваш генератор всегда выводит рёбра в определённом порядке: от корня к листьям, родитель всегда идёт первым концом. Некоторые решения могут этим пользоваться. Надо перемешивать и порядок рёбер, и порядок вершин внутри ребра, не только сами вершины. Кстати, есть полустандартные генераторы.

Претензии к валидатору, чекеру и генераторам:

1. checkGraphIsTree у вас на самом деле ещё и читает. Название путает, лучше readTree(). Аналогично с checkPermutation — лучше readPermutation(). Я смотрел на main и не понимал, где вы считываете граф.

2. Хорошо бы получать более подробные пояснения от валидатора. Например, если не перестановка — значит, какое-то число встретилось два раза, вот его бы хорошо вывести. Если не дерево — значит, какая-то вершина недостижима из 1, хорошо бы вывести. Имена переменных лучше указывать сразу с индексом: не "v", а "v[" + to_string(i + 1) + "]". Аналогичные претензии к чекеру: не только нет индексов, но и дублируются названия переменных при чтении. Это сильно мешает при отладке.

3. Непонятно зачем вы несколько раз делаете shuffle перестановки в getRandomTree. Достаточно один раз сделать случайную перестановку. Любые попытки "увеличить рандом" дальше в лучшем случае ничего не делают, в худшем случае ухудшают рандомизированность.

Придирки по оформлению условия:

1. Традиционно в условиях пишут не просто "YES", а "YES" (без кавычек). Иначе неоднозначно. Аналогично с нумерацией вершин в формате вывода — с нуля или с единицы. Хотя есть и другое мнение — "примеры являются частью условия".

2. Также хорошо бы выделять строки, которые надо записать в файл напрямую, моноширинным: <<\texttt{YES}>> (без кавычек).

3. Вместо ~--- лучше использовать "---. В английской типографике, если правильно понимаю, тире принято не отделять пробелами от соседних слов, поэтому обычное длинное тире в TeX пишется как --- и приклеивается с двух сторон к словам. В русской типографике принято отделять пробелами. Можно поставить костыль в виде Тире~---это что-то такое (заменили пробел перед тире на неразрывный пробел в виде ~), а можно сразу использовать тире в русском стиле "---. Тогда его как раз отбиваем пробелами с двух сторон в исходном коде, и оно само правильно расставляет неразрывности.

4. Вместо \lfloor лучше сразу писать \left\lfloor и \right\rfloor (аналогично с любыми видами парных вещей, вроде скобок). Тогда при компиляции в TeX эти парные штуки станут правильной высоты, чтобы соответствовать внутренностям. Возможно, MathJax делает это автоматически, но это его специфика.

И немного по мелочи:

а потом в Make файле в вашем редакторе указать зависимость.

Это не Make, это CMake, и речь наверняка не про абстрактный редактор, а конкретно про CLion. Плюс не надо использовать \\ — это будет работать только под Windows, используйте прямой слеш /. Хотя это всё происходит локально, так что неважно. Но если локально — то можете просто скопировать testlib.h себе в папку include рядом с компилятором.

но если кто хочет, отдельно про testlib можно почитать тут.

Ссылка битая.

Но для нашей задачи придумать решение, которое получит TL (и при этом будет достаточно адекватным), довольно непросто.

Решение как правильное, только забываем добавить обратное ребро при чтении + проверить родителей в dfs. Кажется, что такое решение иногда может зациклиться (не уверен).

[wataru]

у std::gcd в C++17 свои проблемы, с ним осторожно

А расскажите, пожалуйста, про эти проблемы или ссылку дайте. Интересно, что там такое.

[yeputons]

Конкретно std::gcd может медленно работать в GCC, потому что реализован через алгоритм Евклида не делением, а бинарно. Это в среднем сразу на 20% медленнее работает абсолютно не по делу. К тому же ядом с ним сразу хочется использовать std::lcm, а он при вызове от двух intов возвращает int. Что иногда приводит к переполнению и UB.

Похожие проблемы есть у некоторых алгоритмов и классов из стандартной библиотеки. Например, std::complex<double> старательно а) разбирает кучу случаев с NaN и +/-inf; б) сохраняет совместимость с сишным _Complex и вызывает функции для операций без инлайнинга. Это тоже существенно замедляет код.