Não temos um algoritmo para escrever um bom problema para a Maratona, mas temos algumas heurísticas que podem ajudar! Vamos, como tudo em computação, por partes:

O enunciado (não é necessário estar pronto para a submissão da proposta.)

• Deve ser a última coisa a ser feita! Montar um estória é sempre legal, mas começar por aqui pode dar margem a interpretações diferentes da que você quer.

• Na maioria dos problemas, seja breve: quantos mais palavras gastar para explicar uma parte do problema, maior a chance de confusão na hora da leitura.

• Aborde temas leves e evite polêmicas. Pandemias, desastres, e coisas do gênero podem ser facilmente substituídas por outras pautas.
• Dê nomes aos personagens, cidades, eventos, etc.
• Deve ser auto-contido: quem estiver fazendo o problema deve ter toda a informação para entender a tarefa a ser feita apenas lendo o seu texto.

A tarefa/o problema (necessário para a submissão)

• Pode abordar qualquer número de temas vistos em cursos da área da computação, mas evite  conhecimentos muito específicos. Por exemplo, se só duas pessoas no mundo sabem como resolver o seu problema, é possível que ele seja legal para a Maratona de daqui a dez anos.

• Descreva-a da forma mais objetiva possível na sua proposta.

• Tenha pelo menos uma solução esperada: não é raro termos uma ideia super legal que nos leva a um problema igualmente difícil de ser resolvido.
  • Não é esperado que você já tenha código escrito, mas que tenha confiança de que sua ideia realmente resolve o problema.

• Um erro muito comum é pensar no algoritmo antes do problema; pode ser o caso de existir um algoritmo mais simples/eficiente para a tarefa que você pensou, ou então o algoritmo não resolver corretamente a tarefa descrita.

• Tente classificar o problema em termos de dificuldade. Para isso tente responder a essas perguntas:
  • Qual o perfil do time que vai resolver esse problema? Só quem está treinando há muito tempo, ou gente nova também deveria conseguir fazer?
  • Quais conhecimentos são imprescindíveis para chegar na solução? Por exemplo, um problema de fluxo é, em geral, impossível de ser resolvido por quem não viu nenhum algoritmo.
  • O quão específica é cada observação que deve ser feita pelo time?

• Pense muito bem em como testar seu problema:
  • Podemos só contar com casos aleatórios ou precisamos fazer os casos de teste um a um para saber se o time resolveu o problema? Quais são os casos de borda (corner cases) relevantes?
  • Quais heurísticas podem ser usadas pelos competidores? Elas devem ser pegas por algum teste.
  • Evite problemas com saída apenas SIM ou NÃO, eles são muito mais difíceis de testar. No geral, podemos pedir uma saída adicional (como a menor solução lexicográfica).
  • Ele admite múltiplas saídas? Isso não é ruim, mas requer mais cuidado durante a preparação para termos certeza que tudo está funcionando.
  • O problema tem várias soluções? Quais complexidades devem ser aceitas e quais rejeitadas para que ele atenda à sua vontade? Por exemplo se você quer testar se o time sabe ordenar em O(N log N), então temos de fazer N grande o suficiente para separar identificar automaticamente as soluções O(N²).

Não se preocupe em ter tudo perfeito no primeiro momento, mas quanto mais completa for sua submissão, maior a chance dela ser aceita. Obrigado pela ajuda e nos vemos na Maratona!