Блог пользователя nickpros

Автор nickpros, история, 7 лет назад, По-русски

Не уверен, но кажется в задаче С с регионалки неполный набор тестов. После завершения контеста я поспрашивал решения у своих друзей и с удивлением обнаружил, что большинство из них С решало так: найдем диаметр дерева и его глубину, тогда рассмотрим поддеревья конца диаметра исходного дерева, в них пройдем по глубинам исходного дерева и соединим их по диаметру.

Это решение неверное. Причина: из условия можно сделать вывод, что корень дерева не является листом (потому что у него есть дети), а потому если диаметр кончается в корне, мы не можем подвешивать к нему степени. Соответственно решение должно выводить неверный ответ.

Контртесты подбираются легко: в них диаметр должен кончаться в корне (и при этом степень корня равна единице). В частности, подходит бамбук. Например, при n = 3, m = 2 ответ будет 6, в то время как вышеописанное решение выведет 9.

  • Проголосовать: нравится
  • +48
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем nickpros (предыдущая версия, новая версия, сравнить).

»
7 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

День добрый. Я автор идеи и я же готовил задачу.

Да, там нет ни одного теста в котором степень корня равна 1. Более того это изначально так и планировалось (увы) и это ограничение есть даже в валидаторе.

Дело в том, что когда я предлагал задачу формулировка была дана для не подвешенных деревьев (просто осуществлялось подвешивание ко всем листам дерева), но с выделенной специальной вершиной (она же корень в текущей версии) и если эта вершина является листом, то это вносит некоторые неудобства в том, что к нему тоже подвешивают (в отличии от "корневой" версии в которой корень просто не считается как лист и такого не происходит).

Условие писали немного другие люди, и я немного протормозил в этом месте, а потом случилось тестирование и менять тесты было поздно.

Я сильно извиняюсь и надеюсь это не сильно подпортило вам впечатление от задачи и региона в целом.

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

У нас было много дурацких вопросов о том, "если у корня только один потомок, то это лист", и были вопросы типа "А верно ли что дерево — не бамбук"? При этом условия допускали бамбук и условие задачи оставалось корректным. Но в разборе случай бамбука не рассматривался. Тогда мы уточнили и узнали, что тестов на бамбук нет (и узнали, что авторами задачи бамбук и не предполагался). Общего объявления делать не стали, ибо условия были корректны.