Optymalna strategia dla abstrakcyjnej gry

W wywiadzie otrzymałem następujący problem (którego już nie udało mi się rozwiązać, nie próbując oszukać mojej przeszłości): Gra rozpoczyna się od dodatniej liczby całkowitej . (Np. ) Liczba ta jest konwertowana na reprezentację binarną, a jest liczbą bitów ustawioną na . (Np. , )A 0 = 1234 N 1 A 0 = b 100 1101 0010 N = $A_0$$A_0 = 1234$$N$$1$$A_0 = b100\ 1101\ 0010$$N = 5.$

Gracz 1 wybiera liczbę mniejszą niż . musi mieć tylko jeden bit ustawiony na 1. (Np. ). Niech . (Np a_1 = 1234-512 = = 722 B10 1101 0010 ). Ruch jest ważny jeśli B_0 spełnia poprzednich ograniczeń, a liczba bitów ustawionych w A_1 nadal równa n .A 0 B 0 B 0 = b 10 0000 0000 = 512 A 1 = A 0 - B 0 A 1 = 1234 - 512 = 722 = b 10 1101 $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$A $B_0$$A_1$

Gracz 2 kontynuuje od $A_1$ , wybierając prawidłowy $B_1$ , następnie gracz 1 kontynuuje od $A_2$ i tak dalej. Gracz przegrywa, jeśli nie ma już żadnych ważnych ruchów.

Zakładając, że obaj gracze grają optymalnie, określ zwycięskiego gracza za pomocą dość wydajnej metody. (W mojej definicji problemu ograniczeniem było to, że program musi być w stanie dostarczyć rozwiązanie dla kilku milionów liczb wejściowych, które pasują do 32-bitowej liczby całkowitej ze znakiem). Oznacza to, że rozwiązaniem nie musi być w pełni analityczny.

Moim osobistym zainteresowaniem jest ustalenie, czy oczekiwanie ode mnie znalezienia i wdrożenia prawidłowego rozwiązania bez opinii zwrotnej na temat poprawności w ciągu 120 minut, które otrzymałem, było uzasadnione; lub jeśli było to jedno z tych pytań „zobaczmy, czy widzieli już tę zagadkę”.

Nie udało mi się, ponieważ zdecydowałem się wdrożyć coś, co wydawało się rozsądną strategią, która dała mi prawidłowe wyniki dla kilku przypadków testowych, które otrzymałem z góry, zmarnowałam zbyt dużo czasu na szybkie uruchomienie i skończyła się niepoprawnym podawaniem pełna wydajność, gdy mój czas się skończył.

Z perspektywy czasu powinienem był zastosować wyszukiwanie siłowe i zapamiętać częściowe rozwiązania dla małych liczb początkowych, ale z perspektywy czasu zawsze jest 20/20. Jestem jednak ciekawy, czy istnieje inne wspólne podejście, które wymknęło mi się z tropu.

Poświęć chwilę na uświadomienie sobie, że jeśli możemy odjąć potęgę dwóch, a liczba ludności nie może się zmienić, musimy odjąć w pozycji, w której druga liczba to . Wynikiem tego jest zawsze w tej pozycji, a liczba nie zmienia się nigdzie indziej.$01$$10$$01$

Innymi słowy, gra jest serią zamian , a gra kończy się, jeśli wszystkie są po prawej stronie. Pamiętaj, że nie można wcześnie zakończyć tej gry - nie możesz utknąć. Zawsze znajdziesz się w pozycji, w której wszystkie zera są po lewej stronie, a wszystkie z nich są po prawej stronie.$10 \rightarrow 01$

Jedynym decydującym czynnikiem w grze jest to, ile swapów potrzeba, aby dostać się do stanu, w którym wszystkie są po prawej, i nie ma strategii wygranej lub przegranej. Jedynym czynnikiem determinującym jest parzystość liczby transakcji zamiany.

Więc ile swapów to zajmuje? Zauważ, że s nie mogą się krzyżować, więc jeśli je ponumerujemy i prześledzimy poprzez swapy, pozostaną w tej samej kolejności w końcowym stanie. Każda zamiana przybliża ich do ostatecznej pozycji.$1$

Więc jeśli ta (licząc od prawej, skrajna prawa to ta ) znajduje się w pozycji z prawej, potrzebuje zamienia, aby dostać się do swojej właściwej pozycji. To daje nam algorytm do zliczania wymaganej liczby swapów:$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

Teraz możemy po prostu spojrzeć na parytet, totalaby zobaczyć, kto wygra. Złożoność czasu wynosi .$O(\log n)$

Jednym ze sposobów rozwiązania takiego problemu jest:

• Znajdź rozwiązanie dla kilku prostych wartości, korzystając z proponowanego przez ciebie „zapamiętywanego brute-force”.

• Odgadnij odpowiedź (które pozycje wygrywają, a które tracą).

• Spróbuj udowodnić swoją odpowiedź. Jeśli ci się uda, świetnie. W przeciwnym razie spróbuj znaleźć kontrprzykład i użyj go, aby odgadnąć inną odpowiedź. W tym przypadku pomocne może być rozwiązanie kilku innych przypadków.

Naprawdę trudno powiedzieć, ile czasu to zajmuje. Jednak w wywiadach niekoniecznie oczekuje się rozwiązania. Ankieterzy chcą raczej wiedzieć, jak podeszliście do rozwiązania problemu i jaki postęp udało wam się osiągnąć.

Zwróć uwagę na odpowiedź @ orlp, że chcemy parzystości sumy przesunięć z pozycji początkowej do pozycji końcowej. Dodajmy do tego adnotację:

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

Więc chcemy

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

Pierwsza część to parzystość liczby bitów w pozycjach nieparzystych. Możesz to maskować, biorąc maksymalną liczbę całkowitą bez znaku, dzieląc przez 0b11 i negując.

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

Druga część to parzystość połowy liczby bitów x.

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

bitcountmoże albo użyć popcntinstrukcji sprzętowej , albo może zostać zaimplementowany ręcznie, wykorzystując, że potrzebny jest tylko ostatni lub drugi do ostatniego bit, z takimi szybkimi redukcjami .