Runda 12: omówienie zadań

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

Runda 12: omówienie zadań

Postautor: adam_bak » 24 lis 2013, 12:54

Tutaj po zakończeniu rundy pojawią się omówienia (zapewnie nie od razu wszystkich) zadań. Zachęcam do lektury :)
adam_bak
Koordynator AlgoLigi
 
Posty: 68
Rejestracja: 20 wrz 2012, 09:44

Re: Runda 12: omówienie zadań

Postautor: hejkatufilip » 24 lis 2013, 20:47

Czekam na omówienie szóstego! :)
hejkatufilip
 
Posty: 2
Rejestracja: 25 paź 2013, 08:30

Re: Runda 12: omówienie zadań

Postautor: adam_bak » 24 lis 2013, 21:01

Zadania łatwe nie były, ale mamy nadzieję, że dzięki temu większa sastysfakcja z rozwiązanych ;)


Winda
Zadania nie należy lekceważyć, ma pewne haczyki. Na początek zauważmy, że to trochę dużo, więc symulowanie ruchów windy dla każdego piętra odpada. Również sprawdzenie długości najdłuższego plateau nie jest wystarczającym testem, bowiem możemy go oszukać, np.: oraz ciąg ruchów: UUDUUDUUDUUD. Niby jedziemy zawsze bardzo mało w górę, jednak dla tego testu odpowiedź to oczywiście NIE.

Trik tutaj polega na znalezieniu 'rozpiętości' pięter jaką generuje nam ciąg ruchów. Zacznijmy poruszanie od piętra z numerem . Następnie dla każdego ruchu w górę zwiększamy go o jeden, dla każdego ruchu w dół - zmniejszamy o jeden. Pamiętamy maksymalne i minimalne piętro w zmiennych powiedzmy: . Po zakończeniu wykonywania ruchów odpowiedzią na zadane pytanie jest: .



Punkty w kole
Wzór można oczywiście znaleźć w internecie i to była świadoma decyzja przy wyborze zadania. Tym razem jednak, wbrew pozorom, ten wzór można dość łatwo wyprowadzić samemu, co chcę tutaj pokazać.

Niech , żeby było nieco ogólniej. Bez straty ogólności załóżmy, że środek koła jest w punkcie . To co chcemy znaleźć to: . Najpierw zliczmy wszystkie takie punkty leżące na osiach układu współrzędnych. Punktów typu dla jest dokładnie , czyli tyle ile liczb całkowitych dodatnich mniejszych lub równych . Mamy więc w sumie wszystkich takich punktów leżących na osiach (ta jedynka to od punktu , który wcześniej pominąłem).

Zauważmy, że pozostałe punkty podzieliły się na cztery równoliczne grupy - każda w obrębie jednej ćwiartki układu współrzędnych. Zliczmy więc . Dla ustalonego chcemy policzyć ile jest różnych , takich że nie wyjdziemy z punktem poza koło. Jest ich dokładnie tyle ile wynosi największe takie , które się jeszcze mieści. No, ale największe takie to oczywiście , co wynika z przekształcenia nierówności koła. Wszystkich możliwych wartości jest tyle ile liczb: . Zatem ostateczny wzór to:



którego obliczenie pozwala zmieścić się w limicie czasowym.



Gra w mnożenie
Zauważmy, że w dowolnym momencie gry, gdy ruch wykonuje Alicja, może ona osiągnąć dowolną z liczb mniejszych lub równych (dla akturalnej wartości ).Co by nie zrobiła wartości: są Boba ( już nie). W takim razie możemy iść dopóki , pamiętając kto wykonuje aktualny ruch, po największych osiąganych przez zawodników liczbach. Gdy rusza się Alicja - , a gdy rusza się Bob - . Gdy osiągniemy , wiemy czyj jest ruch, więc wiemy kto wygrał. Złożoność dla pojedynczego testu.



Liczby Erdősa
Na pierwszy rzut oka widać, że mamy tutaj do czynienia z jakąś odległością w grafie. Istotnie, gdy zinterpretujemy wejście w następujący sposób:
- autorzy są wierzchołkami grafu
- dwóch autorów łączy krawędź w grafie wtedy i tylko wtedy gdy opublikowali wspólnie jakąś pracę
to zapuszczając na otrzymanym grafie BFSa (źródło w Erdősie) jesteśmy w stanie policzyć dla każdego naukowca długość najkrótszej ścieżki w grafie łączącej go z Erdősem.

