Zadanie składało się z dwóch części, punktowanych niezależnie po 3pkt: należało udowodnić, że potrzeba 5 porównań (nie da się czteroma) i że 5 porównań wystarcza (istnieje algorytm scalający ciągi, który pesymistycznie używa tylko 5 porównań).
W USOSie wpisałem bardzo skrótowe notatki co do oceny. Zadania można oglądać na konsultacjach (piątki 10:15-11:45, 5790) jak już będą publicznie dostępne wyniki w USOSie.
Rozwiązaniem wzorcowym - i właściwie jedynym poprawnym rozwiązaniem pojawiającym się u Państwa - było zaadoptowanie podejścia z zadania z ćwiczeń o sortowaniu 5 elementów. Przy scalaniu mamy 7*6/2 = 21 możliwych odpowiedzi (miejsc, gdzie należy wstawić krótszy ciąg w wyjściowy 7-elementowy ciąg). Dowolny algorytm można przedstawić jako drzewo decyzyjne, gdzie każdy węzeł wewnętrzny odpowiada porównaniu. Każda z 21 odpowiedzi musi się pojawić w jakimś liściu, więc drzewo to musi mieć wysokość co najmniej 5.
Oryginalną modyfikacją tego rozumowania było następujące: analizując jak na ćwiczeniach omawialiśmy permutację 5-elementową, pokazujemy, że że do posortowania dowolnej 7-elementowej permutacji potrzeba sufit(log2(7!)) = 13 porównań. Zaproponujmy taki algorytm sortowania: sortujemu pierwsze 5 elementów (algorytmem z ćwiczeń, 7 porównań) i ostatnie dwa (trywialne, jedno porównanie), po czym scalamy. Jeśli uda nam się scalić w (pesymistycznie) 4 porównaniach, to otrzymujemy algorytm o (pesymistycznie) 7+1+4=12 porównaniach, sprzeczność.
Było wiele rozwiązań, które próbowały argumentować, że np. (tutaj a1,a2 oraz b1,b2,...,b5 to dane ciągi)
Nie twierdzę, że takiego rozumowania nie można doprowadzić do końca - w końcu teza "nie da się 4 porównaniami" jest prawdziwa - ale żadne z takich rozwiązań nie było blisko naprawdę formalnego uzasadnienia tej tezy, biorąc pod uwagę pełną ogólność tego, co algorytm może robić.
W tej części można było uzystać 1pkt, jeśli się miało dobre podejście, ale się niepoprawnie policzyło liczbę możliwych wyników.
W tej części kluczową sztuczką było by porównać jako pierwsze a1 z b2 (lub symetrzycznie, a2 z b4). Jeśli się tak zaczęło, trudno było już zepsuć.
Przykładowe rozwiązanie. Porównujemy a1 z b2. Jeśli a1 < b2, to określamy pozycję a1 porównując je z b1. Pozostałe 3 porównania zużywamy na wsortowanie a2 zwykłym wyszukiwaniem binarnym. Jeśli a1 > b2, to też a2 > b2. Wsortowujemy zarówno a1 jak i a2 w ciąg b3,b4,b5 przy pomocy wyszukiwania binarnego (2x2 porównania) lub scalamy jak w merge-sorcie (3+2-1 porównania).
Najczęstsze błędy tutaj to:
W tej części można było uzyskać 1pkt, jeśli ktoś dobrze zaczynał, ale nie dokończył. Można było uzyskać 2pkt, jeśli był drobny, łatwo naprawialny błąd w dalekiej odnodze ogólnie poprawnego algorytmu.