Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Добавление успешных взломов в системные тесты.
Автор BECEJIb4AK_U, 13 лет назад, По-русски
Я думаю, надо реализовать сабж. Ведь ясно, что и авторы задач могут что-то упустить. Я с этим столкнулся на прошедшем 85-ом контесте. Моё решение задачи B за O(n * sqrt(n) * log(n)) было взломано по времени, но на следующий день успешно прошло все системные тесты за <= 2 сек.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Мне казалось что это уже реализовано. А оно не на грани работало?
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
На системных тестах отработало за <= 2 сек, а ограничения в задаче 5 сек. На взломе решение не уложилось по времени. То есть не хватает довольно серьёзного теста.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Такой функционал есть давно. Но он не автоматический - то есть на стадии ожидания систестов авторы контеста этим и занимаются - добавляют хорошие взломы в основной тестсет.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А может сделать автоматическим? И авторам меньше работы, и проверка более полная будет.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Возможно это не делается автоматически, чтобы избежать ситуации когда валидатор пропустит некорректный тест, который положит очень много правильных решений
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Чем руками забивать тесты из взломов гораздо проще сделать нормальными валидаторы, такая аргументация нелогична в корне.
        Гораздо приятнее сделать нормальный валидатор, чем потом огребать за слабые тесты.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ситуация спорная: можно потом точно также чесать одно место на затылке за ошибку в валидаторе, который пропустит "баг" на взломах, в результате чего куча народу может лечь во время контеста, или в результате последующего некорректного добавления.
          Поэтому существующая на данный момент ситуация проверки авторами во время контеста  совместно с организаторами соответствия условию на включение дополнительных тестов в полуручном режиме более защищена от подобных проколов.
          Да и второй момент: если все подряд начнут добавлять тесты в систему, то можно только представить, до каких количеств через некоторое время разрастётся тестовая база только по одной задаче.
          Так что, наверное, так как есть, пока наиболее оптимально.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Не понимаю. Ошибка в валидаторе положит много решений, а ошибка в авторском решении (которое обычно на порядок сложнее валидатора) или ошибка в чекере не положит? Тем более что при взломах тест проверяется валидатором.
            → Ответить
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Лично Вы сможете 100% гарантировать:
              1. Что валидатор не содержит ошибки?
              2. Что база тестов при автоматическом добавлении не разрастётся до неизвестных размеров?
              Т.е., если эти 2 условия гарантируются, то, естественно, авторежим намного лучше.
              Но тут возникнет ещё одна проблема: а какой из 2-х похожих тестов должен быть в системе: тот что уже есть, или тот, что предлагается кем-то в данный момент добавить?
              Тут не всё так просто, как кажется на первый взгляд.
              → Ответить
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                А по-моему, тут все просто. Система автоматически может добавлять все тесты, даже если они похожи (можно, разве что, не добавлять полностью совпадающие тесты). Хуже от этого никому не будет.

                Насчет гарантий. Лично Вы можете на 100% гарантировать:
                1. Авторское решение не содержит ошибки?
                2. Чекер не содержит ошибки?

                Ведь эти 2 пункта намного более критичны, чем неправильность валидатора. Обычно предполагается что эти 2 пункта выполняются, т.к. все ответы сверяются с авторским решением. Точно так же предполагается что и валидатор правильный. Да и пишется он обычно тривиально.
                → Ответить
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  =============================================================
                  Сначала  отчечу на вопросы:
                  1. Не могу
                  2. Не могу
                  Вы правы - зти пункты точно также критичны, как и те, что перечисли я. Вот поэтому не всё так просто,  тем более что есть ещё и ряд других моментов..

                  → Ответить
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Такое реализовано на топкодере. Там тоже есть валидатор и авторское решение, которые в теории могут содержать баги. Но я уже не помню, когда последний раз был баг в авторском решении или валидаторе.
                    → Ответить
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Казалось бы, исправить валидатор и сделать реджадж проще, чем добавлять 100500 тестов
                → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А можно узнать тест, на котором  O(n * sqrt(n) * log(n)) получает ТЛЕ? У меня все тесты проходило на компе
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    n = 100000
    a[i] = 83160, b[i]= i
    этим я взломал участника BECEJIb4AK_U

    UPD : я все-таки подозреваю, что его решение не проходит из-за большой константы, он сеты в вектор кидает.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Имхо всё-таки дело в асимптотике. Константу я уменьшить не могу. Зато могу заменить set'ы на vector'ы, тогда ассимптотика станет O(n * sqrt(n)).
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я пытался этим тестом взламывать участника pdwd, у которого была асимптотика такая же O(n*sqrt(n)*log(n)), но вместо вектора из сетов, у него был массив векторов, но у него все успешно прошло. Значит все-таки такая асимптотика проходит. А из-за того, что ты кидаешь в вектор сет, у тебя большая константа.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Согласен. Уменьшается ассимптотика не всего решения, а первой половины, где для каждого делителя запоминаются индексы икcов, делящихся на него.
          → Ответить