W tym podejściu jednak pojawiają się pewne problemy. Pierwszy z nich jest taki, że graf może być bardzo gęsty (dużo krawędzi) - nie zmieści nam się w pamięci.
Drugim problemem jest czas tworzenia grafu - pesymistycznie (i taki test też występuje) może być naukowców, którzy pracowali nad tą samą publikacją. O ile w średnim przypadku możemy sobie poradzić nieźle czasowo sortując publikacje leksykograficznie i potem wykonując porównań stringów dla każdego bloku który tworzy jedna publikacja dorzucając do grafu odpowiednie krawędzie, o tyle w pesymistycznym przypadku sobie nie poradzimy.

Trzeba zejść z rozmiarem grafu tak czy siak. Rzeczywiście możemy to zrobić nieco inaczej go interpretując. Niech zarówno autorzy jak i publikacje będą wierzchołkami. Autor jest połączony krawędzią z publikacją wtw gdy był jej (współ)autorem. Powstaje graf dwudzielny na którym jak wyżej możemy zapuścić BFSa z Erdősa. Ścieżki do autorów wydłużają się dokładnie dwukrotnie względem poprzedniego podejścia. Wystarczy więc wyniki podzielić przez 2. Takie podejście daje AC z dobrym czasem.

Taka uwaga: dużo osób miało problemy z wejściem/wyjściem. Trzeba na to w zadaniu uważać, bo dużo optymalnych już algorytmów wypisywało dziwne rzeczy na wyjście. Polecam stringi, strumienie i cin.getline do publikacji. Staram się dawać łagodne limity (bo sam nie mam rewelacyjnych czasów), aby stringi i strumienie przechodziły.



Jedynki
Pierwsze pytanie jakie się nasuwa w tym zadaniu to dla jakich liczb istnieje szukana wielokrotność. Szybko można zauważyć, że dla wielokrotności lub nie istnieje (ostatnia cyfra się nie zgodzi). Zastanówmy się jak będzie z pozostałymi, tzn. . Szukamy najmniejszego dla którego . Z twierdzenia Eulera , dla . Zatem dla pozostałych istnieje.

Uwaga: Oczywiście nie możemy szukać wyniku obliczając kolejne wielokrotności i sprawdzając czy się składają z samych jedynek, ponieważ już przykładowe wejście daje nam intuicję że potrwałoby to za długo.

Wracając do pierwszego akapitu. Niestety nie wystarczy policzyć , ponieważ może to nie być najmniejsze możliwe , a takich szukamy. Możemy spróbować pociągnąć to dalej z kongruencji: . Obliczanie rzędu modulo tak po prostu licząc kolejne potęgi modulo odpada bo jest koszmarnie wolne. Wiemy jednak (łatwo udowodnić na podstawie tego co już zostało tutaj napisane), że ten rząd musi dzielić , więc możemy istotnie zawęzić obszar poszukiwań. Dodatkowo możemy rozbić tę kongruencję z Chińskiego twierdzenia o resztach i znaleźć lokalne rzędy modulo kolejne potęgi liczb pierwszych dzielące . Wynikiem będzie NWW lokalnych rzędów. Takie podejście daje czas bliski zeru.

No ale po co się tak męczyć ;) Można zupełnie elementarnie. Skoro nie możemy liczyć kolejnych wielokrotności , to sprawdzajmy kolejne liczby postaci oraz ich reszty z dzielenia przez . Jeśli mamy -tą resztę, nazwijmy ją , to kolejną obliczamy ze wzoru: (bo tak się właśnie tworzy kolejne liczby składające się z samych jedynek- poprzednia razy 10 plus 1). Gdy otrzymamy resztę równą to mamy odpowiedź ile jedynek ma ta szukana wielokrotność. Skończymy po co najwyżej krokach, bo tylko tyle jest możliwych reszt, więc dostaniemy AC.



Gemmologia
Tutaj oczywiście do głowy przychodzi sporo zachłannych algorytmów. Żaden niestety nie jest poprawny, bo ta gra nie jest taka prosta (narzucone kolejność kamieni i ruchy zawodników). Poza tym rozmiar sugeruje, że jest to dynamik. No i fakt, że ja zawsze daję dynamika oraz żadne z poprzednich zadań nim nie było :)

Rzeczywiście możemy wyprowadzić rekurencyjny wzór. Pytamy o maksymalny możliwy zysk pierwszego gracza. Taki zostanie osiągnięty tylko wtedy gdy pierwszy gracz gra na zmaksymalizowanie swojego zysku, a drugi na zminimalizowanie swojego (zmaksymalizowanie pierwszego) i obaj znają swoje strategie.

