Runda 22 - omówienie zadań

Tutaj możesz uzyskać pomoc w rozwiązywaniu zadań dostępnych w ramach AlgoLigi

Runda 22 - omówienie zadań

Postautor: macbon » 26 kwie 2015, 20:00

Jeżeli masz ciekawe alternatywne rozwiązanie do któregokolwiek z zadań to zachęcamy do opisania go w tym wątku!

2048

Jest to jedno z najprostszych zadań w tej rundzie. Nie zawiera ono żadnego haczyka, jedyna trudność polega na dokładnym zaimplementowaniu przebiegu rozgrywki. Ponieważ plansza jest bardzo mała (n <= 10) to możemy wszystkie ruchy symulować przesuwając liczby w zwykłej tablicy dwuwymiarowej. W związku z tym, że przy operowaniu na wierszach/kolumnach takiej tablicy bardzo łatwo o głupią pomyłkę (np. modyfikacja złej zmiennej indeksowej w pętli) dobrym pomysłem jest skopiowanie zawartości danego wiersza/kolumny do jednowymiarowej tablicy pomocniczej. W tablicy jednowymiarowej kierunek ruchu przestaje mieć dla nas jakiekolwiek znaczenie. Możemy przyjąć, że zawsze przesuwamy wartości np. do lewej strony. Dzięki temu operację łączenia pól możemy przenieść do osobnej funkcji, której użyjemy we wszystkich typach ruchów. Po obliczeniu nowych wartości kopiujemy je z powrotem do naszej tablicy dwuwymiarowej.

Częstym błędem jaki występował w tym zadaniu było łączenie pola, które powstało w wyniku innego połączenia w tym samym ruchu. Na przykład jeżeli wykonujemy ruch w prawo w wierszu zawierającym liczby 4 2 2 to prawidłowym wynikiem powinno być 4 4. Tymczasem wiele osób po połączeniu dwójek dodatkowo łączyło czwórki.

Jeremy Clarkson

Naszym zadaniem jest znalezienie takiej ścieżki pomiędzy punktami, aby cały czas skręcała ona w lewo oraz żeby żadna para odcinków łączących punkty nie przecinała się. Kluczową rzeczą jaką powinniśmy zauważyć jest fakt, że taka ścieżka zawsze będzie istniała. Każdy zbiór punktów możemy połączyć ze sobą tworząc łamaną o kształcie zbliżonym do spirali. Ta obserwacja rozwiązuje nam dwa podstawowe problemy w tym zadaniu. Po pierwsze nasza łamana o kształcie spirali zawsze skręca w tę samą stronę. Po drugie odcinki w takiej łamanej nie przecinają się. W związku z powyższym jedyna trudność jaka nam pozostała to jej zbudowanie.

Jako nasz punkt początkowy wybierzmy dom klienta o najmniejszej współrzędnej X, a jeżeli jest ich kilka ten o najmniejszej współrzędnej Y. Teraz musimy wyznaczyć kolejne n - 1 punktów na naszej ścieżce. Każdy z nich wyznaczamy w ten sam sposób. Oznaczmy przez P_o ostatni punkt dodany do naszej ścieżki, zaś przez P_k punkt będący kandydatem do dodania do niej. P_k jest właściwym wyborem wtedy i tylko wtedy jeżeli wszystkie pozostałe niedodane jeszcze punkty leżą po lewej stronie odcinka P_o - P_k. Do wyznaczenia, po której stronie odcinka leży dany punkt możemy wykorzystać algorytm sprawdzający względne położenie punktów. Ponieważ domów jest co najwyżej 100, wyszukiwanie kolejnego punktu, który mamy dodać do ścieżki możemy realizować w czasie O(n^2) nie martwiąc się o to, że przekroczymy limit czasu. Całość rozwiązania ma zatem złożoność O(n^3).

Podział

