Introdução
Suponha que você e seu amigo estejam jogando um jogo. Seu amigo pensa em uma sequência específica de n
bits e sua tarefa é deduzir a sequência fazendo perguntas. No entanto, o único tipo de pergunta que você pode fazer é "Quanto tempo é a subsequência comum mais longa da sua sequência e S
", onde S
está qualquer sequência de bits. Quanto menos perguntas você precisar, melhor.
A tarefa
Sua tarefa é escrever um programa ou função que tenha como entrada um número inteiro positivo n
e uma sequência binária R
de comprimento n
. A sequência pode ser uma matriz de números inteiros, uma sequência ou outro tipo razoável de sua escolha. Seu programa deve produzir a sequência R
.
Seu programa não tem permissão para acessar a sequência R
diretamente. A única coisa que ele pode fazer R
é fornecê-lo como entrada para a função, len_lcs
juntamente com outra sequência binária S
. A função len_lcs(R, S)
retorna o comprimento da subsequência comum mais longa de R
e S
. Isso significa a sequência mais longa de bits que ocorre como uma subsequência (não necessariamente contígua) em ambos R
e S
. As entradas len_lcs
podem ter diferentes comprimentos. O programa deve chamar essa função R
e outras seqüências várias vezes e, em seguida, reconstruir a sequência com R
base nessas informações.
Exemplo
Considere as entradas n = 4
e R = "1010"
. Primeiro, podemos avaliar len_lcs(R, "110")
, o que fornece 3
, uma vez que "110"
é a subsequência comum mais longa de "1010"
e "110"
. Então sabemos que R
é obtido "110"
inserindo um bit em alguma posição. Em seguida, podemos tentar len_lcs(R, "0110")
, que retorna 3
desde que as subsequências comuns mais longas são "110"
e "010"
, portanto, "0110"
não estão corretas. Então tentamos len_lcs(R, "1010")
, que retorna 4
. Agora sabemos disso R == "1010"
, para que possamos retornar essa sequência como a saída correta. Isso exigiu 3 chamadas para len_lcs
.
Regras e pontuação
Em este repositório , você encontrará um arquivo chamado subsequence_data.txt
contendo 100 sequências binárias aleatórias de comprimentos entre 75 e 124. Eles foram gerados por tomar três carros alegóricos aleatórios entre 0 e 1, tendo sua média como a
, e em seguida, lançando uma a
moeda -biased n
vezes. Você pontua é o número médio de chamadas paralen_lcs
essas seqüências, sendo a pontuação mais baixa melhor. Sua submissão deve registrar o número de chamadas. Não há limites de tempo, exceto que você deve executar seu programa no arquivo antes de enviá-lo.
Sua submissão deve ser determinística. Os PRNGs são permitidos, mas devem usar a data de hoje 200116
(ou o equivalente mais próximo) como a semente aleatória. Você não tem permissão para otimizar seu envio em relação a esses casos de teste específicos. Se eu suspeitar que isso esteja acontecendo, gerarei um novo lote.
Como não é um código de golfe, você deve escrever um código legível. O Código Rosetta possui uma página na subsequência comum mais longa ; você pode usá-lo para implementar len_lcs
no seu idioma preferido.
lcs
vez delen_lcs
.lcs(R, "01"*2*n)
retornaR
. ;) Mas isso poderia funcionar se chamadalcs(R, S)
iria aumentar a pontuaçãolen(S)
em vez de 1, ou algo assim ...Respostas:
Java,
99.0498.4697.66 chamadas lcs ()Como funciona
Exemplo: Nossa linha que deve ser reconstruída é
00101
. Primeiro, descobrimos quantos zeros existem, comparando (aqui comparando = computando lcs com a cadeia original) por uma cadeia apenas de zeros00000
. Em seguida, passamos por cada posição, vire0
para a1
e verifique se agora temos uma substring comum mais longa. Se sim, aceite e vá para a próxima posição; se não,1
volte a corrente para a0
e vá para a próxima posição:Otimizações
Esta é apenas uma implementação "ingênua"; talvez seja possível encontrar um alogritmo mais sofisticado que verifique várias posições ao mesmo tempo. Mas não tenho certeza se realmente existe um melhor (por exemplo, com base no cálculo de bits de paridade semelhantes ao código de Hamming), pois você sempre pode avaliar o comprimento da substring comum.
Para uma determinada linha de dígitos, esse algoritmo precisa exatamente de
#ofDigitsUntilTheLastOccurenceOf1 + 1
verificações. (Subtraia um se o último dígito for um1
.)EDIT: Uma pequena otimização: se apenas verificarmos o segundo último dígito e ainda precisarmos inserir um
1
, sabemos com certeza que ele deve estar na última posição e podemos omitir a verificação correspondente.EDIT2: Acabei de notar que você pode aplicar a ideia acima às últimas
k
.Obviamente, pode ser possível obter uma pontuação um pouco menor com essa otimização, reordenando todas as linhas primeiro, porque pode ser que você obtenha mais linhas com as linhas no final, mas isso obviamente seria uma otimização para a atual casos de teste que não são mais engraçados.
Tempo de execução
O limite superior é
O(#NumberOfBits)
.Código completo
Aqui está o código completo:
fonte
1
, o que equivale a haver apenas zeros.