Chcemy obliczyć wynik - zysk pierwszego gracza po grze na kamieniach od pierwszego do -tego - uzależniając go jakoś od wyników dla mniejszych przedziałów - krótszych gier. Jako pierwszy gracz wybieramy lewy bądź prawy kamień, jednak potem robi to samo drugi gracz (i od razu musimy jego względnić, bo wzór rekurencyjny jest na pierwszego gracza). Możemy jednak wybrać co jest dla nas bardziej optymalne - maksimum z maksimów. Dostajemy wzór:



gdyż do wyboru dwa kamienie i od razu uwzględniamy najlepszy dla nas ruch przeciwnika. Taki wzór daje nam od razu algorytm. Wynik dla danego przedziału zależy od wyników dla krótszych przedziałów. W takim razie wystarczy żebyśmy wypełniali macierz wyników częściowych dynamika diagonalami od najdłuższej do najkrótszej. W zadaniu jest jednak ograniczenie pamięci, a skoro może być to ta macierz by musiała być typu long long. Dla zajęłoby to okropnie dużo. No ale jak już kilka zadań na AL nas nauczyło, skoro wypełniamy macierz diagonalami, to równie dobrze możemy wypełniać ją wierszami od dołu go góry. A skoro tak to nie potrzebujemy całej macierzy. W tym przypadku wynik zależy od przedziału krótszego o więc musimy pamiętać ostatnie wiersze tej macierzy. Złożoność czasowa , pamięciowa i AC z dobrym czasem.



Dostawca pizzy 2
W zadaniu proszą nas o znalezienie ścieżki Hamiltona w grafie skierowanym. Tak postawiony problem jest NP-zupełny, jednak kluczowym zdaniem w treści jest: "Składa się ona z n domów, ponumerowanych kolejno liczbami naturalnymi od 1 do n, z których każde dwa połączone są jednokierunkową ulicą.". Nie jest to więc przypadkowy graf. Jest to skierowana klika i dla czegoś takiego problem jest istotnie prostszy.

Znów zastanówmy się najpierw dla jakich danych wejściowych odpowiedzią będzie NIE. Okazuje się, że nigdy tak nie będzie :)
Można udowodnić, indukcyjnie po liczbie wierzchołków, że każda skierowana klika posiada ścieżkę Hamiltona. Istotnie dla teza trywialnie zachodzi. Niech zachodzi ona dla wszystkich . Rozważmy skierowaną klikę o wierzchołkach. Powstanie ona z dołączenia do pewnej kliki o wierzchołkach kolejnego wierzchołka i odpowiednio skierowanych krawędzi między nim, a resztą. Weźmy ścieżkę Hamiltona tej pewnej kliki: i pokażmy, że można ją wydłużyć do ścieżki Hamiltona w nowej klice. Jeśli krawędź idzie z dokładanego wierzchołka do to dokładany ląduje na początku. Jeśli idzie z do dokładanego to dokładany, nazwijmy go , idzie na koniec ścieżki. Jeśli żadne z powyższych nie zachodzi to istnieje takie , że mamy krawędzie: oraz i możemy go wsadzić pomiędzy te dwa. Nowa klika ma więc ścieżkę Hamiltona.

To od razu się przekłada na algorytm o złożoności czasowej . Trzymamy listę, której kolejne elementy to kolejne wierzchołki aktualnej ścieżki. Na początku znajduje się w niej tylko . Iteracyjnie bierzemy kolejne wierzchołki i szukamy im miejsca na liście. Dostajemy AC.


Zadanie można również rozwiązać tak zwaną metodą Piotrka :) ale nie wiem czemu to działa. Zapuszczamy DFSa z wierzchołka o najmniejszym stopniu wejściowym na grafie transponowanym. Kolejność post-order odwiedzania wierzchołków wyznacza nam ścieżkę Hamiltona. Złożoności te same.
adam_bak
Koordynator AlgoLigi
 
Posty: 68
Rejestracja: 20 wrz 2012, 09:44

Re: Runda 12: omówienie zadań

Postautor: flashion » 24 lis 2013, 22:51

Oczywiście, teoria liczb u mnie leży.

Czy w zadaniu Festyn wystarczyło jedno drzewo przedziałowe <xor, xor>?

Startowałem pierwszy raz i fajnie się bawiłem.
Dzięki za zadania!
flashion
 
Posty: 8
Rejestracja: 24 lis 2013, 22:50

Re: Runda 12: omówienie zadań

Postautor: adam_bak » 25 lis 2013, 16:52

Rzeczywiście wystarczyło drzewo typu przedział-przedział z operacją xor.
Niebawem powinny pojawić się szkice rozwiązań pozostałych zadań.

Super, że się podobało ;)
I gratuluję rewelacyjnego wyniku!
adam_bak
Koordynator AlgoLigi
 