Zadanie to możemy rozwiązać przy użyciu funkcji rekurencyjnej f(a,b). Funkcja ta oblicza minimalną sumę wartości dwóch ciągów rozpoczynających się odpowiednio od elementów o numerach a i b i zawierających wszystkie elementy aż do n. Przy jej wywołaniu możemy również nie definiować pierwszego elementu jednego z ciągów przekazując zamiast jego numeru wartość 0. Zauważmy, że skoro a i b są początkami ciągów to w każdym rekurencyjnym wywołaniu funkcji musimy podjąć decyzję, do którego ciągu mamy dodać następny nieprzydzielony element, czyli ten o numerze równym max(a,b)+1, oznaczmy go jako c. Jeżeli dodamy go do ciągu zaczynającego się od elementu o numerze a to wynikiem będzie wartość bezwzględna różnicy elementów a i c plus minimalna suma wartości ciągów rozpoczynających się od elementów c i b. Jeżeli dodamy go do ciągu rozpoczynającego się od elementu o numerze b to wynikiem będzie wartość bezwzględna różnicy elementów b i c plus minimalna suma wartości ciągów rozpoczynających się od elementów a i c. Oczywiście jeżeli, któryś z ciągów nie ma ustalonego początku, a lub b jest równe 0, to w takim wypadku wartość bezwzględna różnicy jest pomijana bo to c stanie się jego pierwszym elementem. Podsumowując w każdym wywołaniu wybieramy minimum z dwóch wartości:
  • IF a = 0 THEN 0 ELSE abs(W[a] - W[c]) ENDIF + f(c,b)
  • IF b = 0 THEN 0 ELSE abs(W[b] - W[c]) ENDIF + f(a,c)
Jak łatwo zauważyć warunkiem stopu dla wywołań rekurencyjnych jest sytuacja gdy max(a,b) jest równe n, wtedy nie mamy kolejnego elementu do przydzielenia, a zatem nasza funkcja może od razu zwrócić 0. Rozwiązaniem całego zadania jest wartość funkcji f(1,0) albo f(0,1), to którą wybierzemy nie ma znaczenia. Jako, że funkcja może być wielokrotnie wywoływana dla tego samego zestawu parametrów powinniśmy zapisywać wyniki wywołań w tablicy dwuwymiarowej i przy ponownym uruchomieniu dla tego samego zestawu parametrów od razu zwracać wynik. Jest to typowe zastosowanie programowania dynamicznego w wersji Top-Down.

Rekrutacja

Rozwiązanie naiwne tego zadania polega na liniowym wyszukaniu dla każdego zgłoszenia czy istnieje inne o lepszych parametrach. Niestety z racji maksymalnej liczby rozwiązań równej 10^5 takie zgłoszenie na pewno nie zmieści się w wyznaczonym limicie czasu. Musimy zatem poszukać trików, które pozwolą nam zdecydowanie je przyspieszyć. Naszą optymalizację rozpoczynamy od posortowania wszystkich rozwiązań w kolejności niemalejących wartości c, następnie niemalejących wartości p oraz nierosnących wartości j. Dzięki posortowaniu zgłoszeń nie musimy już analizować wartości c bo wiemy, że każde kolejne rozwiązanie ma czas wykonania w najlepszym wypadku równy poprzedniemu. Jednocześnie znamy już jedno rozwiązanie, które na pewno pozostanie w naszym zbiorze, jest to oczywiście zgłoszenie będące na pierwszym miejscu. Teraz możemy rozpocząć analizę kolejnych rozwiązań począwszy od drugiego na liście. Pierwszą rzeczą jaką powinniśmy sprawdzić jest to czy bieżące zgłoszenie nie jest czasem równe poprzedniemu. Jeżeli jest możemy od razu je usunąć i przejść do następnego rozwiązania. Jeżeli warunek równości nie jest spełniony, to sprawdzamy czy aktualne zgłoszenie nie ma najmniejszego zużycia pamięci albo najlepszej jakości kodu z dotychczas przeanalizowanych. Jeżeli któryś z tych parametrów został poprawiony to mamy gwarancję, że takie rozwiązanie na pewno pozostanie w naszym zbiorze. Oczywiście minimalną wartość p i maksymalną wartość j powinniśmy przechowywać w zmiennych pomocniczych, żeby za każdym razem nie sprawdzać całej listy. Jeżeli zgłoszenie nie osiągnęło najlepszej wartości dla jednego z tych dwóch parametrów to nie pozostaje nam nic innego jak sprawdzić czy wśród już dodanych rozwiązań nie znajduje się takie o lepszych wartościach p i j, jeżeli jest to oczywiście bieżące zgłoszenie zostaje usunięte ze zbioru. Jak widać główną operacją jaką będziemy wykonywać na naszej liście rozwiązań jest usuwanie, musimy zatem zadbać również o dobór odpowiedniej struktury danych do jej reprezentacji. Tutaj najlepszym wyborem jest lista dwukierunkowa (np. list w bibliotece STL) gdyż umożliwia ona usuwanie elementu w czasie O(1). Po zastosowaniu wyżej opisanych usprawnień nasze rozwiązanie powinno bez problemu zmieścić się w ustalonym limicie czasu.

