Runda 17 - omówienie zadań

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

Re: Runda 17 - omówienie zadań

Postautor: mario » 16 lip 2014, 20:38

Wstążki
@radarek:
Nie, wszystkie rozwiązania bazują na wyszukiwaniu binarnym na przedziale. Różnica w czasach wynika głównie z wczytywania danych z wejścia.
Programy z czasami poniżej 0.3 s wykorzystują tzw. fastIO, cokolwiek to oznacza :)
Bardziej szczegółowe rozwiązanie opisał Piotr Kąkol tu: http://zadania-algorytmiczne.blogspot.com/2014/07/20178-wstazki-al1703.html

Krecik
Rozwiązanie o złożoności d*n^2 będzie zbyt wolne, zatem należy znaleźć rozwiązanie o złożoności d*n.
Do realizacji wystarczy kilka zmiennych pomocniczych, które będą przechowywać aktualne wartości dwóch wyrazów, długość aktualnego podciągu,
maksimum, które będzie nadpisywane oraz zmienna przechowująca długość ciągu złożonego wyłącznie z wartości ostatniego pobranego wyrazu.

//------------------

Zadanie Jasio włamywacz miało najwięcej zróżnicowanych algorytmów, jedno z rozwiązań powinno pojawić się wkrótce na blogu Piotrka.
mario
Koordynator AlgoLigi
 
Posty: 59
Rejestracja: 10 kwie 2013, 21:21

Re: Runda 17 - omówienie zadań

Postautor: Crucian » 07 sie 2014, 10:18

Dojdzie jeszcze omówienie zadania HANOI ?
Awatar użytkownika
Crucian
Organizator AlgoLigi
 
Posty: 37
Rejestracja: 07 sie 2014, 10:07

Re: Runda 17 - omówienie zadań

Postautor: radarek » 08 sie 2014, 00:44

Na wikipedii jest opisany wątek reprezentacji binarnej stanu krążków: http://en.wikipedia.org/wiki/Tower_of_H ... y_solution
Pomimo usilnych prób nie byłem za bardzo w stanie zrozumieć przykładu. Znalazłem na szczęście pięknie wyłożony algorytm tutaj: https://www.mail-archive.com/algogeeks@ ... 07726.html (przeczytaj cały wątek).
radarek
 
Posty: 4
Rejestracja: 13 lip 2014, 20:37

Re: Runda 17 - omówienie zadań

Postautor: kokosek » 18 wrz 2014, 20:05

kokosek
Koordynator AlgoLigi
 
Posty: 107
Rejestracja: 20 wrz 2012, 16:04

Re: Runda 17 - omówienie zadań

Postautor: narbej » 28 cze 2015, 10:46

kaspro pisze:Bazy danych
Oczywiście podałem przykładowe rozwiązanie, to które urzekło mnie najbardziej :) i które jest bardzo proste w implementacji. Wspomnę tylko, że przy rozwiązywaniu tego zadania należy przyjrzeć się dokładnie danym wejściowym. Kilka zgłoszeń nie maiło AC z tego powodu.

To znaczy? ;-)
Z opisu, wynika, że:
W drugim wierszu n unikatowych liczb naturalnych, które należy wstawić do drzewa BST

Czy należy to sprawdzać, tzn stopień unikatowości liczb w drugim wierszu?
Czy chodzi Ci tylko o maksymalną wartość liczb [2^32-1]
CZy może wreście oto, że w drugiej części danych [instrukcja i - insert], można "próbować" wstawić do bazy już istniejącą w niej liczbę i co się dzieje, po takiej próbie z poźniejszymi redo i reredo, czy takich sytuacji nie ma?

PS
Twoja implementacja jest zapewne bardzo prosta, ale jeżeli drzewo jest niezrównoważone, bardzo kosztowna - kopiowanie całego drzewa. Ja mam inny pomysł, ale niestety WA, więc na razie nie opisuję.
Taki przykład, do twojej implementacji: [operacje redo reredo - to tylko małokosztowna inkrementacja dekrementacja wskaźników, ale dla takich przykładowych danych - poniżej, insert to kopiowanie całej bazy]
10
0 1 2 3 4 5 6 7 8 9
2..[00000]
i 10
i 11
i 12
....

PS 2
Oczywiście, nawet jeżeli w testach [nie] występuje [uwzględniłeś lub nie] problem niezrównoważonego BST to i tak zadanie jest super. Gratuluję! ;-)
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 17 - omówienie zadań

Postautor: narbej » 29 cze 2015, 20:19

Ok. Jest AC moim pomysłem.
A polega on na tym, aby początkową bazę [drzewo] wpisać normalnie. Zapamiętujemy wartość n - jest to niekasowalna ilość danych. Dodatkowo pamiętamy wartość [zmienna] insert oraz last. Operacje z, y przesuwają insert pomiędzy n i last. Przy wyszukiwaniu dodatkowo sprawdzamy, czy wskaźniki [lewy lub prawy syn], nie wskazują na "adres" większy od insert. Jeżeli tak, to w tym momencie przerywamy przeszukiwanie drzewa. Przy operacji insert, dodatkowo musimy skasować [wyszukując rodzica] odpowiednie komórki. Aby takie kasowanie przyśpieszyć, można dodać dodatkowo trzeci wskażnik, na rodzica, ale wystarczy tylko w modyfikowalnej części drzewa.
Ponieważ, przy budowaniu całkowicie dynamicznym drzewa, adresy mogą być przydzielone dowolnie, bezpieczniej użyć tu "swojego" odpowiednio dużego bloku pamięci [np tablicy].

PS
Może napisałem to niezgrabnie i niejasno, więc jeżeli masz pytania i coś jest niejasne, pytaj, a postaram się wyjaśnić.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Poprzednia

Wróć do Zadania

Kto jest online

Użytkownicy przeglądający to forum: Obecnie na forum nie ma żadnego zarejestrowanego użytkownika i 1 gość

cron