Posty: 68
Rejestracja: 20 wrz 2012, 09:44

Re: Runda 12: omówienie zadań

Postautor: agrochowski » 25 lis 2013, 22:29

Również standardowo świetnie się bawiłem, chociaż nie poszło mi jakoś specjalnie dobrze ;) .

Moje rozwiązanie do zadania "Konkatenacja Liczb" miało najlepszy czas (pewnie ze względu na fast i/o), a nie ma go na liście rozwiązań na http://zadania-algorytmiczne.blogspot.com/ dlatego podzielę się nim tutaj:

Moje rozwiązanie polegało na zamianie każdej z liczb na wejściu na taką postać, aby wszystkie miały jednakową liczbę cyfr (wybrałem 10 ze względu na ograniczenie 10^9 w zadaniu). Zamieniałem je w następujący sposób, np. 926 w 9269269269, czy też 87 w 8787878787. Następnie wartości te sortowałem i na tej podstawie wiedziałem która liczba z wejścia będzie na której pozycji. Również dosyć proste i przyjemne rozwiązanie.
agrochowski
 
Posty: 4
Rejestracja: 05 sie 2013, 00:30

Re: Runda 12: omówienie zadań

Postautor: kaspro » 25 lis 2013, 23:14

Dobre :), a ja się tak namęczyłem z tym zadaniem.
kaspro
Koordynator AlgoLigi
 
Posty: 69
Rejestracja: 13 kwie 2013, 21:01

Re: Runda 12: omówienie zadań

Postautor: kokosek » 26 lis 2013, 02:14

A oto moje omówienie zadań:

Bajtomir na giełdzie
http://zadania-algorytmiczne.blogspot.c ... l1208.html

Głuchy telefon epicykloidorów
http://zadania-algorytmiczne.blogspot.c ... dorow.html

Festyn w Bajtlandii
http://zadania-algorytmiczne.blogspot.c ... l1211.html

Bajtek w przedszkolu
http://zadania-algorytmiczne.blogspot.c ... l1205.html

Konkatenacja liczb
http://zadania-algorytmiczne.blogspot.c ... l1204.html

Dzięki Artur za podzielenie się swoim algorytmem! Dodałem go na bloga wraz z małą optymalizacją.

Jeśli jeszcze macie jakieś inne algorytmy (niekoniecznie optymalne) czy optymalizacje/modyfikacje to śmiało piszcie. :-)
kokosek
Koordynator AlgoLigi
 
Posty: 107
Rejestracja: 20 wrz 2012, 16:04

Re: Runda 12: omówienie zadań

Postautor: flashion » 26 lis 2013, 16:48

adam_bak pisze:Jedynki

No ale po co się tak męczyć ;) Można zupełnie elementarnie. Skoro nie możemy liczyć kolejnych wielokrotności , to sprawdzajmy kolejne liczby postaci oraz ich reszty z dzielenia przez . Jeśli mamy -tą resztę, nazwijmy ją , to kolejną obliczamy ze wzoru: (bo tak się właśnie tworzy kolejne liczby składające się z samych jedynek- poprzednia razy 10 plus 1). Gdy otrzymamy resztę równą to mamy odpowiedź ile jedynek ma ta szukana wielokrotność. Skończymy po co najwyżej krokach, bo tylko tyle jest możliwych reszt, więc dostaniemy AC.


Dlaczego możemy skończyć po n krokach? Skąd wiemy, że dostaniemy wszystkie reszty w n pierwszych krokach?
flashion
 
Posty: 8
Rejestracja: 24 lis 2013, 22:50

Re: Runda 12: omówienie zadań

Postautor: adam_bak » 26 lis 2013, 23:31

Skończymy w co najwyżej krokach (niektóre reszty mogą być nieosiągalne).
Wszystkich możliwych reszt z dzielenia przez jest dokładnie i są to liczby: . Wyrazy wyżej wspomnianego ciągu są właśnie z tego zbioru. Zgodnie z zasadą szufladkową Dirichleta w kolejnych wyrazach tego ciągu występują co najmniej dwa takie same elementy. Skoro tak, to mamy cykl, bowiem jest jednoznacznie wyznaczone przez więc jak raz się zapętli to potem będzie występował tylko ten cykl. Stąd ciąg jest cykliczny, a w tym cyklu musi być szukane , gdyż wielokrotności lub odrzucamy na początku. Indeks pierwszego takiego zera jest odpowiedzią do zadania, bowiem interesuje nas najmniejsza wielokrotność składająca się z samych jedynek.
adam_bak
Koordynator AlgoLigi
 
Posty: 68
Rejestracja: 20 wrz 2012, 09:44

Następna

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