Detektyw Monk

Problem ten można rozwiązać za pomocą algorytmu przeszukiwania wszerz (BFS) zaczynając od permutacji numerów albumów jaką otrzymaliśmy na wejściu. Niestety w przypadku gdy liczba albumów wynosi 9 drzewo poszukiwań jest na tyle duże, że czysty algorytm BFS nie zmieści się w wyznaczonym limicie czasu. W związku z tym musimy poszukać sposobu na zmniejszenie rozmiaru naszego problemu. Pierwszym krokiem jest sprawdzenie jaka jest maksymalna liczba przestawień pomiędzy dowolną permutacją 9 albumów a ich ustawieniem docelowym czyli 1 2 3 4 5 6 7 8 9. Żeby to sprawdzić odpalamy nasz algorytm BFS tym razem zaczynając od permutacji 1 2 3 4 5 6 7 8 9 i zapamiętujemy maksymalną odległość jaką z niej osiągnęliśmy. Jak się okazuje maksymalna liczba przestawień potrzebnych do uporządkowania 9 albumów wynosi 5. Ta informacja pozwala nam na przygotowanie szybszego rozwiązania z wykorzystaniem techniki Meet in the middle.

Zapuśćmy nasz algorytm BFS zaczynając od permutacji początkowej, ale tym razem nie rozwijając drzewa poszukiwań dalej niż na odległość dwóch przestawień. Jeżeli w tym wywołaniu osiągnęliśmy ustawienie docelowe to wypisujemy niezbędną liczbę ruchów. Jeżeli nie udało nam się znaleźć wyniku to odpalamy drugie wywołanie BFS tym razem zaczynając od permutacji docelowej. W tym wywołaniu drzewo również nie powinno być rozwijane dalej niż na odległość dwóch przestawień. Jeżeli podczas drugiego uruchomienia natknęliśmy się na permutację osiągniętą również w pierwszym wywoływaniu przeszukiwania wszerz to sumujemy odległości od niej do permutacji początkowej i docelowej. Obliczoną liczbę przestawień porównujemy z najlepszym do tej pory osiągniętym wynikiem i w razie potrzeby aktualizujemy. Jeżeli w drugim uruchomieniu BFS nie dotarliśmy do żadnej permutacji z pierwszego wywołania tzn. że liczba przestawień potrzebnych do uporządkowania zbioru jest większa od 4, a ponieważ wiemy, że maksymalną odległością jest 5 to właśnie 5 będzie naszym wynikiem.
macbon
Koordynator AlgoLigi
 
Posty: 184
Rejestracja: 19 wrz 2012, 23:38

Re: Runda 22 - omówienie zadań

Postautor: kokosek » 28 kwie 2015, 01:38

Od zera do Billa Gatesa
W tym zadaniu wystarczył algorytm zachłanny. Sortujemy ceny w porządku nierosnącym i wybieramy co k-te ubranie. Jeśli z końcówki ubrań nie uzbieramy ich k, to po prostu je ignorujemy.

