Streszczenie wykonawcze
Biorąc pod uwagę wejście k
znajdziesz partycję liczb całkowitych 1
, aby n
do k
SUM-wolny podzbiorów dla największych n
można w ciągu 10 minut.
Tło: liczby Schur
Zestaw A
jest sum, jeśli jego suma A + A = { x + y | x, y in A}
nie ma z nim żadnych wspólnych elementów.
Dla każdej dodatniej liczby całkowitej k
istnieje największa liczba całkowita, S(k)
dzięki czemu zestaw {1, 2, ..., S(k)}
można podzielić na k
podzbiory bez sum. Ten numer nazywa się k- tym numerem Schura (OEIS A045652 ).
Na przykład S(2) = 4
. Możemy podzielić {1, 2, 3, 4}
jako{1, 4}, {2, 3}
, i jest to unikalny podział na dwa podzbiory bez sumy, ale nie możemy teraz dodać żadnego 5
z nich.
Wyzwanie
Napisz program deterministyczny, który wykonuje następujące czynności:
- Weź dodatnia
k
jako wejście - Zapisz aktualny znacznik czasu Unix na standardowe wyjście
- Wysyła sekwencję partycji
1
don
wk
podzestawy bez sumy w celu zwiększenian
, po każdej sekwencji z bieżącym znacznikiem czasu Unix.
Zwycięzcą zostanie program, który wydrukuje partycję największej n
w ciągu 10 minut na moim komputerze po otrzymaniu danych wejściowych 5
. Więzy zostaną zerwane przez najszybszy czas na znalezienie partycji dla największej n
, uśrednionej dla trzech przebiegów: dlatego dane wyjściowe powinny zawierać znaczniki czasu.
Ważne szczegóły:
- Mam Ubuntu Precise, więc jeśli twój język nie jest obsługiwany, nie będę mógł go ocenić.
- Mam czterordzeniowy procesor Intel Core2, więc jeśli chcesz korzystać z wielowątkowości, nie ma sensu używać więcej niż 4 wątków.
- Jeśli chcesz, żebym użył konkretnych flag kompilatora lub implementacji, udokumentuj to wyraźnie w swojej odpowiedzi.
- Nie będziesz specjalnie kodować swojego kodu do obsługi danych wejściowych
5
. - Nie musisz przedstawiać każdej znalezionej poprawy. Np. Dla danych wejściowych
2
można wyprowadzić tylko partycjęn = 4
. Jeśli jednak nie wyprowadzisz niczego w ciągu pierwszych 10 minut, zdobędę to jakon = 0
.
źródło
n=59
i sortowanie według największej liczby dozwolonych liczb mniejszej niżnextN
dajen=64
. Sortowanie według długości niedozwolonej listy numerów (która może zawierać powtórzenia) prowadzi bardzo szybko do eleganckiegon=30
wzoru.Tue Nov 10 00:44:25 2015
), ale zobaczyłemn=92
w mniej niż 2 sekundy.ctime
siętime
, ponieważ produkcja była ładniejsza, kiedytime
było dokładnie to, co powinien wybrałem.n=121
. oOPython 3, 121, <0,001s
Ulepszona heurystyka dzięki Martinowi Buttnerowi oznacza, że nie potrzebujemy nawet przypadkowości.
Wynik:
Kod:
Python 3, 112
Sortuj według sumy pierwszych 2 elementów + pochylenia
Skopiowałem strukturę danych El'endii Starman, która składa się z listy par, gdzie pierwszy element pary to elementy w tym segmencie, a drugi to sumy tego segmentu.
Zaczynam od tego samego podejścia „śledź, jakie kwoty są dostępne”. Moja heurystyka sortowania jest po prostu sumą dwóch najmniejszych elementów na danej liście. Dodam również małe, losowe pochylenie, aby wypróbować różne możliwości.
Każda iteracja po prostu umieszcza każdy nowy numer w pierwszym dostępnym pojemniku, podobnie jak losowy chciwy. Gdy to się nie powiedzie, po prostu uruchamia się ponownie.
źródło
Java 8, n =
142144Ostatnie wyjście:
Przeprowadza rozsiane losowe wyszukiwanie rozłożone na 4 wątki. Gdy nie może znaleźć odpowiedniej partycji
n
, próbuje zwolnić miejsce nan
jednej partycji naraz, zrzucając jak najwięcej z innej partycji.edycja: poprawiono algorytm zwalniania miejsca dla
n
, dodano także możliwość powrotu do poprzedniego wyboru i ponownego wyboru.Uwaga: wynik nie jest ściśle deterministyczny, ponieważ w grę wchodzi wiele wątków i mogą one ostatecznie zaktualizować najlepsze
n
znalezione do tej pory w pomieszanym porządku; ostateczny wynik 144 jest jednak deterministyczny i osiągany jest dość szybko: 30 sekund na moim komputerze.Kod to:
źródło
C, Random Greedy, n = 91
Aby zapewnić podstawowe rozwiązanie, iteruje się
n
, śledząc pojemniki oraz ich sumy i sumyn
do losowego pojemnika, w którym nie pojawia się jeszcze jako suma. Kończy się razn
pojawia się we wszystkichk
sumach, a jeśli wynikn
był lepszy niż jakakolwiek poprzednia próba, drukuje go do STDOUT.Dane wejściowe
k
są dostarczane za pomocą argumentu wiersza polecenia. Maksymalne możliwek
jest obecnie zakodowane na 10, ponieważ byłem zbyt leniwy, aby dodać dynamiczny przydział pamięci, ale można to łatwo naprawić.Chyba mógłbym teraz polować na lepsze ziarno, ale ta odpowiedź i tak prawdopodobnie nie jest szczególnie konkurencyjna, więc meh.
Oto partycja dla
n = 91
:I na koniec, oto kod:
źródło
n=91
, znaleziony w 138 sekund. Jeśli to konieczne do zerwania remisu, zrestartuję, aby uniknąć dużych błędów z powodu różnych obciążeń procesora.C ++, 135
Dołącza następny n do losowo wybranego podzbioru. Jeśli nie jest to możliwe, usuwa losowe liczby z podzbiorów i dołącza je do innych w nadziei, że pozwoli to gdzieś dołączyć n.
Prototypowałem to w awk, a ponieważ wyglądało to obiecująco, przetłumaczyłem to na C ++, aby przyspieszyć. Używać
std::set
powinno nawet przyspieszyć.Wyjście dla n = 135 (po około 230 sekundach na mojej [starej] maszynie)
Nie sprawdziłem ponownie ważności, ale powinno być w porządku.
źródło
Python 3, losowy chciwy, n = 61
Ostatnie wyjście:
Wykorzystuje to skutecznie ten sam algorytm, co Martin Büttner , ale opracowałem go niezależnie.
Istnieją
k
pojemniki, które zawierają zarówno liczby, jak i liczby, które nie mogą już w nim wchodzić. Na każdej głębokości w iteracji (jest to w zasadzie wyszukiwanie od pierwszej głębokości) kolejność bin jest tasowana, a następna liczba (nextN
) jest (sekwencyjnie) umieszczana w pojemnikach, które mogą ją wziąć, a następnie idzie o krok głębiej. Jeśli nie ma żadnych, wraca, tworząc kopię zapasową o jeden krok.źródło
Python, n = 31
Ok, więc oczywiście nie jest to zwycięzca, ale czułem, że i tak tu należy. Pozwoliłem sobie nie uwzględniać znaczników czasu, ponieważ wygasają one natychmiast, a ponieważ nie jest to prawdziwy konkurent.
Najpierw zauważ, że suma dwóch dowolnych liczb nieparzystych jest parzysta, więc możemy zrzucić wszystkie nieparzyste liczby w pierwszym bloku. Następnie, ponieważ wszystkie pozostałe liczby są parzyste, możemy je podzielić przez 2. Ponownie możemy rzucić wszystkie uzyskane liczby nieparzyste w drugim bloku (po ponownym pomnożeniu ich przez 2), podzielić pozostałe liczby przez 2 (tj. , o 4 razem), rzuć nieparzyste w trzecim bloku (po ponownym pomnożeniu ich przez 4) i tak dalej ... Lub, mówiąc słowami, rozumiecie, umieszczamy wszystkie liczby, których najmniej znaczący zbiór bit to pierwszy bit w pierwszym bloku, wszystkie liczby, których najmniej znaczący ustawiony bit to drugi bit w drugim bloku i tak dalej ...
W przypadku k bloków wpadamy w kłopoty, gdy osiągniemy n = 2 k , ponieważ najmniej znaczący ustawiony bit n to
( k + 1) -ty bit, który nie odpowiada żadnemu blokowi. Innymi słowy, ten schemat działa
do n = 2 k - 1. Tak więc, podczas gdy dla k = 5 otrzymujemy tylko skromne n = 31 , liczba ta rośnie wykładniczo z k . Ustalono również, że S ( k ) ≥ 2 k - 1 (ale tak naprawdę możemy łatwo znaleźć niższy limit niż ten.)
Dla porównania, oto wynik dla k = 5:
źródło
[1], [2,3], [4,5,6,7], ...
, które prawdopodobnie jest prostsze, z odwrotną kolejnością bitów i bloków. Łatwo jest zobaczyć, jak można go rozszerzyć.