Runda 15 - omówienie zadań

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

Runda 15 - omówienie zadań

Postautor: macbon » 03 kwie 2014, 20:46

Test (http://www.spoj.com/ALGOLIGA/problems/AL_15_01/)

Jest to najprostsze zadanie z całego zestawu, pomimo tego zostało do niego nadesłanych całkiem sporo błędnych zgłoszeń. Zadanie sprowadza się do sprawdzenia kilku warunków dla każdego z pytań i zsumowania punktów. Ponieważ jest to test jednokrotnego wyboru to Jarek i Marek mogą uzyskać 2 punkty tylko wtedy kiedy udzielili tej samej odpowiedzi na dane pytanie i jednocześnie odpowiedź ta jest różna od odpowiedzi Darka. 1 punkt za pytanie uzyskają jeżeli ich odpowiedzi się różnią i co najmniej jedna z nich jest różna od odpowiedzi Darka. W każdym innym przypadku studenci otrzymają za pytanie 0 punktów.

Kompresja 3 (http://www.spoj.com/ALGOLIGA/problems/AL_15_02/)

Jest to jedno z dwóch zadań tekstowych, które w zasadzie bardziej sprawdzały umiejętności programistyczne niż wiedzę algorytmiczną. Naszym celem była kompresja albo dekompresja tekstu według zasad określonych w treści zadania. Niezależnie od przeprowadzanej operacji najlepszą strategią było wczytywanie danych wyraz po wyrazie.

Kompresja
Wczytujemy pierwszy wyraz do zmiennej A i ustawiamy liczbę identycznych wyrazów na 1. Następnie w pętli wczytujemy kolejne wyrazy z wejścia do zmiennej B. Jeżeli A = B to zwiększamy liczbę identycznych wyrazów o 1, w przeciwnym wypadku sprawdzamy czy warto przeprowadzić kompresję liter w ramach A, a następnie kompresję jego sąsiadujących wystąpień. Po zakończeniu tego etapu wypisujemy wyraz A na ekran w wersji skompresowanej albo nie. Następnie ustawiamy ostatnio wczytany wyraz B jako nowe A i resetujemy liczbę wystąpień z powrotem do 1. Cały proces powtarzamy aż do momentu wczytania wszystkich danych.

Dekompresja
Po wczytaniu wyrazu sprawdzamy jego zawartość znak po znaku. Gdy trafiamy na literę to od razu kopiujemy ją do zmiennej przechowującej zdekompresowaną postać wyrazu. W przypadku napotkania na znak * wczytujemy wszystkie cyfry następujące po nim jednocześnie zamieniając je na liczbę. Po wczytaniu całej liczby do zmiennej L powielamy ostatnio dodaną literę w postaci zdekompresowanej L-1 razy. Jeżeli napotkamy znak / to również wczytujemy następującą po nim liczbę do zmiennej przechowującej liczbę powtórzeń analizowanego wyrazu. Po zakończeniu dekompresji wypisujemy nasz wyraz na ekran odpowiednią liczbę razy.

Oczywiście jest to tylko jedno z możliwych rozwiązań.

Formatowanie (http://www.spoj.com/ALGOLIGA/problems/AL_15_03/)

Podobnie jak "Kompresja 3" było to zadanie bez haczyka. Jedyna rzecz, na którą należało zwrócić uwagę to białe znaki. Nie dozwolone było wypisywanie nadmiarowych spacji na końcach linii czy też brak przejścia do nowej linii na końcu wyjścia (był to chyba najczęstszy błąd).

Sponsorzy (http://www.spoj.com/ALGOLIGA/problems/AL_15_04/)

Zadanie to można było rozwiązać na dwa sposoby. Pierwszy z nich zakładał rozłożenie każdej potęgi p^w na czynniki pierwsze. Po rozłożeniu wszystkich, wykładniki przy takich samych czynnikach pierwszych należało zsumować, w ten sposób uzyskiwaliśmy rozkład całego iloczynu. Kolejnym krokiem było rozłożenie na czynniki pierwsze liczby m. Liczba m dzieli nasz iloczyn bez reszty jeżeli każdy z jej czynników pierwszych występuje w iloczynie z takim samym lub większym wykładnikiem. W sposobie tym należało też zwrócić uwagę na fakt, że wykładniki przy czynnikach pierwszych mogą przekroczyć zakres zmiennych 32 bitowych.

Prostszym podejściem do tego zadania było skorzystanie z szybkiego potęgowania modularnego i sprawdzenie czy wartość iloczynu modulo m jest równa 0.

Gra 2 (http://www.spoj.com/ALGOLIGA/problems/AL_15_05/)

Zadanie to można rozwiązać korzystając z programowania dynamicznego. Potrzebna nam jest do tego 2-wymiarowa tablica, w której to w j-tej kolumnie i-tego wiersza będziemy przechowywać wartość na ile sposobów (modulo 10^12) można dotrzeć na pole o współrzędnych j,i z pola 0,0. Ponieważ zaczynamy z pola 0,0 to jest oczywiste, że możemy na nie dotrzeć dokładnie na 1 sposób. Wiemy również, że ponieważ rzucamy jednocześnie dwoma kostkami i zaczynamy z pola 0,0 to nie jesteśmy w stanie dotrzeć na żadne z pól w 0 wierszu i w 0 kolumnie z wyjątkiem wcześniej wymienionego, a zatem wartość tych komórek wynosi 0. Po ustawieniu tych wartości początkowych możemy obliczyć całą resztę. Obliczamy wartości w naszej tablicy wierszami. Będziemy zatem kolejno obliczać wartości dla współrzędnych
1,1 2,1 3,1 4,1 ... x,1
1,2 2,2 3,2 4,2 ... x,2
...
1,y 2,y 3,y ... x,y

Obliczenie wartości dla pola j,i polega na zbadaniu na jakim polu mogliśmy być w poprzednim ruchu, pamiętając o tym, że w poziomie mogliśmy wykonać jedno z h, zaś w pionie jedno z v przesunięć. Załóżmy, że analizujemy ruch, w którym na pole j,i dostaliśmy się przesuwając o a jednostek w poziomie i b jednostek w pionie. W pierwszej kolejności sprawdzamy czy pole j-a,i-b w ogóle mieści się na naszej planszy o współrzędnych od 0,0 do x,y. Jeżeli nie przechodzimy do analizy następnej pary przesunięć. Jeżeli tak to do wyniku dla pola j,i dodajemy na ile sposobów mogliśmy się dostać na pole j-a,i-b, wartość ta została obliczona wcześniej. Suma wyników dla pól, z których mogliśmy się dostać na pozycję j,i jest jednocześnie wynikiem dla tego pola. W związku z powyższym po obliczeniu całej tablicy szukany wynik znajduje się w wierszu y w kolumnie x.

Windy (http://www.spoj.com/ALGOLIGA/problems/AL_15_06/)

Jest to zadanie grafowe, które najprościej można rozwiązać korzystając z algorytmu przeszukiwania grafu wszerz (BFS). Na pierwszy rzut oka jako wierzchołki naszego grafu możemy wytypować piętra budynku, jednak w takiej sytuacji pojawiają się dwa problemy. Po pierwsze nie jesteśmy w stanie szybko sprawdzić czy możemy się znaleźć na piętrze w danej jednostce czasu, bo musimy przeszukać całą listę przedziałów czasowych szefa. Po drugie każde piętro możemy odwiedzić wielokrotnie, za każdym razem z innym czasem, co sugeruje nam, że w takiej sytuacji bardziej odpowiedni byłby algorytm Dijkstry. Jak zatem zastosować w tym zadaniu algorytm BFS? W bardzo prosty sposób, wystarczy zmienić definicję wierzchołka. Wierzchołek grafu powinien odpowiadać parze piętro,czas. W takim wypadku cały graf możemy reprezentować jako tablicę dwuwymiarową, gdzie pierwszy index odpowiada piętru zaś drugi czasowi. Takie podejście upraszcza nam rozwiązanie. W każdej komórce przechowujemy jedną z 3 wartości: 0 - wierzchołek nieodwiedzony, 1 - odwiedzony przez Jana, 2 - odwiedzony przez Szefa. Przypuszczenia odnośnie pozycji szefa możemy od razu nanieść na nasz graf wstawiając wartość 2 w odpowiednich wierzchołkach. Dzięki temu sprawdzenie czy możemy znaleźć się na danym piętrze w danej jednostce czasu sprowadza się do sprawdzenia czy wierzchołek był już odwiedzony. Po wykonaniu algorytmu BFS na takim grafie, wystarczy przeszukać wiersz dla piętra na którym miał znaleźć się Jaś i wypisać komórkę o najmniejszym indeksie czasu odwiedzoną przez Jana.

Scrabble 2 (http://www.spoj.com/ALGOLIGA/problems/AL_15_07/)

Jeżeli popatrzeć na statystyki to zadanie Scrabble 2 okazało się najtrudniejszym ze wszystkich chociaż moim zdaniem wcale takim nie jest. Pierwszym krokiem rozwiązania tego zadania jest wyznaczenie wszystkich wyrazów. Można to zrobić zwykłym przejściem wszystkich wierszy i kolumn i zliczaniem sąsiadujących ze sobą liter. Jeżeli mamy ciąg 2 albo więcej liter to trafiliśmy na wyraz. Zapisujemy współrzędne jego końców i obliczamy jego wartość. Ponieważ dokładane wyrazy muszą się łączyć to następnym etapem jest wyznaczenie macierzy sąsiedztwa, w której zaznaczymy, które pary wyrazów się przecinają. Ostatnią częścią jest obliczenie maksymalnego wyniku Grzesia. W związku z tym, że maksymalna liczba wyrazów to zaledwie 10 to spokojnie możemy sprawdzić każdą kolejność układania wyrazów. Musimy zatem przeanalizować 10! permutacji co daje 3 628 800 przypadków. Analizując daną permutację bierzemy kolejne wyrazy i sprawdzamy w macierzy sąsiedztwa czy łączą się z tymi ułożonymi przed nimi. Jeżeli któryś się nie łączy tzn. że dana permutacja jest niemożliwa do zrealizowania. Jednocześnie przechodząc przez listę wyrazów zliczamy sumy punktów jakie mógł uzyskać gracz, który zaczynał rozgrywkę i ten który grał po nim. Większą z tych sum porównujemy z dotychczasowym maksymalnym wynikiem i w przypadku, gdy jest większa od niego aktualizujemy go.

Nowa waluta 2 (http://www.spoj.com/ALGOLIGA/problems/AL_15_08/)

Zadanie to należało rozwiązać przy użyciu zmodyfikowanego drzewa przedziałowego. Nasze drzewo powinno realizować dwie funkcje. Pierwsza z nich to klasyczne liczenie sumy elementów w danym przedziale. Druga to liczenie NWD dla danego przedziału. Oczywiście równie dobrze mogą to być dwa osobne drzewa. W momencie gdy jesteśmy w stanie obsłużyć te 2 operacje nasze zadanie jest już praktycznie rozwiązane bo sprowadza się do wykonania dwóch zapytań dla danego przedziału i podzieleniu obliczonej sumy przez wyznaczone NWD.

Plamy (http://www.spoj.com/ALGOLIGA/problems/AL_15_09/)

Ponieważ Jaś ma zamiar posprzątać podłogę idąc od skrajnie lewego punktu do skrajnie prawego (LP) i z powrotem (PL), na początku warto posortować wczytane punkty rosnąco względem współrzędnej x. Wiemy, że punkt 1 i punkt n będą należeć zarówno do ścieżki LP jak i PL, a zatem to co nam pozostało to wyznaczenie, do której z tych ścieżek będzie należał każdy z punktów od 2 do n-1. Problem ten możemy rozwiązać przy pomocy funkcji rekurencyjnej F do której jako parametry przekazujemy numery dwóch punktów p1 i p2. Zadaniem funkcji jest obliczenie najkrótszej ścieżki p1 -> n -> p2 zawierającej tylko jeden nawrót w n. Rozwiązaniem zadania będzie zatem wywołanie funkcji F(1,1). Wewnątrz funkcji analizujemy do której ścieżki powinniśmy dodać punkt o numerze p3 równym 1+max(p1,p2). W przypadku gdy p3 jest równy n wynikiem funkcji jest po prostu Odległość(p1, p3) + Odległość(p3, p2). W przypadku gdy p3 jest mniejszy od n sprawdzamy czy bardziej się opłaca dodać go do ścieżki LP czy PL, a zatem wynikiem funkcji w takim wypadku jest mniejsza z 2 wartości:

  1. Odległość(p1, p3) + F(p3, p2)
  2. Odległość(p2, p3) + F(p1, p3)

Ponieważ wywołania funkcji F dla danych par parametrów mogą się powtarzać to w celu przyspieszenia naszego programu powinniśmy zapamiętywać obliczone wyniki np. w tablicy dwuwymiarowej. W momencie ponownego wywołania funkcji dla danej pary punktów zwracamy wyznaczony wcześniej wynik.

Demonstracja 2 (http://www.spoj.com/ALGOLIGA/problems/AL_15_10/)

Kolejne zadanie grafowe w zestawie. Tym razem mamy zwiększyć wagę krawędzi, na których znajdują się budynki władz tak, aby najkrótsza ścieżka od wierzchołka p do wierzchołka k nie przebiegała przez żadną z nich. Oznaczmy sobie ulice przez, które nie może przejść demonstracja jako a i b. Żeby obliczyć o ile należy podnieść koszt krawędzi musimy w pierwszej kolejności znać koszt 4 rodzajów najkrótszych ścieżek:

  1. z p do k nie przechodzącej przez a i b, oznaczmy ją jako s1
  2. z p do k przechodzącej tylko przez a, oznaczmy ją jako s2.
  3. z p do k przechodzącej tylko przez b, oznaczmy ją jako s3.
  4. z p do k przechodzącej przez a i b, oznaczmy ją jako s4.

Do obliczenia tych kosztów możemy użyć lekko zmodyfikowanego algorytmu Dijkstry, który na każdym wierzchołku zamiast pojedynczego kosztu najkrótszej trasy przechowuje koszty dla każdego z 4 rodzajów tras wymienionych powyżej. Kiedy już obliczymy koszty, nasz wynik możemy wyznaczyć za pomocą kilku prostych operacji. W pierwszej kolejności wyznaczamy o ile trzeba zwiększyć koszt krawędzi a tak, aby trasa s2 była droższa od s1. Następnie to samo robimy dla krawędzi b i trasy s3. Wartości o jakie podnieśliśmy wagi krawędzi a i b sumujemy, oznaczamy tę sumę jako S. Teraz pozostało nam ostatnie sprawdzenie, jeżeli koszt trasy s4 powiększony o naszą sumę S jest nadal mniejszy od kosztu s1 to zwiększamy wartość S, tak aby ten warunek nie był spełniony. Odpowiedzią jest oczywiście wartość S.
macbon
Koordynator AlgoLigi
 
Posty: 184
Rejestracja: 19 wrz 2012, 23:38

Re: Runda 15 - omówienie zadań

Postautor: flashion » 05 kwie 2014, 00:51

Władze stolicy właśnie dowiedziały się, że w najbliższym czasie planowane jest przejście ogromnej demonstracji. Miasto pełne jest zabytków i starych kamienic, które mogłyby ucierpieć w przypadku zamieszek, ale naszych polityków to nie obchodzi. Jedyne na czym im zależy to, aby demonstracja nie przeszła ulicami, na których znajdują się ratusz oraz sejm. W związku z powyższym urzędnicy negocjują właśnie z organizatorami trasę przemarszu.

Organizatorzy przedstawili sprawę jasno - chcą jedynie dotrzeć z punktu p do punktu k ponosząc przy tym jak najmniejszy koszt (w stolicy organizatorzy demonstracji muszą płacić za możliwość przejścia przez daną ulicę, wyznaczoną przez urząd miasta stawkę). Nic prostszego pomyśleli urzędnicy - wyznaczymy koszty przejścia przez ulice na których są ratusz i sejm w taki sposób, aby demonstracja je ominęła!

Po opracowaniu tej genialnej koncepcji (i otrzymaniu w związku z tym premii) urzędnicy zabrali się za... poszukiwanie osoby, która zrobi wszystko za nich i poprosili nas, aby umieścić to zadanie w AlgoLidze.


Chciałem pogratulować tylko autorowi tego tekstu :)
flashion
 
Posty: 8
Rejestracja: 24 lis 2013, 22:50


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