Zabawa Jasia i Małgosi
Tutaj z kolei do wykorzystania było proste drzewo przedziałowe. Jeżeli długość x=7482591 i k=3 to najpierw musimy znaleźć największą cyfrę z pierwszych 5 pozycji. Musimy bowiem zostawić 2 cyfry, jako że mamy wypisać ich 3. Będzie to cyfra 8. Następnie musimy znaleźć największą cyfrę zaczynając na następującej po ostatniej maksymalnej cyfrze (czyli 8) a kończąc na przedostatniej (bo musimy sobie zostawić jeszcze 1 cyfrę w zapasie). A więc wybieramy maxa z podciągu 259 - i jest to 9. Ostatnią cyfrę wybieramy z ciągu zaczynającego się po 9 i kończącego na ostatniej cyfrze (bo nie potrzebujemy już żadnej innej cyfry). Jest tylko jedna taka cyfra - 1. Odpowiedź to zatem 891. Musimy więc umieć odpowiedzieć na pytanie "jaka jest największa cyfra w danym przedziale". No i tego dowiemy się tworząc z x drzewo przedziałowe.
Musimy też zapamiętywać indeks maksymalnej cyfry z danego zapytania. Bo musimy wyszukiwać następną cyfrę od pozycji tuż PO poprzedniej maksymalnej cyfrze. Czyli w powyższym przykładzie po znalezieniu 8 zaczynaliśmy od 2. Ja to zrealizowałem za pomocą wyszukiwania binarnego, ale pewnie dało się prościej. A więc utworzyłem sobie 10 tablic - każda zawierała indeksy wystąpień danej cyfry. No i jeśli maksymalną cyfrą okazało się 8, to szukałem w tab[8] za pomocą wyszukiwania binarnego indeksu, który był najmniejszą liczbą, większą lub równą początkowi przedziału, w którym znalazłem tą 8. Czyli 8 z przykładu szukałem w przedziale 0..4 (indeksując od 0). A pierwszą (i jedyną) 8 w tym przedziale była ta o indeksie 2. Tak więc następne wyszukiwanie zaczynałem od indeksu 3.

Bezpieczne konie
Moje najtrudniejsze zadanie. Wymyśliłem jeszcze 1 trudniejsze, ale generator został na partycji do której nie mam póki co dostępu, więc nie zdążyłem go utworzyć. Mam już jednak pomysł na jeszcze lepszy generator, więc zadanie jeszcze się ukaże w późniejszej AlgoLidze.
Do rzeczy. Ciąg można znaleźć tutaj: https://oeis.org/A189145. Różni się tym, że w moim zadaniu nie bierzemy pod uwagę 0 lub 1 konia na planszy. Dzięki temu trudniej było znaleźć ten ciąg na OEIS. Jak widać, jest tam podane równanie rekurencyjne. Można więc odpowiedzieć na zapytanie w czasie O(log n) korzystając z szybkiego potęgowania macierzy o rozmiarze 8. To jednak nie dawało AC. Zauważyłem bowiem, że kolejne wyrazy tego ciągu to kwadraty liczb. Wpisałem więc ich pierwiastki ponownie do OEIS i wyskoczył mi ciąg: https://oeis.org/A006498. Znów ciąg rekurencyjny, ale 2 razy mniej wyrazów. Możemy więc spotęgować macierz o rozmiarze 4 i podnieść wynik do kwadratu (oczywiście wszystko modulo 1e9+7). Ale i to mi było mało. Jednym ze wzorów wymienionych na stronie jest bowiem: a(2*n) = F(n+1)^2, a(2*n - 1) = F(n+1)*F(n). Wystarczy więc macierz 2x2, która pozwala na szybkie obliczenie liczby Fibonacciego mod 1e9+7. Widzimy jednak, że dla nieparzystych n potrzebujemy 2 kolejnych liczb Fibonacciego. Ale to absolutnie nie problem, bo wystarczy podnieść macierz 2x2 do potęgi n+1 i w macierzy wynikowej otrzymamy obie potrzebne liczby.
Tak więc wzorcówka to potęgowanie macierzy 2x2. Przeszedł jednak 1 program z potęgowaniem macierzy 4x4, więc uważam, że limity czasu nie były za ostre. Dało się zaliczyć zadanie z cin/cout bez korzystania z funkcji sync_with_stdio.
Niestety nie jestem dobrym matematykiem, więc nie umiem wyprowadzić tego ostatniego wzoru wykorzystującego iloczyn liczb Fibonacciego.
kokosek
Koordynator AlgoLigi
 
