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

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

В последнем раунде CodeCraft-20 была дана задача.

Решение её очень простое.

Spoiler

Далее будут описаны детали моего решения. Предупреждение для тех, кто не решал задачу и хочет самостоятельно её решить.

Во время раунда я написал ужасное не самое лучшее решение. А именно перебирал случайные пары чисел i и j такие, что ai % p ≠ 0 и bj % p ≠ 0 и за O(n) проверял, подходит ли нам эта пара. Такой процесс повторял максимум 150 раз или пока не найдется ответ. Посылка.
Полагаю, данное решение при наличии времени и желания можно взломать :)

После конца раунда я был уверен, что моё решение упадёт на полном наборе тестов. Но, как вы могли заметить, оно получило вердикт "полное решение". Тогда, после окончания тестирования, я решил проверить, насколько в задаче слабый набор тестов :). Я решил повторять описанный выше процесс не 150 раз, а ровно 1. Да-да. Выводить в ответ какую-то одну случайную пару индексов, найденных по описанным условиям выше. Посмотрите на две посылки ниже и попытайтесь найти отличия между ними. Их нет :))

Полное решение
Неправильный ответ на тесте 3

Набор тестов состоит из 156 тестов. А код выше проходит 3-й тест с вероятностью 50%. Да! Код, проходящий 3-й тест с вероятностью 50% проходит оставшиеся 153! Ну разве это не впечатляет?! :))

Почему 50%

Целью данного поста не является обвинить/оскорбить авторов контестов или тестировщиков задач. А скорее является призывом к более ответственному подходу создания раундов и тестирования задач. Я понимаю, что создание раундов, их тестирование и организация всего — далеко не простая задача. Все люди мыслят по-разному и учесть все слабые места решений и самой задачи довольно сложно. Ну а ещё, просто захотелось поделиться интересным случаем :)

Полный текст и комментарии »

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