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

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

Зачастую мне удается подобрать контр-тесты к своим полным решениям уже после их сдачи. Я не помню всех задач, но я точно валил свое accepted-решение задачи с сортировкой по полярному углу в long double с применением atan2 в одном из первых образовательных раундов (или даже в самом первом). Есть ли на codeforces механизм добавления тестов к задачам в уже завершенных контестах и перетестирование решений? Если нет, то мне кажется, что сохранение возможности взламывать решения в любой момент времени с момента завершения контеста и добавление тестов из успешных взломов было бы неплохим усовершенствованием, ведь многие люди дорешивают старые задачи. Если каждый раз перетестировать решения затратно, то можно, например, накапливать изменения и делать это раз в сутки, пока все спят или ищут на какую кнопку стать легендарным гроссмейстером, и уведомлять пользователей о падении их старых решений.

Пример

UPD: Приношу свои извинения, задача C. Ближайшие вектора из образовательного раунда 1 была упомянута ошибочно, так как в ней ограничения на координаты 10^4 по модулю. Я перепутал ее с задачей 4774. Выпуклая оболочка с сайта e-olymp, где проходит неверное решение, не смотря на наличие 34 тестов к задаче. В ней ограничения на координаты до 10^9 по модулю, а, как известно, atan2(1, -10^9) и atan2(1, -10^9+1) отличаются в 18-м знаке после запятой. Используемый тип long long конвертируется в double и ошибка неизбежна. Нужно либо писать решение в целых числах, либо явно конвертировать в long double.

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

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

Перетестирования решений нет, но не думаю, что авторы задач будут против добавления тестов, если вы им напрямую напишете. Я, как автор, добавил бы ваш тест, если бы он был полезен)

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Я не знал, что у авторов задач есть возможность добавления тестов, спасибо!

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится -38 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ни один набор тестов, кроме полного, не может строго доказать корректность решения типичной задачи спортивного программирования. Всегда можно взять правильное решение и поставить там if, чтобы один конкретный тест обрабатывался неправильно.

    Теорема Гёделя здесь совершенно ни при чём.