Posty: 107
Rejestracja: 20 wrz 2012, 16:04

Re: Runda 22 - omówienie zadań

Postautor: narbej » 28 kwie 2015, 10:30

Zabawa Jasia i Małgosi
Tak, jak napisał kokosek, drzewo maksimów jest tu najlepszą [jedyną?] alternatywą. Można jeszcze pomyśleć o drobnej optymalizacji - czasami, w trakcie dokładania [czasami już od samego początku] przedział wyboru skórczy się do jednego [jedności i za chiny dalej już się nie będzie chciał skórczybyk skórczyć '-) ]
Możnaby od takiego momentu [i od tej pozycji] przepisywać jak leci.
Skoro drzewo jest takie dobre, to czy nie można go jeszcze bardziej wykorzystać? Czy nie można zapamiętywać w drzewie zarówno cyfry jak i pozycji?
{cyfra, pozycja} Cyfry szukamy maks, a pozycji min, więc możnaby zapamiętywać: {cyfra, dlugosc_x - pozycja} czyli max, max.
Jak to można zrobić "technicznie", aby nie bawić się w make_pair, czy struktury?
np tak:
do_zapamiętania_w_drzewie = (cyfra << 20) + dlugosc_x - pozycja // wartość 20 jest tu do "obliczenia" i musi spełniać (1 << 20) > 10^6 [zakres w zadaniu], więc równie dobrze może być 21, 22, 23 ... 31? [no nie 31 już nie, musi zostać jeszcze miejsce na char, a czy nie chcemy się "zmieścić" w int? Czyli po poprawce:
2^31 > (char << x) > zakres
Jak "odzyskiwać" [wyłuskiwać] dane z drzewa?
wartosc = max_w_przedziale(a..b)
cyfra = wartosc >> 20
pozycja = dlugosc_x - wartosc & ((1<<20) - 1)
---
Tak zrobiłem.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 22 - omówienie zadań

Postautor: rr_ » 28 kwie 2015, 12:50

Z tym Jasiem i Małgosią można jeszcze inaczej :)
Ja uzyłem 10 kolejek (oznaczmy je jako queue<int> q[10]) - na początku przechodzimy po ciągu i wrzucamy do kolejki o indeksie równym danej cyfrze jej pozycję, np. dla 7482591 do q[7] trafi 0, do q[4] trafi 1, do q[8] trafi 3 itd.
Potem wystarczy z tychże kolejek y razy wybrać "najlepszą" cyfrę tzn. największą taką, której da się uzyć (nie jest po lewej od ostatnio wybranej i "zostawi" wystarczająco wiele po swojej prawej na wybranie pozostałych). A więc zaczynamy od kolejki z pozycjami dziewiątek, jeśli znajdziemy taką spełniająca warunki to bierzemy ją, jeśli nie to przechodzimy do ósemek itd. I tak y razy. Problemem mogłoby być to, że sprzwdzalibyśmy ciągle te same indeksy przez co rosła by złożoność. Ale tutaj przychodzi z pomocą fakt, że jesli przy pierwszym sprawdzeniu danej cyfry jest ona po lewo od ostatnio wybranej to znaczy, że nie uzyjemy jej juz nigdy później. Mozemy zatem wyrzucać takie cyfry z kolejki przy sprawdzaniu. A zatem sprawdzania nie będzie więcej niz wrzucania * 10 i wszystko sie zamortyzuje. Razy 10, bo moze nastąpić np. taka sytuacja: 123456789 9, wtedy sprawdzamy dziewiątki, jest jedna, za daleko na prawo (zabraknie miejsca po prawej na kolejne 8 cyfr), ale nie możemy jej wyrzucić, bo moze przydac się później (jednocześnie widzimy, że jest już za daleko na prawo, więc nie sprawdzamy ewentualnych kolejnych dziewiątek, a co najwyzej tą jedną), przechodzimy do ósemek, taka sama sytuacja, potem z siódemkami itd., w końcu wybieramy jedynkę z samego początku, szukamy kolejnej cyfry - znowu zaczynamy od dziewiątek, sprawdzamy tę samą i znów musimy zostawić itd. - widać, że dziewiątka bedzie sprawdzana 9 razy, ósemka 8 itd.
Złożoność czasowa O(y) (jeśli uwzględnić podstawę zapisu jako k to złożonośc to O(y * k^2)), czyli nawet minimalnie lepiej niż z drzewami (jesli dobrze liczę, a jeśli nie to przynajmniej pewnie kod prostszy :) )
Ostatnio zmieniony 28 kwie 2015, 17:44 przez rr_, łącznie zmieniany 1 raz
rr_
 
