Chamadas de Problemas

 

Chamada de Problemas para a Sexta Maratona Mineira de Programação (Texto Base: Maratona Nacional)

O Comitê de Provas da Maratona Mineira de Programação está solicitando problemas para a sexta Maratona Mineira, que ocorrerá em maio de 2017, em Belo Horizonte.
Os autores dos problemas selecionados serão convidados a participar do desenvolvimento final da prova.

A etapa de submissão de propostas de problemas para a VI Maratona Mineira de Programação tem início dia 27/10/2016 e término no dia 13/01/2017. Interessados em enviar problemas devem: Escrever um enunciado do problema em latex. O enunciado deve ser composto pelas seguintes partes:
  • Texto: Nesta parte, o autor deve descrever claramente a questão, de forma que seja possível compreender exatamente qual o problema que deve ser resolvido sem a necessidade de ler outras partes do enunciado. Preferencialmente, o enunciado não deve conter apenas a descrição formal do problema, mas também um contexto baseado em uma situação real ou fictícia.
  • Especificação de entrada: Nesta parte, o autor deve especificar de forma não ambígua o formato dos dados de entrada, sem esquecer de definir os valores que as variáveis do problema podem assumir.
  • Especificação da saída: Nesta parte, o autor deve especificar de forma não ambígua o formato dos dados saída.
  • Exemplos: Nesta parte, o autor deve fornecer um ou mais exemplos de entrada e saída válidos, seguindo os formatos especificados anteriormente. Caso o autor deseje, ele pode fornecer também uma explicação dos exemplos.
Escrever um editorial em latex, contendo uma descrição precisa da solução do problema, incluindo complexidade assintótica de tempo.
A submissão será composta por duas etapas:
1) Submissão de ideias de problemas
2) Finalização dos problemas

1) Submissão de Ideias de Problemas
Nesta etapa, o autor do problema descreverá em alto nível a proposta de problema. Essa descrição deverá conter:
  • Um nome para o problema (não precisa ser o nome final).
  • O grau estimado de dificuldade.
  •  O(s) temas do problema (por exemplo, grafos, ad-hoc, strings).
  • Uma descrição em alto nível do problema (não é necessária uma história neste momento mas ela é bem vinda).
  •  Uma descrição em alto nível das estratégias possíveis para solução; para problemas em que o tempo de execução seja relevante, indicar a complexidade máxima aceitável.
  •  Corner-cases e outros detalhamentos que são esperados que o competidor leve em consideração quando estiver desenvolvendo a solução do problema.
  •  [Opcional] Alguns casos de teste que facilitam o entendimento da questão.

2) Finalização dos Problemas
Nesta etapa, os autores serão convidados a terminar a elaboração do problema. Eles terão um prazo de DOIS MESES para enviar para a comissão:
  • Um arquivo contendo a descrição detalhada do problema (incluindo uma história).
  • Uma implementação correta para o problema em C++, C ou Java.
  • [opcional] Uma implementação errada para o problema que gera Time Limit Exceeded, se for relevante.
  • Um gerador de casos de teste que cubra todos os casos de borda e detalhes descritos na etapa anterior (O template para o gerador, será fornecido pela comissão).

Resultados:
A comissão de provas se encarregará em escolher os melhores problemas submetidos nesta etapa para compor a prova da maratona mineira. Assim que os problemas forem selecionados, os autores serão convidados a concluir a elaboração do seu problema na etapa seguinte.

Incentivo:
Para incentivar a participação das instituições nesta etapa, a comissão de provas pretende criar mini-competições online no primeiro semestre de 2017 se houver volume suficiente de problemas submetidos. Essas mini-competições deverão utilizar de 9 a 11 problemas que seriam descartados para a competição final. A data da mini-competição será anunciada com um mês de antecedência. Acreditamos que essas competições online são um excelente treino para os times e ressaltamos que a sua realização só depende da participação de todos na submissão dos problemas.

Importante
  • Submissões incompletas ou que não cumpram o formato estabelecido não serão consideradas.
  • As submissões de ideias para os problemas ocorrerão pelo formulário: http://goo.gl/forms/uaYbCpGZDZ
  • Em caso de dúvida contacte comissaoproblemamineira [at]gmail.com para receber informações sobre como proceder.

Restrições
  •  o autor não pode ser competidor.
  • o autor deve ter tempo disponível, durante os meses de Fevereiro, Março e Abril para para trabalhar em seu problema (finalizar e melhorar enunciado, testes e soluções), e de preferência ter também tempo para trabalhar em problemas de outros autores.
  • o autor deve se comprometer a manter sigilo sobre o problema submetido até que o Comitê tenha terminado a seleção dos problemas, e caso o problema seja selecionado, até o final da competição.
Os problemas não selecionados podem ser utilizados pelos autores que os enviaram, em outras competições, ou para re-envio em outro ano.

Sugestões para escrever um bom problema
  • Se você nunca escreveu um problema, leia e estude ao menos uma prova inteira da regional latino-americana, sub-regional ou da maratona mineira de anos passados antes de começar a escrever. Sugere-se estudar mais de uma prova.
  • Para uma boa prova, necessita-se de problemas de todos os níveis de dificuldade. Um bom problema não é equivalente a um problema difícil.
  • Há muitos temas para problemas (grafos, programação dinâmica, geometria, aritmética, guloso, backtracking, estruturas de dados, etc.). Geralmente grafos e programação dinâmica são os mais populares, mas os problemas das provas serão selecionados tendo diversificação em mente. Nota: é muito bom quando um mesmo problema toca vários temas.
  •  Procure deixar bem claro quais são as entradas válidas, incluindo limites para todos os parâmetros.
  • Os problemas com saída única são preferíveis. Se sua ideia tem saída múltipla, há várias técnicas que podem ser usadas para facilmente transformá-la em um problema com saída única (resultados em ordem lexicográfica, solicitar apenas o mínimo e o máximo e não a descrição do conjunto completo de resultados, etc.).
  • Os problemas de decisão são os mais difíceis de testar. Procure fazer com que as possíveis saídas de seu problema tenham vários valores (um inteiro, uma cadeia, etc.).
  •  A menos que a ideia de um problema seja diretamente relacionada à entrada/saída. (por exemplo, problemas de parsing, ou de desenho na tela), tanto a entrada como a saída devem ser o mais simples possível de ler usando entrada/saída padrão (printf/scanf, cout/cin, BufferedReader/System.out).


Exemplos: