Programowanie i algorytmy

Omówienie zadań IV rundy

powrót

Szyfrogram

W tym zadaniu należy zauważyć, że podany ciąg cyfr to tak naprawdę kody ASCII poszczególnych liter. Jedyny haczyk polega na tym, że niektóre znaki mają trzycyfrowy kod ASCII.

Największa suma cyfr

Dla danego przedziału [a..b] rozpoczynamy przeszukiwanie począwszy od liczby b (ponieważ szukamy największej). Liczba kroków, jakie musi wykonać algorytm jest równa co najwyżej liczbie cyfr liczby b. Rozwiązanie przedstawię na przykładzie [100.. 3200].

Max = 3200, suma_cyfr = 5;

Najmniej znaczącą cyfrę zamieniamy 9 i szukamy kolejnej niezerowej cyfry, którą zmniejszamy o 1. Napotkane po drodze 0 zamieniamy na cyfrę 9, co w rezultacie daje nam liczbę 3199. Sprawdzamy czy mieści się ona w przedziale, jeśli tak to

Max = 3199, suma_cyfr = 22;

Teraz kolejną cyfrą, która jest różna od 9 jest 1. Podmieniamy ją na 9 a kolejną niezerową zmniejszamy o 1:

Max = 2999, suma_cyfr = 29. W tym momencie kończymy działanie algorytmu, ponieważ najbardziej znaczącej nie zamieniamy na 9.

Księżyce Bajtka

W tym zadaniu mowa jest o księżycach Hipokratesa, których pole ma coś wspólnego z polem podanego trójkąta.

Zlot programistów

Żeby żadna osoba nie przysłaniała dane miejsce, (1) największy wspólny dzielnik wartości bezwzględnych współrzędnych danego punktu musi być równy 1. Żeby sprawdzić, czy dana osoba niezarezerwowała jeszcze miejsca, które spełnia warunek (1), to każdą rezerwację wrzucamy np. do mapy i w czasie logarytmicznym sprawdzamy, czy jest ono jeszcze wolne.

Silnia

Przeanalizujmy przykład z zadania:

1*2*3*4*5*6*7*8*9*10 mod (2*3*5)p = 0, oznacza to, że liczba po prawej stronie musi dzielić liczbę po lewej stronie bez reszty. Wszystko zależy od największej liczby pierwszej, czyli liczby 5, a dokładniej ile razy wystąpiła ona jako czynnik po lewej stronie. Rozbijmy sobie lewą stronę na czynniki pierwsze:

2*3*2*2*5*2*3*7*2*2*2*3*3*2*5

Widzimy, że wystąpiła ona 2 razy i taka jest odpowiedź.

Żeby szybko to policzyć zliczamy ilość wystąpień wielokrotności kolejnych potęg liczby z = 5 w liczbie n.

Czyli 10/5 = 2, 10/25 = 0 i tu kończymy. Wyniki sumujemy.

Liczby (nie)względnie pierwsze

W tym zadaniu należy każdą z liczb rozbić na czynniki pierwsze i zapamiętać każdy z nich tylko raz. Wynikiem będzie największa liczba czynników pierwszych. Popatrzmy na przykład:

4 7 14 21

4: 2

7: 7

14: 2, 7

21: 3, 7

Liczba 7 powtórzyła się trzy razy, więc 3 to rozwiązanie.

Drzewo genealogiczne

W tym zadaniu należy użyć dynamicznej struktury danych. Drzewo będzie rozwijane dynamiczne na potrzeby zadania. Każdy wierzchołek przechowuje następujące informacje: imię oraz trzy wskaźniki na kolejnych potomków. Najpierw musimy odtworzyć całą ścieżkę w drzewie. Zaczynamy od podanego pokolenia i potomka w tym pokoleniu. Wyliczamy ojca biorąc pod uwagę sumę ciągu oraz liczbę elementów w tym ciągu (czynność wykonujemy, aż dojdziemy do pierwszego przodka), czynność tą wykonujemy rekurencyjnie, następnie przy powrocie rekurencji budujemy dynamicznie potrzebną ścieżkę.

Binarne porównywanie

To zadanie można rozwiązać w dwojaki sposób.

Sposób I. Dla przykładu weźmy dwie liczby:

10001111

10110001

Jeśli na drugiej pozycji w drugiej liczbie wstawimy 1, to mamy pewność, że będzie ona zawsze większa od pierwszej niezależnie od ustawień pozostałych bitów:

10001111

11??????

A więc możemy w ten sposób wyliczyć liczbę permutacji pozostałych cyfr, a dla liczb binarnych jest to dwumian Newtona w tym przypadku n nad k, gdzie n to liczba znaków zapytania a k to liczba zer (jedynek). W drugim kroku wstawiamy powrotem 0 i szukamy kolejnego zera na i-tej pozycji w pierwszej liczbie:

10001111

101?????

Ponownie wykonujemy permutację pozostałego ciągu bitów, które możemy wstawić pod znaki zapytania, itd.

Otrzymane wyniki oczywiście dodajemy do siebie pamiętając o modulacji.

Sposób II. Szybszym i przyjemniejszym sposobem jest podejście dynamiczne. Rozwiązanie pozostawiam do samodzielnego odgadnięcia, gdyż nie jest ono skomplikowane.

Proste i punkty

Wczytane punkty wrzucamy np. do mapy, aby w czasie logarytmicznym je wyszukiwać. Dodatkowo (1) spamiętujemy liczbę punktów o współrzędnej x oraz liczbę punktów o współrzędnej y.

Dla każdej prostej Ax + By + C = 0, wykonujemy przekształcenie:

(2)    Ax + By = - C

Następnie rozwiązujemy równanie diofantyczne (3) Ax + By = nwd(A, B) wykorzystując rozszerzony algorytm Euklidesa wyznaczamy x i y. Jeśli – C nie dzieli się bez reszty przez nwd(A, B), to oznacza, że równanie (2) nie ma rozwiązania w zbiorze liczb całkowitych, a więc nie istnieją takie całkowite liczby x i y, które spełniają (2) i od razu wypisujemy 0.

Jeśli któraś z liczb A lub B ma wartość 0, to odpowiedź dajemy w czasie stałym, ponieważ wyniki przechowujemy w (1) – jest to najgorszy przypadek, ponieważ musielibyśmy sprawdzić największą liczbę punktów.

Ostatecznie, jeśli nwd(A, B)|C, to w prosty sposób wyznaczamy pierwsze rozwiązanie mnożąc stronami (3) przez –C/nwd(A, B) i otrzymujemy pierwszy punkt spełniający (2). Każdy następny jest postaci:

Xi = x + B/nwd(A,B)*k, Yi = y – A/nwd(A,B)*k, gdzie k jest dowolną liczbą całkowitą.

Kolejne punkty ograniczamy do dziedziny podanej w zadaniu i w czasie logarytmicznym sprawdzamy czy znajduje się w mapie i ile razy.

Chera Man

Rozwiązanie problemu jest w czasie liniowym. Problem rozwiązuje algorytm Manachera.

Naprzeciw

Dla nieparzystego n wynikiem jakiegokolwiek zapytania jest słowo BRAK. Dla parzystego n, rozpatrujemy dwa przypadki. Dla k>n/2 odpowiedzią jest k-n/2 w przeciwnym razie k+n/2.

Suma algebraiczna

W tym zadaniu wystarczy sprawdzić kilka warunków i na ich podstawie zamienić pionowe kreski na odpowiednie nawiasy. Jeśli pierwszy znak ciągu jest pionową kreską, dokonujemy zamiany na nawias otwierający i iterujemy dalej po ciągu, zamieniając na bieżąco kreski na nawiasy. Kreska stojąca bezpośrednio za nawiasem otwierającym, za znakiem plus lub za znakiem minus zamieniana jest na nawias otwierający, w pozostałych przypadkach zamieniamy znak kreski na nawias zamykający. Gotowe.

Ranking

Dla każdego przypadku testowego należy uzupełnić rekordy struktury o dane podane z wejścia i posortować je za pomocą funkcji porównującej, którą definiujemy zgodnie z podanymi priorytetami.

Spirala liczbowa

Rozwiązanie iteracyjne: poruszamy się po komórkach tablicy dwuwymiarowej zgodnie z przyjętą rotacją i uzupełniamy je kolejnymi liczbami naturalnymi do wyczerpania zerowych komórek tablicy. Rozwiązanie rekurencyjne: dla każdej komórki tablicy uruchamiamy funkcję rekurencyjną
Run(a,b,i,j) return j ? a+Run(b-1,a,j-1,a-i-1) : i+1;
Przy drukowaniu zwracamy uwagę na zera wiodące i białe znaki.

Dwa po(d)ciągi

Potrzebne jest rozwiązanie liniowe z uwagi na liczbę wagonów. Obliczamy sumę wszystkich wyrazów ciągu i zapamiętujemy w zmiennej pomocniczej S. Iterując liniowo ciąg a(n) od 1 do n sprawdzamy, czy suma wyrazów s_i = a(0) + ... + a(i), dla i>0, równa jest S-s_i, jeśli tak, to liczba sposobów zwiększa się o jeden.

Mrówka Langtona

Symulacja dla każdego zapytania nie wchodzi w grę, bo żaden procesor w pojedynczej jednostce, na tę chwilę, nie wykona w sekundę tylu operacji dla maksymalnych danych. Nawet dla jednego zapytania maksymalnej wartości n=10^9 klaster SPOJ-a nie da radę w 1 sekundę. Zatem trzeba mrówkę i jej ruchy poddać jakiejś analizie. Zwróćmy uwagę, że prędzej czy później, mrówka zmieniając stany pól, musi dotrzeć do takiego stanu diagramu, w którym już była. Pesymistycznie, biorąc pod uwagę kierunek rozpoczęcia, otrzymujemy, że maksymalnie 4*2^36 ruchów powinno zająć jej dotarcie do takiego stanu. Okazuje się, że dla diagramu 6 x 6 jest to prędzej, bo już po kilku tysiącach ruchów. Taki wynik daje nam symulacja, w której mrówka wybiela nam diagram. Na podstawie tej informacji przeprowadzamy preprocesing, w którym stany diagramu haszujemy w 36-ciu bitach lub zapamiętujemy w statycznej tablicy, po czym na zapytania odpowiadamy w czasie stałym, drukując stan diagramu n%a, gdzie a jest poszukiwaną liczbą ruchów prowadzącą do wyzerowania diagramu.

Najbliższa pierwsza

W tym zadaniu także potrzebny jest preprocesing, którym jest sito Eratostenesa, bo koszt czasowy sprawdzania pierwszości kolejnych liczb naturalnych jest na tyle duży, że nie pozwoli zmieścić się w wyznaczonym czasie. Po utworzeniu, za pomocą sita, tablicy boolowskiej przechowującej informacje o pierwszości liczb, szukamy najbliższej liczby pierwszej inkrementując i dekrementując wartość n. Można pokusić się jeszcze o to, aby na zapytania odpowiadać w czasie stałym, ale nie ma takie potrzeby, ponieważ w przedziale [1-10^7] długość najdłuższego ciągu kolejnych liczb złożonych równy jest 153, a średnia dla losowych danych, to tak na oko chyba mniej niż 20, więc koszt nieduży. Ale nawet dla pesymistycznie dobranych przypadków testowych, szukanie liniowe najbliższej liczby pierwszej, spotka się, ku zadowoleniu rozwiązującego, z akceptacją sędziego. Należało zwrócić uwagę na górny zakres, bezpiecznie jest wykonać sito do 10^+10, jako bufor bezpieczeństwa porównywania odległości górnych wartości.

Soczystość

Należy zauważyć, że do wyznaczenia największej sumy soczystości wystarczy przejść liniowo po ciągu, aktualizując szukaną sumę na bieżąco i wykorzystując do tego celu trzy kolejne wyrazy ciągu. Tzn. dla trzech kolejnych wyrazów ciągu sprawdzamy co się bardziej opłaca: a(i)+a(i-2) czy a(i-1). Wybieramy wartość większą, nadpisujemy w a(i) i przechodzimy do następnego wyrazu postępując tak samo. Rozwiązaniem jest wartość w a(n).

Wartość sumy algebraicznej

Na ten problem jest kilka rozwiązań. Jednym z nich jest ONP (Odwrotna Notacja Polska) - algorytm, którego nie będę tu opisywał, bo jest wiele publikacji na ten temat. Zanim jednak wyrażenie poddamy temu algorytmowi, trzeba zamienić sumę algebraiczną na wyrażenie arytmetyczne. Obliczając wartości jednomianów, otrzymujemy wyrażenie arytmetyczne z dwoma operatorami (+,-) i nawiasy. Dla takiego wyrażenia, algorytm ONP wykorzystuje tylko dwa priorytety na stosie.
Innym rozwiązaniem jest rekurencyjne obliczanie wartości w zagnieżdżonych nawiasach. Za każdym razem, kiedy napotkamy nawias otwierający uruchamiamy funkcję rekurencyjną, której wynik zwracamy w postaci liczby po napotkaniu nawiasu zamykającego. W tym przypadku warto wyrażenie uzupełnić o dodatkowy nawias otwierający na początku i zamykający na końcu tak, aby wynik rekurencji był ostatecznym. Tu także warto zamienić sumę algebraiczną na wyrażenie arytmetyczne, choć takiej potrzeby nie ma. Co kto woli.
Jest jeszcze proste rozwiązanie, z którego można było skorzystać. Jest nim funkcja eval, która dostępna jest w wielu językach, i która oblicza uprzednio przygotowane wyrażenie. Z zadaniem tym można będzie powalczyć na polskim SPOJ-u, ale dla potrzeb nauki zostanie zmniejszony limit czasowy, niepozwalający zmieścić się w czasie zgłoszeniom wykorzystującym tę funkcję.

Górska kraina

Mamy do czynienia ze strukturą drzewa, należy więc znaleźć najdłuższą ścieżkę. Drzewo to szczególny graf, wystarczy, że za pomocą algorytmu przeszukiwania w głąb lub wszerz znajdziemy najbardziej odległy liść od dowolnego losowego wierzchołka, po czym ponownie uruchamiamy DFS lub BFS z wyznaczonego poprzednio wierzchołka. Tym razem otrzymamy najdłuższą ścieżkę w drzewie.