Runda 25 - omówienie zadań

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

Runda 25 - omówienie zadań

Postautor: macbon » 08 lis 2015, 21:01

Ruletka

Zadanie możemy rozwiązać symulując kolejne skoki piłeczki i sprawdzając czy nie trafiliśmy na pole o numerze k. Zauważmy, że jeżeli piłka drugi raz odbija się od tego samego pola tzn. że cała sekwencja skoków zaczyna się powtarzać od nowa i dalsza symulacja nie ma sensu. W takim wypadku wypisujemy NIGDY. To ile razy odwiedziliśmy do tej pory każde pole możemy przechowywać w tablicy jednowymiarowej, w której indeks odpowiada numerowi pola, a wartość zapisana w komórce pod tym indeksem określa ile razy je odwiedziliśmy. Przypadek, na który warto było zwrócić uwagę to sytuacja, w której p = k.

Sztuka dla sztuki

W pierwszej wersji zadania jego celem miało być tylko i wyłącznie wyznaczenie wysokości prostopadłościanu po zalaniu klocków mieszanką. Rozwiązaniem jest wyszukiwanie binarne wysokości. Minimalna wysokość prostopadłościanu to min(W[i,j]), zaś potencjalna maksymalna wysokość to max(W[i,j])+l/(m*n). Szukamy zatem wysokości z tego przedziału. Dla każdej wysokości analizowanej podczas wyszukiwania przechodzimy po naszej tablicy stosów i liczymy ile litrów mieszanki powinniśmy posiadać żeby zalać dzieło do tego poziomu. Innymi słowy liczymy sumę różnic w-W[i,j] dla każdego W[i,j] mniejszego od w, gdzie w to aktualnie analizowana wysokość. Jeżeli obliczona suma jest mniejsza bądź równa l to przesuwamy dolną granicę przedziału na w, w przeciwnym wypadku przesuwamy górną granicę na w-1. Po zakończeniu wyszukiwania binarnego naszą odpowiedzią jest dolna granica przedziału.

W wersji ostatecznej zadania postanowiłem dorzucić warunek, że wysokość musi być możliwie jak największym elementem ciągu Fibonacciego. Dla powyższego rozwiązania jest to niewielka zmiana wystarczy wygenerować największy element ciągu Fibonacciego mniejszy bądź równy znalezionej wysokości. Jak się jednak okazało ta zmiana treści zadania otworzyła furtkę dla dużo prostszego algorytmu. Zauważmy, że elementów ciągu Fibonacciego mniejszych bądź równych 10^6+10^12 (maksymalna wysokość mogąca wystąpić) jest zaledwie 60. Wystarczy zatem dla każdej z tych 60 wysokości policzyć czy mamy tyle mieszanki żeby ją uzyskać, tak jak to robiliśmy w wyszukiwaniu binarnym. Następnie spośród tych, które możemy uzyskać wybieramy największą.

Ze względu na duże wartości wysokości należało użyć zmiennych 64 bitowych (np. long long w C/C++).

Kajdan

Wyobraźmy sobie, że liczby z przedziału [1;z] to wierzchołki grafu skierowanego, zaś przekształcenia pomiędzy tymi liczbami to krawędzie o wagach równych kosztom przekształceń. Analizujemy kolejne elementy ciągu: 1-szy i n-ty, 2 i n-1, 3 i n - 2, ... Jeżeli liczby a b w parze są takie same i są to liczby pierwsze to oczywiście nie musimy nic zmieniać. Jeżeli jednak, któryś z tych warunków nie jest spełniony to musimy znaleźć taką liczbę pierwszą p dla której suma długości ścieżek a->...->p i b->...->p w grafie jest minimalna. Wynikiem jest zatem suma długości takich ścieżek dla każdej pary.

Jak to zrealizować w praktyce. Na początek wyznaczamy sobie najkrótsze ścieżki pomiędzy każdą parą liczb. W związku z tym, że maksymalna wartość z jest mała możemy użyć do tego celu algorytmu Floyd-Warshalla o złożoności O(z^3). Załóżmy, że obliczone długości ścieżek mamy zapisane w dwuwymiarowej tablicy D. Następnie dla każdej możliwej pary liczb wyznaczamy minimalny koszt przekształcenia na liczbę pierwszą, a zatem P[a,b] = min(D[a,p] + D[b,p]) gdzie p to liczba pierwsza z przedziału [1;z]. Teraz analizując kolejne pary wystarczy odczytywać wartości z tablicy P.

W zadaniu należało zwrócić szczególną uwagę na dwie rzeczy. Po pierwsze wynik może się nie zmieścić w zmiennych 32 bitowych, zatem należało użyć typu 64 bitowego (np. long long w C/C++). Po drugie szczególną uwagę trzeba było zachować przy ciągach o nieparzystej długości. W takim wypadku środkowy element ciągu również powinien być analizowany o czym wiele osób zapominało.

