Estratégia ideal para um jogo abstrato

Eu recebi o seguinte problema em uma entrevista (que eu já não consegui resolver, sem tentar me enganar): O jogo começa com um número inteiro positivo . (Por exemplo, A 0 = 1234. ) Esse número é convertido em representação binária e N é o número de bits definido como 1 . (Por exemplo, A 0 = b 100 1101 0010 , N = 5. )$A_0$$A_0 = 1234$$N$$1$$A_0 = b100\ 1101\ 0010$$N = 5.$

O jogador 1 escolhe um número menor que A 0 . B 0 deve ter apenas um bit definido como 1. (Por exemplo, B 0 = b 10 0000 0000 = 512. ) Seja A 1 = A 0 - B 0 . (Por exemplo, A 1 = 1234 - 512 = 722 = b 10 1101 0010. ) Um movimento é válido se B $B_0$$A_0$$B_0$$B_0 = b10\ 0000\ 0000 = 512$$A_1 = A_0 - B_0$$A_1 = 1234-512 = 722 = b10 1101 0010$$B_0$satisfaz as restrições anteriores e se o número de bits definido em $A_1$ é ainda igual a N .

O jogador 2 continua de escolhendo um B 1 válido e o jogador 1 continua de A $A_1$$B_1$$A_2$ , e assim por diante. Um jogador perde se não tiver mais movimentos válidos.

Supondo que os dois jogadores joguem da melhor maneira, determine o jogador vencedor usando um método razoavelmente eficiente. (Na minha definição de problema, as restrições eram que o programa precisava fornecer uma solução para alguns milhões de números de entrada que se encaixam em um número inteiro de 32 bits assinado.) Ou seja, a solução não precisa ser totalmente analítico.

Meu interesse pessoal aqui é descobrir se a expectativa de mim de ter encontrado e implementado a solução correta sem nenhum retorno sobre a correção nos 120 minutos que me foram dados era razoável; ou se essa foi uma das perguntas "vamos ver se eles já viram esse quebra-cabeça antes".

Eu falhei porque escolhi implementar o que parecia ser uma estratégia razoável, que me deu resultados corretos para os poucos casos de teste que recebi de frente, perdi muito tempo agilizando a execução e acabei entregando incorretamente saída total como o meu tempo acabou.

Em retrospecto, eu deveria ter implementado uma busca por força bruta e memorizado soluções parciais para pequenos números iniciais, mas a retrospectiva é sempre 20/20. No entanto, estou curioso para saber se existe uma abordagem comum diferente que me iludiu como desonesta.

$01$$10$$01$

$10 \rightarrow 01$

Portanto, o único fator determinante em um jogo é quantos swaps são necessários para chegar ao estado em que todos estão à direita e não há estratégia de ganhar ou perder. A paridade do número de swaps necessários é o único fator determinante.

$1$ s não pode atravessar um ao outro, por isso, se nós numerados los e monitorados-los através de swaps que eles permanecem na mesma ordem no estado final. Cada troca os aproxima um da sua posição final.

$i$$1$$1$$0$$1$$k$$k - i$

i = 0
k = 0
total = 0
while n > 0:
    if n & 1:
       total += k - i
       i += 1
    n >>= 1
    k += 1

total$O(\log n)$

Uma maneira de resolver esse problema é a seguinte:

• Encontre a solução para alguns valores simples usando a abordagem "força bruta memorizada" que você está sugerindo.

• Adivinhe a resposta (quais posições estão ganhando e quais estão perdendo).

• Tente provar sua resposta. Se você conseguir, ótimo. Caso contrário, tente encontrar um contra-exemplo e use-o para adivinhar outra resposta. Aqui, pode ser útil resolver mais alguns casos.

É realmente difícil dizer quanto tempo leva. No entanto, em entrevistas, não se espera necessariamente que você encontre a solução. Em vez disso, os entrevistadores querem saber como você abordou a solução do problema e que progresso você conseguiu fazer.

Observe na resposta do @ orlp que queremos a paridade da soma dos deslocamentos da posição inicial para a posição final. Vamos anotar isso:

       9876543210
       9 76 4  1    (positions at start)
start: 1011010010
end:   0000011111
            43210   (positions at end)

Então nós queremos

  ((1 - 0) + (4 - 1) + (6 - 2) + (7 - 3) + (9 - 4)) & 1
= ((1 + 4 + 6 + 7 + 9) - (0 + 1 + 2 + 3 + 4)) & 1
= ((1 + 0 + 0 + 1 + 1) - (0 + 1 + 0 + 1 + 0)) & 1

A primeira parte é apenas a paridade do número de bits nas posições ímpares. Você pode mascarar isso usando o número máximo não assinado máximo, dividindo por 0b11 e negando.

= (bitcount(x & ~(UINT_MAX / 0b11)) ^ (0 + 1 + 0 + 1 + 0)) & 1

A segunda parte é a paridade de metade do número de bits x.

= (bitcount(x & ~(UINT_MAX / 0b11)) ^ (bitcount(x) >> 1)) & 1

bitcountpode usar a popcntinstrução de hardware ou pode ser implementado manualmente, utilizando apenas o último ou o penúltimo bit, com reduções rápidas como essa .