Я видел как-то статейку как раз, "Путь проблемсеттера", так что там что-то об этом рассказано. Правда статье той почти 2 года.

Отличная тема! Хоть и не раз уже всплывала в комментариях, но все равно хотелось бы узнать, как это делают профессионалы.

Я со своими знакомыми составлял однажды условия для небольшой школьной олимпиады... Фактически, это своеобразным срезом знаний тех, кто занимался на школьном же кружке, а потому были сначала определены темы, на которые надо придумать задачи (бинпоиск, немного жадных реализаций, основы дп, bfs/dfs). Это служило каркасом для условий, потом на него накладывались ситуации, персонажи — вся легенда. После составления задачек раскидали их по сложности, ее не так просто оказалось оценить заранее. Довольно тяжелой оказалась часть с упрощением условий. По ходу контеста пришлось докидывать клары и чуть править задачи, так что стало понятно, что этому стоило уделить больше времени (впрочем, не исключаю, что это было из-за того, что участникам недоставало опыта, а оттого и интуиции).

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

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

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

Думаю, все же не стоит писать подобные блоги в "Новости".

Действительно,как и где создавать свои задачи,а потом их внедрять
на своё собственное тренировочное соревнование?Где-то слышал,что "создавать задачи нужно на Polygon'e",
но как?Где-то ведь должно быть инструкция(и т.п). Посоветуйте пожалуйста ресурс по обучению создания своих задач на Polygon'e.

Спасибо.

Как правило есть некоторый круг людей, у которых возникают  различные задачи (обычно каждый любит определенные жанры), они собираются, обсуждают, отсеивают баяны, заполняют бреши (чтобы было нечто вроде аккуратной ступеньки по сложности), были представлены разнообразные жанры и еще много разных нюансов. Очень часто в процессе обсуждения задача превращается в нечто совершенно далекое от первоначальной идеи, часто она усложняется или упрощается, чтобы контест был более сбалансированным и т.д. и т.п. Все это в идеале, когда составителей хотя бы 3-4. Если меньше, то все немного по-другому, но общие принципы составления те же.

Для меня обычно происходит одним из нескольких способов:

• Берется какая-то упрощенная формальная жизненная модель (люди стоят в очереди что-то хотят, кто-то куда-то едет и так далее) и пробуешь в рамках нее сформулировать и решить задачу. Обычно сформулировать получается, а решить — нет. Однако в процессе её придумывания находятся какие-то решаемые переформулировки/упрощения — из них и получается задача.
• Бывает, что задача придумывается из соображения обобщения чего-то тривиального или понятного. Берется какая-то известная задача/модель и ты такой думаешь — давайте навесим вот сюда веса или цвета. Бывает, что задача от этого не перестает быть решаемой, но требует более глубокого анализа и подхода посложнее.
• Иногда задача рождается из какого-то найденного где-то факта/трюка/алгоритма. Чаще всего это бывают научные статьи по CS тематике. Здесь важно найти что-то такое, что решается за час-два (часто статьи эксплуатируют слишком сложные идеи), не гуглится и вообще находится в нашей тематике и традициях.

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

Один раз я покупал раскладную открытку. Возник вопрос о критериях складываемости произвольной картонной структуры. Оказалось, что если ограничиться почти что наипростейшей структурой (4 элемента в 2D), получается подходящая задача.

Один раз я думал о Шекспире. А именно, "Shakespeare" = "Shake" + "speare" или всё-же "Shakes" + "peare"? Найти все такие слова оказалось не сложно, там только одна небольшая хитрость, из которой появилась подходящая задача. (Пример: "crystallion" = "cry" + "stallion" = "crystal" + "lion".) Шекспир предоставил эпиграф.

Один раз я написал задачу по знаменитой статье Felleman & Van Essen о структуре зрительной части мозга. Между регионами этой части мозга фактически два типа рёбер: те, по которым данные двигаются "вверх" извне, формируют почти directed acyclic graph, и другие рёбра, по которым, считается, предсказания интерпретаций идут в противоположную сторону. Topological sort (примерно) снизу вверх даёт вот эту знаменитую диаграмму:

Так что я сделал из этого задачу, потому что это жутко интересно, компьютерщики в общем недооценивают сколько системным нейрофизиологам известно о головном компьютере, и если бы мне это рассказали когда я ещё ничего не знал о мозге, это могло бы быть даже полезно.