Posty: 4
Rejestracja: 31 gru 2013, 04:56

Re: Runda 22 - omówienie zadań

Postautor: narbej » 28 kwie 2015, 13:30

Kody, moim zdaniem, najlepiej jest wrzucać, na portal Mariusza, jeżeli masz tan dostęp [jeżeli zrobiłeś alfabet morsa?], bo w ten sposób [tutaj] każdy ma dostęp do twojego kodu, ale może się mylę?
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 22 - omówienie zadań

Postautor: narbej » 28 kwie 2015, 14:20

A tam tylko uprawnieni ;-)

PS
Ja pewnie też postaram się tam dodać swój - po oczyszczeniu ze zbędnych komentarzy, i porobieniu ładnych wcięć, zagięć i takich tam upiększeń.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 22 - omówienie zadań

Postautor: kokosek » 28 kwie 2015, 16:24

Fajnie, że podzieliliście się swoimi rozwiązaniami. :-)
Ja nie wrzucę swojego kodu na stronę Mariusza, bo wrzucam tam tylko najprostsze kody (czyli takie jak ten Radka) lub jeśli nikt inny nie wrzucił swojego.
kokosek
Koordynator AlgoLigi
 
Posty: 107
Rejestracja: 20 wrz 2012, 16:04

Re: Runda 22 - omówienie zadań

Postautor: rr_ » 28 kwie 2015, 17:43

Ok, wrzucę zatem na stronę Mariusza, a nie tutaj (jak rozumiem tu: http://www.mariosoft.pl/spoj/rank.php?id=kody ).
rr_
 
Posty: 4
Rejestracja: 31 gru 2013, 04:56

Re: Runda 22 - omówienie zadań

Postautor: spectral_ » 28 kwie 2015, 17:48

Zabawa Jasia i Małgosi
Dwukierunkowa lista, idziemy od początku i zachłannie wyrzucamy strlen(x)-y elementów.
spectral_
Organizator AlgoLigi
 
Posty: 18
Rejestracja: 15 lip 2014, 15:27

Re: Runda 22 - omówienie zadań

Postautor: mario » 19 lip 2015, 01:10

Rekrutacja

Zamiast usuwać z listy można równie dobrze dodawać trójki do kolejki w czasie stałym.
Moim zdaniem złożoność opisanej metody to mocno zamortyzowana kwadratówka, limit czasowy można by trochę zwiększyć dodając bardziej wyszukane testy :).
Problemem pozostaje jeszcze wybór kierunku przechodzenia po liście. W zależności od tego, czy ten stół chcemy obejść "w prawo" czy "w lewo", jedno z rozwiązań dostaje TLE. Kłopotliwe zadanie, ale opisana metoda przechodzi, choć chyba nie powinna dla tak ustawionego limitu czasowego :/
Lepszym rozwiązaniem będzie chyba wrzucanie trójek do SET-a po wartości p i sprawdzanie tylko części uporządkowanej listy.
mario
Koordynator AlgoLigi
 
Posty: 59
Rejestracja: 10 kwie 2013, 21:21

Następna

Wróć do Zadania

Kto jest online

Użytkownicy przeglądający to forum: Google [Bot] i 2 gości

cron