Układając książki, zwykle chcesz umieścić największe na dole, a najmniejsze na górze. Jednak moja ukryta OCD sprawia, że czuję się bardzo nieswojo, jeśli mam dwie książki, w których jedna jest krótsza (na wysokości), ale szersza od drugiej. Bez względu na to, w jakiej kolejności je złożę, górna książka będzie rozciągać się poza dolną książkę z jednej strony.
Na przykład powiedzmy, że jedna książka ma wymiary, (10,15)
a inna ma wymiary (11,14)
. Bez względu na to, w którą stronę je postawię, dostaję nawis. Ale jeśli mam książki o wymiarach (4,3)
i (5,6)
, mogę uniknąć przewieszania, umieszczając ten ostatni pod pierwszym.
Na potrzeby tego wyzwania rozważymy zwisy tylko w odniesieniu do książki bezpośrednio poniżej . Na przykład jeśli mam stos (5,5)
, (3,3)
, (4,4)
(nie, że każda osoba przy zdrowych zmysłach by tego nie zrobił), liczy top książkę jako zwis, choć nie wykracza poza dolną książki. Podobnie, stos (3,3)
, (3,3)
, (4,4)
posiada tylko jeden występ, mimo górnym książki wykraczającego poza dolnej jeden.
Wyzwanie
Biorąc pod uwagę listę par liczb całkowitych dla wymiarów książek, posortuj te pary / książki tak, aby liczba nawisów była minimalna. Nie wolno obracać książek - chcę, aby wszystkie kolce były skierowane w tym samym kierunku. Jeśli istnieje wiele rozwiązań z taką samą liczbą zwisów, możesz wybrać dowolną taką kolejność. Twój algorytm sortowania nie musi być stabilny. Wdrożenie może zakładać, że wymiary książki są mniejsze niż 2 16 każdy.
Złożoność czasowa: aby uczynić to nieco bardziej interesującym, asymptotyczna złożoność algorytmu najgorszego przypadku musi być wielomianowa pod względem wielkości stosu. Więc nie możesz po prostu przetestować każdej możliwej permutacji. Dołącz krótki dowód optymalności i złożoności algorytmu oraz opcjonalnie wykres pokazujący skalowanie dla dużych losowych danych wejściowych. Oczywiście nie można użyć maksymalnego rozmiaru danych wejściowych jako argumentu działania kodu w O (1).
Możesz napisać program lub funkcję, wziąć dane wejściowe za pomocą argumentu STDIN, ARGV lub funkcji w dowolnym dogodnym (nieprzetworzonym) formacie listy i wydrukować lub zwrócić wynik.
To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).
Jestem pewien, że istnieje rozwiązanie wielomianowe, ale jeśli możesz udowodnić, że się mylę, możesz przedstawić taki dowód zamiast zgłoszenia w golfa. W takim przypadku możesz założyć P ≠ NP . Przyjmę pierwszy poprawny taki dowód i przyznam mu nagrodę.
Przykłady
In: [[1, 1], [10, 10], [4, 5], [7, 5], [7, 7], [10, 10], [9, 8], [7, 5], [7, 5], [3, 1]]
Out: [[10, 10], [10, 10], [9, 8], [7, 7], [7, 5], [7, 5], [7, 5], [4, 5], [3, 1], [1, 1]]
In: [[4, 5], [5, 4], [5, 4], [5, 4], [5, 4], [4, 5], [4, 5], [4, 5], [5, 4], [4, 5]]
Out: [[4, 5], [4, 5], [4, 5], [4, 5], [4, 5], [5, 4], [5, 4], [5, 4], [5, 4], [5, 4]]
or [[5, 4], [5, 4], [5, 4], [5, 4], [5, 4], [4, 5], [4, 5], [4, 5], [4, 5], [4, 5]]
In: [[2, 3], [1, 1], [5, 5], [7, 1]]
Out: [[5, 5], [2, 3], [7, 1], [1, 1]]
or [[5, 5], [2, 3], [1, 1], [7, 1]]
or [[7, 1], [5, 5], [2, 3], [1, 1]]
or [[7, 1], [1, 1], [5, 5], [2, 3]]
Stworzyłem je ręcznie, więc daj mi znać, jeśli zauważysz jakieś błędy.
źródło
Odpowiedzi:
Pyth , 30
Jest to bezpośredni golf wspaniałego algorytmu grc. Oto dokładny odpowiednik powyższego programu pyth w jego skompilowanym kodzie python.
W tym kontekście
Psum(Y)
funkcja jest równoważna pythonowisum(Y,[])
.Rzeczywisty skompilowany i uruchom kod (z
pyth -d
):źródło
sum(Y,[])
. To wszystko powinno działać w Pyth, tylko tłumaczenie nie obejmuje go automatycznie.Pprint("\n",Psum(Y))
. Myślę, że mógł go uprościć dla wygody, wraz ze wszystkimi innymi-1
itd., TakPsum
naprawdę działałby bardziejreduce(lambda x,y:x+y, Y[1:], Y[0])
.Python, 113
Po posortowaniu listy książek w kolejności malejącej (najpierw według szerokości, a następnie wysokości) dzieli książki na stosy bez nakładania się. Aby ustalić, gdzie umieścić każdą książkę, jej wysokość jest porównywana z wysokością górnej książki w każdym stosie. Jest on umieszczany na pierwszym możliwym stosie, w przeciwnym razie tworzony jest nowy stos.
Nie jestem zbyt dobry w złożoności czasowej, ale uważam, że miałby to najgorszy przypadek O ( N 2 ). Istnieją dwie pętle, każda z co najwyżej N iteracjami. Używam również wbudowanego sortowania Pythona, którym jest O ( n log n ).
Mój pierwszy dowód, że ten algorytm zapewnia optymalne rozwiązania, okazał się niepoprawny. Ogromne podziękowania należą się @xnor i @ Sp3000 za świetną dyskusję na czacie o udowodnieniu tego (którą możesz przeczytać, zaczynając tutaj ). Po opracowaniu prawidłowego dowodu @xnor stwierdził, że część tego już została wykonana ( twierdzenie Dilwortha ).
Oto przegląd dowodu i tak (podziękowania dla @xnor i @ Sp3000).
Najpierw zdefiniujemy pojęcie antypala lub antychaina ( cytowane z @xnor ):
Następnie sortujemy książki w kolejności malejącej według ich szerokości (pierwsza) i wysokości (druga) *.
Dla każdej książki B wykonujemy następujące czynności:
Teraz stworzyliśmy łącze z każdej książki (z wyjątkiem tych w pierwszym stosie), do książki w poprzednim stosie, która ma większą szerokość i mniejszą wysokość.
Doskonały schemat @ Sp3000 dobrze to ilustruje:
Podążając dowolną ścieżką od ostatniego stosu (po prawej) do pierwszego stosu (po lewej), otrzymujemy antypile. Co ważne, długość tego antypala jest równa liczbie stosów. Dlatego liczba stosów jest minimalna.
Wreszcie, ponieważ zorganizowaliśmy książki w minimalną liczbę stosów bez nakładania się, możemy ułożyć je jeden na drugim, aby uzyskać jeden stos z minimalną liczbą nakładek.
* ten pomocny komentarz wyjaśnia kilka rzeczy
źródło