Tłumacze

Klasyczne zadanie na programowanie dynamiczne. Rozważmy sytuację w której nad księgą siedzi już i-ty tłumacz, przetłumaczonych zostało j stron i zrobiono przy tym k błędów. Stan ten określmy jako DP[i,j,k]. Na ile sposobów mogliśmy dojść do takiej sytuacji? Jest to suma dwóch przypadków:
1) Jeżeli i-ty tłumacz nie przetłumaczył ani jednej strony, to liczba sposobów jest równa sytuacji, w której nad księgą siedziało i - 1 tłumaczy, którzy przetłumaczyli j stron robiąc k błędów czyli DP[i - 1, j, k]
2) Jeżeli ostatnia strona została przetłumaczona przez i-tego tłumacza to liczba sposobów jest równa sytuacji, w której nad księgą siedziało i tłumaczy, którzy przetłumaczyli j - 1 stron robiąc łącznie k - b_i błędów, gdzie b_i to liczba błędów robiona przez i-tego tłumacza per strona. Żeby ta sytuacja była możliwa k >= b_i.
Przypadkiem prostym jest DP[0,0,0] = 1.

Podsumowując:
if k >= b_i then DP[i,j,k] = (DP[i - 1,j,k] + DP[i,j - 1,k - b_i]) mod (10^9+9)
else DP[i,j,k] = DP[i - 1,j,k]
.

Odpowiedzią jest DP[n,s,b].

Ukraina kontratakuje dzięki Adamowi

Na początku chciałbym bardzo podziękować Adamowi Bąkowi, który był tak miły, że zgodził się testować to zadanie w piątek o godzinie 23:00, na 13 godzin przed rozpoczęciem rundy :)

Rozwiązaniem zadania jest lekko wzbogacony algorytm do wyznaczania najniższego wspólnego przodka (LCA) w drzewie. Na początku przechodzimy nasze drzewo algorytmem przeszukiwania w głąb (DFS). Podczas przechodzenia drzewa dla każdego wierzchołka wyznaczamy jego przodków oddalonych o 2^0, 2^1, 2^2, ..., 2^lb(n) pozycji, w takiej właśnie kolejności. Jak to zrobić szybko? Załóżmy, że wyznaczam przodka wierzchołka v oddalonego o 2^2 pozycji. W tym momencie mam już wyznaczonych przodków v oddalonych o 2^0 i 2^1 pozycji. Jeżeli znam przodka oddalonego o 2^1 pozycji, oznaczmy go jako u, to wystarczy, że spośród jego wyznaczonych przodków wybiorę tego oddalonego o 2^1 pozycji od niego. Uogólniając jeżeli przez P[v,i] oznaczymy przodka oddalonego o 2^i pozycji od v to P[v,i] = P[P[v,i-1],i-1]. Ponieważ w zadaniu musimy wyznaczać obiekty do zniszczenia podczas wyznaczania przodków będziemy również wyznaczać 10 najważniejszych obiektów na trasie od wierzchołka v do jego poprzednika oddalonego o 2^i pozycji oznaczmy tę listę obiektów jako M[v,i]. M[v,i] = scal_i_ogranicz_do_10_najmniejszych_elementow(M[v,i-1], M[P[v,i-1],i-1]). Po przejściu drzewa i wyznaczeniu wartości w tabelach P i M na każde zapytanie możemy odpowiedzieć w czasie logarytmicznym wyznaczając LCA, a następnie scalając listy obiektów na trasie od wierzchołka a do LCA oraz od wierzchołka b do LCA. Bardziej szczegółowy opis samych zapytań zostanie zamieszczony później.
macbon
Koordynator AlgoLigi
 
Posty: 184
Rejestracja: 19 wrz 2012, 23:38

Re: Runda 25 - omówienie zadań

Postautor: kaspro » 08 lis 2015, 21:30

Gratuluję Panowie, bardzo pomysłowe zadania, bardzo dobrze dobrane poziomy trudności.
kaspro
Koordynator AlgoLigi
 
Posty: 69
Rejestracja: 13 kwie 2013, 21:01

Re: Runda 25 - omówienie zadań

Postautor: narbej » 08 lis 2015, 21:35

Gratuluję wspaniałych zadań i udanej rundy.

Ruletka
Czy na pewno potrzebna jest odzielna tablica na trzymanie informacji ile razy odwiedziliśmy dany punkt na ruletce? Przecież już jednorazowe powtórzenie powoduje odpowiedź NIGDY. Więc mogłaby to być tablica bool? Ale można też wykorzystać tablicę skoków, zerując w niej wartości skoku [lub zmieniając wartość na ujemną] w odwiedzonym polu.


PS
Wydaje mi się, że witman masz prawo dodania zadań do pl.spoj? Jeżeli się mylę, to oczywiście z przyjemnością zrobię to nawet jeszcze dziś, gdy je zakwalifikujecie.

