Оптимальная стратегия для абстрактной игры

Мне дали следующую проблему в интервью (которую я уже не смог решить, не пытаясь обмануть мой путь мимо): Игра начинается с положительного целого числа . (Например , 0 = 1234 ) . Это число преобразуется в двоичное представление, и N представляет собой количество битов в 1 . (Например, A 0 = b 100 1101 0010 , N = 5. )$A_0$$A_0 = 1234$$N$$1$$A_0 = b100\ 1101\ 0010$$N = 5.$

Игрок 1 выбирает число меньше, чем A 0 . B 0 должен иметь только один бит, установленный в 1. (Например, B 0 = b 10 0000 0000 = 512. ) Пусть A 1 = A 0 - B 0 . (Например, A 1 = 1234 - 512 = 722 = b 10 1101 0010. ) Ход действителен, если 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$удовлетворяет предыдущие ограничения, и если количество битов в по - прежнему равна N .$A_1$

Игрок 2 продолжает с , выбирая действительный B 1 , затем игрок 1 продолжает с A 2 и так далее. Игрок проигрывает, если у него не осталось действительных ходов.$A_1$$B_1$$A_2$

Предполагая, что оба игрока играют оптимально, определите победителя, используя достаточно эффективный метод. (В моем определении проблемы, ограничения на это заключались в том, что программа должна быть в состоянии предоставить решение для нескольких миллионов входных чисел, которые вписываются в 32-разрядное целое число со знаком.) То есть решение не должно быть полностью аналитический.

Мой личный интерес здесь состоит в том, чтобы выяснить, было ли разумным ожидание от меня того, что я найду и осуществлю правильное решение без обратной связи о правильности в течение 120 минут, которые мне дали или если это был один из тех вопросов «давайте посмотрим, видели ли они эту загадку раньше».

Я потерпел неудачу, потому что я решил реализовать то, что казалось разумной стратегией, которая дала мне правильные результаты для нескольких тестовых случаев, которые мне дали заранее, потратила слишком много времени на быстрый запуск этого теста и в итоге дала неверные результаты. полный выход, так как мое время истекло.

Оглядываясь назад, я должен был осуществить поиск методом грубой силы и запоминать частичные решения для небольших начальных чисел, но задним числом всегда 20/20. Мне любопытно, однако, есть ли другой общий подход, который ускользнул от меня как лакея.

$01$$10$$01$

$10 \rightarrow 01$

Таким образом, единственным определяющим фактором в игре является то, сколько свопов требуется, чтобы попасть в состояние, в котором все находятся справа, и нет стратегии выигрыша или проигрыша. Соотношение количества свопов, которое требуется, является единственным определяющим фактором.

$1$

$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)$

Один из способов решения такой проблемы заключается в следующем:

• Найдите решение для нескольких простых значений, используя предложенный вами подход «запоминания грубой силы».

• Угадай ответ (какие позиции выигрывают, а какие проигрывают).

• Попробуйте доказать свой ответ. Если вам это удастся, отлично. В противном случае попытайтесь найти контрпример и используйте его, чтобы угадать другой ответ. Здесь может быть полезно решить еще несколько случаев.

Трудно сказать, сколько времени это займет. Тем не менее, в интервью вы не обязательно должны найти решение. Скорее интервьюеры хотят знать, как вы подошли к решению проблемы, и какой прогресс вам удалось сделать.

Обратите внимание на ответ @ orlp, что мы хотим получить паритет суммы смещений от начальной позиции к конечной позиции. Давайте аннотируем это:

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

Итак, мы хотим

  ((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

Первая часть - это просто четность количества бит в нечетных позициях. Вы можете замаскировать это, взяв максимальное целое число без знака, разделив на 0b11 и отрицая.

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

Вторая часть - это четность половины количества бит в x.

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

bitcountможет либо использовать аппаратную popcntинструкцию, либо может быть реализован вручную с использованием только одного последнего или второго до последнего бита с такими быстрыми сокращениями .