Wprowadzenie
Załóżmy, że ty i twój przyjaciel gracie w grę. Twój przyjaciel myśli o określonej sekwencji n
bitów, a Twoim zadaniem jest wydedukować sekwencję, zadając im pytania. Jednak jedynym rodzajem pytania, które możesz zadać, jest: „Jaka jest najdłuższa wspólna podsekwencja twojej sekwencji i S
”, gdzie S
jest dowolna sekwencja bitów. Im mniej pytań potrzebujesz, tym lepiej.
Zadanie
Twoim zadaniem jest napisanie programu lub funkcji, która przyjmuje jako dane wejściowe dodatnią liczbę całkowitą n
i binarną sekwencję R
długości n
. Sekwencją może być tablica liczb całkowitych, ciąg znaków lub inny rozsądny typ twojego wyboru. Twój program wyświetli sekwencję R
.
Twój program nie ma R
bezpośredniego dostępu do sekwencji . Tylko rzecz to wolno zrobić, aby R
to dać to jako wejście do funkcji len_lcs
wraz z innej sekwencji binarnej S
. Funkcja len_lcs(R, S)
zwraca długość najdłuższego wspólnego podsekwencji R
i S
. Oznacza to najdłuższą sekwencję bitów, która występuje jako (niekoniecznie ciągła) podsekwencja zarówno w, jak R
i S
. Dane wejściowe len_lcs
mogą mieć różne długości. Program powinien wywołać tę funkcję R
i inne sekwencje kilka razy, a następnie zrekonstruować sekwencję R
na podstawie tej informacji.
Przykład
Rozważ dane wejściowe n = 4
i R = "1010"
. Po pierwsze, możemy ocenić len_lcs(R, "110")
, co daje 3
, ponieważ "110"
jest to najdłuższa wspólna podsekwencja "1010"
i "110"
. Wtedy wiemy, że R
uzyskuje się to "110"
poprzez wstawienie jednego bitu w pewnej pozycji. Następnie możemy spróbować len_lcs(R, "0110")
, który powraca 3
od najdłuższych wspólnych podciągów to "110"
i "010"
tak "0110"
nie jest poprawna. Następnie próbujemy len_lcs(R, "1010")
, co powraca 4
. Teraz wiemy o tym R == "1010"
, abyśmy mogli zwrócić tę sekwencję jako poprawne wyjście. Wymagało to 3 połączeń z len_lcs
.
Zasady i punktacja
W tym repozytorium znajdziesz plik o nazwie subsequence_data.txt
zawierający 100 losowych sekwencji binarnych o długości od 75 do 124. Zostały one wygenerowane poprzez pobranie trzech losowych liczb zmiennoprzecinkowych od 0 do 1, przyjęcie ich średniej jako a
, a następnie przerzucenie a
bezstronnych n
czasów monet . Twój wynik to średnia liczba wywołańlen_lcs
w tych sekwencjach, przy czym niższy wynik jest lepszy. Twoje zgłoszenie powinno rejestrować liczbę połączeń. Nie ma ograniczeń czasowych, z wyjątkiem tego, że powinieneś uruchomić program na pliku przed jego przesłaniem.
Twoje zgłoszenie będzie deterministyczne. PRNG są dozwolone, ale muszą używać dzisiejszej daty 200116
(lub najbliższego odpowiednika) jako losowego materiału siewnego. Niedozwolone jest optymalizowanie procesu przesyłania w odniesieniu do tych konkretnych przypadków testowych. Jeśli podejrzewam, że tak się dzieje, wygeneruję nową partię.
To nie jest kod golfowy, więc zachęcamy do napisania czytelnego kodu. Kod Rosetta ma stronę o najdłuższym wspólnym podsekwencji ; możesz użyć tego do wdrożenia len_lcs
w swoim wybranym języku.
lcs
zamiast tego można uzyskać dostęplen_lcs
.lcs(R, "01"*2*n)
powracaR
. ;) Ale to może zadziałać, jeśli dzwonienielcs(R, S)
zwiększy wyniklen(S)
o 1, lub coś w tym stylu ...Odpowiedzi:
Java,
99,0498,4697,66 lcs ()Jak to działa
Przykład: nasza linia, która ma zostać zrekonstruowana, to
00101
. Najpierw dowiadujemy się, ile jest zer, porównując (tutaj porównując = obliczanie lcs z oryginalnym ciągiem) przez ciąg tylko zer00000
. Następnie przeglądamy każdą pozycję, przełączamy na0
a1
i sprawdzamy, czy mamy już dłuższy wspólny podłańcuch. Jeśli tak, zaakceptuj i przejdź do następnej pozycji, jeśli nie, odwróć bieżącą pozycję z1
powrotem do pozycji0
i przejdź do następnej pozycji:Optymalizacje
Jest to po prostu „naiwna” implementacja, być może byłoby możliwe znalezienie bardziej wyrafinowanego algorytmu sprawdzającego wiele pozycji jednocześnie. Ale nie jestem pewien, czy naprawdę jest lepszy (np. Na podstawie obliczenia bitów parzystości podobnych do kodu Hamminga), ponieważ zawsze można po prostu ocenić długość wspólnego podłańcucha.
Dla jednej linii cyfr ten algorytm wymaga dokładnie
#ofDigitsUntilTheLastOccurenceOf1 + 1
sprawdzenia. (Odejmij jeden, jeśli ostatnie cyfry to1
.)EDYCJA: Jedna mała optymalizacja: Jeśli właśnie sprawdziliśmy drugą ostatnią cyfrę i nadal musimy wstawić a
1
, wiemy na pewno, że musi ona znajdować się na ostatniej pozycji i możemy pominąć odpowiednie sprawdzenie.EDYCJA 2: Właśnie zauważyłem, że możesz zastosować powyższy pomysł do ostatnich
k
.Dzięki tej optymalizacji można oczywiście uzyskać nieco niższy wynik, zmieniając najpierw wszystkie linie, ponieważ może się zdarzyć, że na końcu pojawi się więcej linii, ale to oczywiście będzie optymalizacja dla bieżącego przypadki testowe, które nie są już śmieszne.
Środowisko wykonawcze
Górny limit to
O(#NumberOfBits)
.Pełny kod
Oto pełny kod:
źródło
1
, co jest równoważne z pozostawieniem samych zer.