PS 2
Jak ktoś miałby wątpliwości, to pytania do ruletki były z mojej strony tylko retoryczne ;-). Jeszcze lepszy pomysł podsunął poniżej @znirzejskwarka
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 25 - omówienie zadań

Postautor: macbon » 08 lis 2015, 21:40

Dzięki za gratulacje. Odnośnie Ruletki to oczywiście druga tablica nie jest konieczna.
macbon
Koordynator AlgoLigi
 
Posty: 184
Rejestracja: 19 wrz 2012, 23:38

Re: Runda 25 - omówienie zadań

Postautor: znirzejskwarka » 08 lis 2015, 21:50

@narbej

W zadaniu Ruletka nie jest potrzebna wcale dodatkowa tablica, wystarczy ta z wejścia i nie trzeba jej modyfikować.
Wystarczy zasymulować n kroków i jeśli przez n kroków nie trafiliśmy na pole k, to już nigdy na nie nie trafimy.
znirzejskwarka
 
Posty: 8
Rejestracja: 11 cze 2013, 07:48

Re: Runda 25 - omówienie zadań

Postautor: witman » 08 lis 2015, 21:52

Enigma w wersji light po raz trzeci

Niech zadanie pozostanie łamigłówką. Podpowiem tylko, że aby zdekodować napis trzeba z całego kodu odczytać kody ASCII poszczególnych liter, liczbę ich wystąpień i pozycje, na których występują.

6, 8 i 343
Potrzebna wiedza: cechy podzielności lub schemat Hornera.

Limity czasowe były tak dobrane, że zadanie można było rozwiązać przeliczając liczbę z systemu siódemkowego na dziesiątkowy wykonując obliczenia modulo (odpowiednio) 6, 8 i 343. Efektywniejszym podejściem było jednak wykorzystanie cech podzielności liczby w systemie o podstawie siedem przez 6, 8 i 343, które są analogiczne jak dla 9, 11 i 1000 w systemie dziesiątkowym.

Iloczyn

Wykorzystując język, w którym istnieje implementacja arytmetyki dużych liczb, zadanie jest trywialne. W innych językach należy wykorzystać algorytm szybkiego mnożenia.

Wytyczanie działek
Potrzebna wiedza: Twierdzenie Eulera dla grafów planarnych.

Z treści zadania wynika, że mamy do czynienia z grafem planarnym. Wystarczy więc wyznaczyć liczbę składowych grafu, stosując np. DFS (oznaczmy ją przez K).
Wtedy dla N - słupków (wierzchołki) i M - kawałków siatki (krawędzie) mamy N+[liczba działek]-M = K+1.

Nowy ogród króla Bajtolomeusza
Potrzebna wiedza: symbol Newtona, arytmetyka modularna

Opiszę rozwiązanie na przykładzie dla N=6, M=5.
Obrazek
Trzeba zauważyć, że aby obejść staw np. od południowego-wschodu trzeba przejść przez jeden z czerwonych punktów, a nie ma trasy, która przechodziłaby przez więcej niż jeden taki punkt. Jeśli symbol Newtona oznaczymy (n k), to liczba możliwych przejść wynosi
(4 2)*(5 3)+(4 1)*(5 2)+ (4 0)*(5 1)
Jednak obliczenie z takiego wzoru, wymaga wielokrotne obliczania odwrotności modulo => TLE.
Można jednak przekształcić wzór wyciągając pierwszy czynnik przed nawias,
(4 2)*(5 3)*(1+(2/3)*(3/3)+((2*1)/(3*4))*((3*2)/(3*4)))
i sprowadzając ułamki do wspólnego mianownika, co daje stałą liczbę obliczeń odwrotności. Wyrażenia w liczniku i mianowniku powstałego ułamka, można obliczyć stosując programowanie dynamiczne.
Analogicznie obliczamy liczbę możliwych obejść stawu od północnego-zachodu i sumujemy wyniki.
Zadanie można oczywiście rozwiązać stosując inne podejście, ale kluczowe jest ograniczenie liczby wyznaczania odwrotności modulo.

Gra w wielu wymiarach
Potrzebna wiedza: Twierdzenie Sprague’a-Grundy’ego.

Traktujemy figury jako gry o następujących wartościach:
Skoczek = NWD ze wszystkich współrzędnych
Goniec = MAX ze wszystkich współrzędnych
Wieże rozbijamy na tyle gier ile jest wymiarów, każda o wartości równej odpowiedniej współrzędnej.
Liczymy wartość funkcji SG. Jeśli jest niezerowa, to przeglądamy po kolei wszystkie figury szukając tej, którą należy wykonać pierwszy ruch.
witman
Koordynator AlgoLigi
 
Posty: 78
Rejestracja: 10 kwie 2013, 21:03


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