Existe um suporte bastante forte na meta para que perguntas de redação de desafios sejam abordadas no tópico principal, desde que sejam específicas e respondíveis. No entanto, ainda não temos essas perguntas, então pensei em testar as águas. Essa pergunta provavelmente está entrando em um bom território subjetivo, ruim, subjetivo , mas acho que é provável que perguntas de redação de desafios tenham que ser. Para garantir que eles ainda gerem conteúdo de alta qualidade, não basta postar idéias especulativas selvagens nas respostas. Explique por que eles evitam os problemas mencionados abaixo ou, idealmente, apontam para os desafios existentes que usaram com sucesso a técnica sugerida no passado.

Para certos desafios de otimização, um parâmetro livre na configuração do desafio é o tamanho do problema a ser otimizado. Por "desafio de otimização", não quero dizer coisas como nosso gênero de código mais rápido , em que as respostas geralmente são necessárias para serem exatas / ideais, e o desafio é pontuado em um tamanho de problema fixo ou no maior tamanho de problema que pode ser tratado em um período fixo de tempo. Quero dizer, especificamente, desafios em que soluções abaixo do ideal para o problema subjacente são permitidas e até prováveis, e o objetivo é fazer o melhor possível.

Por uma questão de definição, considere os desafios ocupados dos castores , embora, em princípio, isso se aplique a outros tipos de desafios sem soluções ótimas conhecidas (estou apenas usando castores ocupados aqui porque exacerbam os problemas mencionados abaixo). Digamos, eu queria desafiar a encontrar o castor mais movimentado de Brainfuck. O parâmetro livre em problemas de castores ocupados é o tamanho do código. Não posso definir o desafio sem fazer referência ao tamanho do código de alguma forma. De certa forma, cada valor do parâmetro de tamanho do problema Noferece um desafio separado (cada vez mais difícil). Minha principal pergunta é como posso fazer esse desafio funcionar sem ter problemas de balanceamento.

A solução óbvia é corrigir N: "Encontre um programa Brainfuck finalizado com Nbytes de código-fonte que imprima o máximo de caracteres possível / execute o maior número possível de ticks". Isso tem enormes problemas de balanceamento: se eu escolher o tamanho muito pequeno, alguém poderá encontrar rapidamente ocastor mais movimentado e o desafio acabou. Se eu escolher um tamanho muito grande, a solução ideal imprimirá uma quantidade astronômica de caracteres antes de terminar, o que significa que provavelmente será trivial encontrar esses programas e o desafio se tornará uma tarefa / exercício de paciência - isso também deixa o território onde castores ocupados podem ser encontrados programaticamente e, em vez disso, as pessoas precisariam começar a provar seus resultados formalmente, que muitas pessoas podem não considerar muito divertidas. Obviamente, esse problema é mais pronunciado em desafios de castores ocupados do que outros tipos, devido ao crescimento das soluções ideais, mas se aplica a outros desafios.

A próxima opção seria deixar Nsem restrições e fazer parte da pontuação através de alguma função. Mesmo para desafios "normais", acertar o equilíbrio entre as pontuações combinadas é incrivelmente difícil, mas no caso de castores ocupados é realmente fundamentalmente impossível, devido ao fato de que as soluções ideais crescem mais rapidamente do Nque qualquer função computável. Isso significa que sempre posso vencer a melhor resposta existente, indo para uma área suficientemente grande, Nonde encontro facilmente um programa que dura tanto tempo que posso obter uma pontuação melhor sem muito esforço.

Também considerei estabelecer um plano fixo Ne permitir que as pessoas enviassem castores maiores, Nque serão usados ​​como desempate sucessivos. Isso tem um problema semelhante, pois alguém pode "encontrar um castor igualmente bom" para um N, criando assim um empate e enviando praticamente qualquer coisa para o próximo, Nonde encontrar uma pontuação maior é mais fácil (mesmo se encontrar o pontuação ótima fica mais difícil). Nesses casos, como você lida com várias pessoas usando a mesma solução? Proibir também seria estranho caso seja ideal.

Talvez alguém possa atingir um meio termo, fazendo um palpite razoável Ne depois pedindo castores ocupados para todos os tamanhos dentro de (digamos) 5 bytes de N, para que haja alguma margem de manobra nas duas direções (e então você combine as ~ 10 pontuações em um único por uma técnica ou outra). Isso também não parece satisfatório porque meu palpite inicial Nainda pode estar muito fora do alcance que gera desafios interessantes.

TL; DR: nos casos em que o desafio é (resolver e otimizar subótimamente) um problema cujo tamanho é variável, como incorporar o tamanho ao desafio? Idealmente, eu gostaria que as pessoas pudessem trabalhar com um valor Npróximo do limite superior da variedade de tamanhos tratáveis. Mas, no caso de soluções ideais serem possíveis N, seria ótimo se as soluções um pouco maiores Ncomeçassem a pesar, de modo que o desafio pudesse continuar com um tamanho de problema mais interessante.

Encontre o próximo N

O desafio indicaria Nque os envios devem começar às.

Então, as pessoas enviavam respostas no momento N. Se um determinado envio é o ideal, Né aumentado em 1 e o processo se repete.

Existem várias maneiras de pontuar isso:

1. Marque a melhor finalização no momento N
2. Dê um ponto para a melhor submissão no momento N, mais um ponto para cada solução ideal
3. O mesmo que o nº 2, mas também indica a pessoa que provou que uma determinada submissão era ótima.

Dê pontos para soluções dentro de um N limitado

Permita Nestar dentro de limites fixos. O limite inferior deve excluir respostas obviamente triviais e o limite superior não deve estar muito longe do limite inferior.

Em seguida, dê 1 ponto para cada pessoa que tiver a melhor solução para cada um Ndentro dos limites. Se mais alto Nsignifica que a solução é mais difícil, dê N pontos a eles. (ou alguma fórmula baseada em N).

Este método é semelhante a como AZsPCs faz isso, mas pontos parciais não são fornecidos.