Действительно в контесте были интересные задачи и я не утверждаю, что контест плохой, однако некоторые вещи мне (и я думаю не только мне) мягко говоря не очень понравились. Например D или C. Начну с задачи Саша и интересный факт из теории графов 1) Во-первых для div1D, она слишком проста по сравнению с С например (которая была слишком сложна, её сдало примерно столько же человек сколько E и гораздо меньше, чем D, что тоже не есть хорошо). 2) Во-вторых в авторском решении используется мало известная теорема(Теорма Кэли https://www.turgor.ru/lktg/2018/3/3-1ru-sol.pdf здесь и https://www.sciencedirect.com/science/article/pii/0097316590900644?via%3Dihub здесь про неё можно почитать по-подробнее), да это решение можно было придумать без использования гугла, однако на это тратилось существенное время, а гуглилось за 2-3 минуты. Так что участники, которые обычно не используют гугл на контестах (например я) явно проигрывали во времени. По задаче A: возможно это баг системы, но мой код на раунде получил TL на системных тестах, однако потом тот же код получил AC, что как минимум странно По задаче B — довольно не плохая задача, но претесты довольно слабые (например у Ильдара Гайнулина эта задача упала на сис. тестах), однако это не делает задачу плохой, так же действительно было бы не плохо сделать длину строки 10^5, т.к. это сделает задачу более подходящей для div1B, однако это тоже субъективно Задача С — просто слишком сложна для div1C
В общем раунд получился не из лучших, т.к. хороших задач максимум половина, а остальные в лучшем случаи не очень хорошие. Если в чём-то со мной не согласны пишите в комментариях, я постараюсь на всё ответить.
По поводу div1D можно долго дискутировать, так что не будем начинать.
В Div1B претесты были вполне хорошие. Было не столь просто покрыть все случаи (это по поводу решения Ильдара) в претестах и при этом не сделать очень много претестов.
Div1C вполне вписывалась по сложности. Может не такая приятная в написании из-за крайних случаев, но это не столь критично как мне кажется.
По поводу D полностью согласен с Вами По поводу B решение упало далеко не только у Ильдара, но и STO, Федосеева Тимофея, также было не мало взломов По поводу C, всё же разница в количестве сдавших и длине решения существенно отличается от D, было бы логично поменять их местами
лично мне не принципиален порядок задач
Важен не порядок задач, а их стоимость, например человек решивший D или C получит больше баллов, чем решивший C, а поэтому желание решать C отпадает, что не есть хорошо
В этот раз баллы за решение C и D совпадали
Да, но D решалась гораздо легче и при выборе D или C однозначно выбиралась D, также при выборе C или E, скорее E т.к баллов больше, а решило примерно столько же человек
Автокомментарий: текст был обновлен пользователем Degalat57 (предыдущая версия, новая версия, сравнить).
Я постарался высказать свою аргументированную позицию, поэтому прошу перед тем как поставить дизлайк, написать соответствующий комментарий, что бы я понимал, что конкретно не так в моих рассуждениях
Теперь можно ставить? :)
по 1) да возможно тяжело, но если длина разбора С почти в 3 раза больше разбора D, то это кажется довольно странным и можно предположить, что порешает меньшее количество человек
2) судя по комментариям под разбором не только я и многие мои друзья (как Шуклин Максим например) не знали эту теорему, а тем более расширенную её версию
3) Довольно странно что на претестах мое решение работало около 0,5, а на сис. тестах получило TL, так как время работы зависит в моём решении только от n, а не от самих элементов массива + в TL варианте у меня так же был корректный вывод (к сожалению не знаю, как прикрепить фотку, чтобы доказать это), но система не засчитала его
4) да не спорю и не отношу B к плохим, однако странно что у двух людей с рейтингом почти 3000 она упала
1) Мне кажется, что в данном случаи очень даже говорит, т.к в решении D я не вижу ничего идейного, кроме теоремы Кэли, также ничего сложно реалезуемого, решение задачи C по моему мнению придумать было сложнее 2) Получается, что задача на знание/умение гуглить, не очень похоже на хорошую задачу, а известность теоремы довольно субъективная вещь (опять же комментарии к разбору говорят в мою пользу) 3) если количество различных элементов увеличить даже в 100 раз, то решение не станет работать существенно дольше, что бы удвоить время работы, надо квадратично увеличить количество различных элементов и я считаю, что этот случай с большим количеством различных чисел должен быть в претестах 4) Нет и я не утверждаю, что задача плоха
Поправьте меня, если я не прав, но чтобы найти формулу для решение задачи в Интернете, нужно как минимум знать про существовани формулы Кэли, иначе непонятно, по каким словам искать :)
"Слишком проста" или "слишком сложна" — критерии довольно субъективные и различаются для разных участников. При этом часто сложно авторам предугадать, какая задача окажется более решаемой; в Div.1 раундах не редкость, что задачи стоят не в порядке сложности. Хотя, мне D действительно показалась проще.
Такое бывает (не может программа два раза отработать точно одинаковое время)
Очень неожиданный факт: претесты не обязаны покрывать все случаи :) То, что какое-то одно решение упало не должно быть претензией авторам :)
Слабые претесты — это когда падает где-то треть часть решений, а не несколько.
Можно здесь подробнее? Судя, по посту, насчитал только B и C.
Поправляю. Решение задачи D гуглится по следующим словам: "количество деревьев из N вершин с путем a-b длины k"
Да действительно один из вариантов
На тему D, я вбил запрос количество способов построить дерево и по первой или второй вкладке получил эту теорему (до этого я её не знал), поэтому совсем необязательно её знать
По задаче B как я уже писал выше, упала задача далеко не у одного человека, но как я и написал в посте это не делает задачу плохой
По задаче A довольно странно, т.к в зашедшем варианте время работы 0,951, что довольно далеко от 1, также, что очень странно в TL варианте у меня был вывод!
Когда я говорил о половине задач, я не рассматривал div2AB, также div1F, хотя как понимаю, там тоже решение не из приятных, а из остальных, не очень хорошие D, С и A (но по поводу A субъективно)
Решение в div1F очень красивое и просто пишется. Можно в этом убедиться, посмотрев код.
Да, т.к. я над ней не думал, то и не упомянул в посте и не рассматривал её
Автокомментарий: текст был обновлен пользователем Degalat57 (предыдущая версия, новая версия, сравнить).
Раунд мне тоже не понравился(задача D действительно плохая по моему мнению, после 20 минут раздумий я решил загуглить запросом "number of different trees with n nodes" и нашел ссылку на вики, а С и Е гробы, поэтому место в положение ниже топ30 определялось быстротой решения А, Б и в большинстве скоростью загугливания Д).
Но я не согласен с автором:
A: Действует простое правило: видишь лимит 1с и ввод 300к чисел — используй scanf/printf.
B: Претесты были нормальные, в претестах были тесты типа aba и aabaa, у всех видимо падало решение на тесте с одной буквой.
По поводу сложности задач: сложность задач можно прямо в онлайне на контесте определять количество решений по каждой задачи. Уже на 45 минуте можно было почти однозначно понять, что D легче, чем С.
По поводу A, я не утверждаю, задача сложная или плохая, я просто говорю, что конкретно у меня задача довольно неожиданно и что конкретный случай должен быть добавлен в претесты По поводу B, да претесты были не очень плохи, однако было довольно много взломов и падений у высокорейтинговых участников, также было бы не плохо увеличить длину строки По задаче D согласен и мне это не нравиться т.к. плохо когда из двух задач с одинаковой сложностью одна очевидно проще