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 ¹⁶ 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.

Pyth , 30

FN_SQFbYIgeeYeb~b]NB)E~Y]]N;sY

Jest to bezpośredni golf wspaniałego algorytmu grc. Oto dokładny odpowiednik powyższego programu pyth w jego skompilowanym kodzie python.

Q = eval(input())
Y = []
for N in sorted(Q)[::-1]:
     for b in Y:
         if Y[-1][-1] >= b[-1]:
             b += [N]
             break
     else:
         Y += [[N]]
print(Psum(Y))

W tym kontekście Psum(Y)funkcja jest równoważna pythonowi sum(Y,[]).

Rzeczywisty skompilowany i uruchom kod (z pyth -d):

Y=[]
Q=copy(eval(input()))
for N in neg(Psorted(Q)):
 for b in Y:
  if gte(end(end(Y)),end(b)):
   b+=[N]
   break
 else:
  Y+=[[N]]
Pprint("\n",Psum(Y))

Python, 113

P=[]
for n in sorted(input())[::-1]:
 for p in P:
  if p[-1][1]>=n[1]:p+=[n];break
 else:P+=[[n]]
print sum(P,[])

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 ² ). 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 ):

Antypile jest sekwencją książek o malejącej wysokości, ale rosnącej szerokości
Tak więc każda kolejna książka jest ściśle wyższa, ale o mniejszej szerokości
Zauważ, że każda książka w antypile wystaje nad każdą inną książkę w antypile
Tak więc nie ma dwóch książek w antypile być na tym samym stosie
W konsekwencji, jeśli możesz znaleźć antypile x książek, to te książki muszą znajdować się w różnych stosach,
więc wielkość największej antypile jest dolną granicą liczby stosów

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:

1. Jeśli B zmieści się na pierwszym stosie, umieszczamy go tam i idziemy dalej.
2. W przeciwnym razie znajdziemy najwcześniejszy * stos x, na którym B można umieścić na wierzchu. W razie potrzeby może to być nowy stos.
3. Następnie łączymy B z P , gdzie P jest najwyższą książką na poprzednim stosie x - 1 .
4. Teraz wiemy, że:
   • B ma ściśle * mniejszą szerokość niż P , ponieważ książki są sortowane w kolejności malejącej według szerokości
   • B ma ściśle większą wysokość niż P , inaczej umieścilibyśmy B na P

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}