Организация конкурсов - проблемы входных данных.

Нередко для решения какой-то прикладной задачи может оказаться выгодным провести конкурс. Данный подход за счет привлечения достаточно большого числа участников позволяет получить неплохие решения для задачи. Особенно выгодным этот подход может оказаться для получения решения НП-полных или же плохо исследованных задач.


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


Но что делать, если не имеется необходимого набора данных и чекера или же задача является выдуманной специально для данного конкурса? В данном случае возникает необходимость как-то генерировать наборы исходных данных, на которых можно не сложно проверить удовлетворение решения нашим требованиям. И вот тут появляется краеугольный камень данного вида задач: что делать с генерацией тестов, чтобы все участники были в равном положении (т.е. тесты для всех должны быть одинаковыми)?


В данном направлении я вижу 3 подхода:



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

  2. Предоставить алгоритм некоторого псевдослучайного генератора входных данных, который на основе пары параметров генерирует все необходимые данные. При этом использовать особенности генерации запретить сложно, в силу того что полученный код может быть очень запутанным и проверить его достаточно затруднительно. Данный метод лишён недостатка предыдущего, однако, тоже не идеален. При выборе псевдослучайного алгоритма генерации у него могут оказаться особенности, о которых организаторы даже не подозревали. И в итоге можно получить от конкурса не совсем ожидаемый результат. В частности лучшие решения вообще не будут применимыми на исходной задаче. При этом изменение алгоритма генерации может достаточно сильно рассторить участников, которые использовали его недостатки. Например в конкурсе Acceler8 2011 такой неожиданностью оказались проблемы с генерацией матрицы линейным конгруэнтным методом. В результате чего при больших размерностях задачи, матрицы в большинстве случаев получалась вырожденной и решалась в разы проще. Кстати данная проблема, в той или иной мере, осталась и после изменения способа генерации.

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


Теперь немного о возможных применениях данных методов и потенциальным решениях их проблем:



  1. Отлично подходит для сложных задач с малым входом.

  2. Можно решить часть потенциальных проблем увеличив число алгоритмов генерации данных. Действительно подходит для задач с огромными данными.

  3. Отлично подходит для большого класса потенциальных задач.


Удачного проведения конкурсов!


For more complete information about compiler optimizations, see our Optimization Notice.