Problema D - Buscas no aeroporto

O Problema

Dado o tamanho dos números de série de passaportes $N$ e um dos concorrentes (o Luís ou o Vitor), adivinhar o número de série do seu passaporte em menos de 2050 tentativas.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ $N$ ≤ 1 000

Número de dígitos

Os casos de teste deste problema estão organizados em 4 grupos com restrições adicionais diferentes:

Grupo	Número de Pontos	Restrições adicionais
1	25	$N$ ≤ 10, $C$ = 'L'
2	25	$C$ = 'L'
3	25	$N$ ≤ 50, $C$ = 'V'
4	25	$C$ = 'V'

Solução Parte I

Neste problema pedem-nos algo um pouco diferente do comum: descobrir uma string binária de $N$ dígitos em menos de 2050 tentativas. Nesta primeira parte do problema quando tentamos adivinhar um número de série, é nos dito quantos dígitos errámos.

Claro que uma solução óbvia para este problema seria tentar todas as strings binárias possíveis de tamanho $N$, que são $2^N$. Uma solução deste género apenas funciona para os casos em que $N$ é pequeno (pois se $N > 10$, então $2^N > 2050$) e por isso teria apenas 25 pontos.

Mas o objetivo do problema não é tentar todas as strings possíveis mas sim usar a informação que recebemos quando tentamos adivinhar uma para ficar mais próximo de uma solução. Assim, vamos começar por adivinhar uma string aleatória qualquer, por exemplo, podemos começar com a string que só contém 0s. Depois de a adivinhar, caso não tenhamos acertado (se no processo de descobrir a string correta a descobrirmo "acidentalmente", então paramos o processo porque já temos o que queríamos), verificamos que errámos $x$ dígitos. Agora tentamos adivinhar a mesma string, mas com o primeiro dígito com o valor 1 e temos duas hipóteses: ou erramos $x + 1$ ou erramos $x - 1$, pois ao trocarmos apenas um dígito estamos ou a passar um dígito que estava certo para errado ou vice-versa. Se errámos $x + 1$, então piorámos a nossa adivinha, logo o primeiro dígito tem de ser um 0. Se errámos $x - 1$, então melhorámos a nossa adivinha, logo o primeiro dígito tem de ser um 1.

Podemos repetir este processo para cada dígito, em cada adivinha descobrimos qual o valor correto do dígito atual. Assim, conseguimos adivinhar a resposta em apenas $N + 1$ adivinhas: a inicial só com 0s mais uma por dígito. Esta solução teria exatamente 50 pontos e resolve a primeira parte do problema por completo.

Solução Parte II

Deparamo-nos agora com um problema muito parecido, mas com objetivos bastante diferentes. Como só temos informação quando a resposta é exatamente $N / 2$ temos de alguma adivinhar strings que possam ter $N / 2$ dígitos errados. Assim, dividimos a nossa solução em duas partes: primeiro queremos encontrar uma string (não interessa qual) cuja resposta da máquina seja $N / 2$; depois, partindo da string encontrada, queremos chegar à resposta. Vamos dedicar no máximo $N$ adivinhas a cada parte.

Para descobrir uma string com $N / 2$ dígitos errados, começamos da mesma forma que no problema anterior: adivinhando uma string aleatória, por exemplo, a string que apenas contém 0s. Novamente, assumimos que o número de dígitos que errámos foi $x$. Se $x$ for igual a $N / 2$ então já temos o que queríamos, caso contrário temos de pensar um pouco pois a resposta da máquina é $N$ (novamente assumimos que descobrirmos a string correta "acidentalmente", ou seja, a resposta da máquina ser 0, então paramos o processo). Ora se a string que adivinhámos tem $x$ dígitos errados, então a string reversa, ou seja, a string onde trocamos todos os 1s por 0s e 0s por 1s terá $N - x$ dígitos errados, pois os dígitos que errávamos passamos a acertar e vice-versa. Se $x$ é diferente de $N / 2$, então ou $x$ é menor que $N / 2$ e $N - x$ maior que $N / 2$ ou $x$ é maior que $N / 2$ e $N - x$ menor que $N / 2$. Isto sugere que o que podemos fazer é o seguinte: trocamos o primeiro dígito para 1 e tentamos adivinhar; caso ainda não tenhamos encontrado a string que erra $N / 2$, então trocamos o segundo dígito para 1 e tentamos adivinhar; e por ai fora. Entre cada passo, o número de dígitos que erramos muda exatamente por um: ou aumenta um, ou diminui um. Se fizermos isto $N$ vezes, chegaremos à string inversa da inicial e como temos de passar por todos os valores de dígitos errados entre $x$ e $N - x$ (pelo teorema do valor intermédio), algures no meio temos de ter passado por uma string que errava exatamente $N / 2$ dígitos. Assim, com no máximo $N$ adivinhas, descobrimos o que queríamos.

Para a última parte, não podemos fazer algo exatamente igual à solução do problema da primeira parte, mas podemos fazer algo parecido. Se trocarmos o primeiro e o segundo dígito da string encontrada na solução do parágrafo anterior, duas coisas podem acontecer: se ambos estivessem corretos ou errados, o número de dígitos errados iria diminuir ou aumentar em duas unidades, logo a resposta da máquina automática iria passar a ser $N$; se um estivesse correto e o outro errado, o número de dígitos errados manter-se-ia, logo a resposta da máquina automática manter-se-ia a $N / 2$. Assim, conseguimos saber, de acordo com a resposta da máquina automática, se os dois primeiros dígitos "concordam" ou não.

Se usarmos esta observação, podemos repetir o processo com o primeiro e terceiro dígito, primeiro e quarto e por ai fora, descobrindo assim a concordância de todos os dígitos com o primeiro. Com isto, invertemos todos os dígitos que não concordam com o primeiro e adivinhamos a string correspondente, se esta não for a resposta significa que adivinhámos a string inversa à solução e por isso basta-nos inverter todos os dígitos para termos a solução.

Nesta solução, a primeira parte precisa de no máximo $N$ adivinhas e a segunda de outras $N$, logo para qualquer $N$ dentro dos limites do problema estamos dentro do máximo de 2050 adivinhas. Assim, esta solução teria exatamente 100 pontos (se conjugada com a anterior).

Problema bónus

Uma propriedade interessante deste problema, é que podia ser resolvido probabilisticamente para um limite de adivinhas a 1550. Por probabilístico queremos dizer uma solução cuja probabilidade de funcionar é muito alta (maior que 99.999%, que, para efeitos práticos, é garantido que funciona), mas que não é certo que funcionaria. Esta solução é baseada no facto que o valor médio de dígitos errados de uma adivinha aleatória é $N / 2$ (por argumentos de simetria), mas deixamos como exercício perceberem como é que podem conjugar esta observação com as soluções apresentadas.