Runda 27 - omówienie zadań

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

Runda 27 - omówienie zadań

Postautor: witman » 02 maja 2016, 08:44

1. W poszukiwaniu palindromów
Należy zauważyć, że trzyliterowy palindrom można utworzyć, jeśli jakaś litera występuje w co najmniej dwóch wyrazach. W przeciwnym wypadku nie da się stworzyć palindromu w sposób opisany w zadaniu.

2. Enigma w wersji light po raz czwarty
Zadanie, choć łamigłówka, okazało się najłatwiejsze dla zawodników. Niech więc łamigłówką zostanie ;)

3. Ukryty skarb
Do rozwiązania zadania należy zastosować klasyczny algorytm wyszukiwania binarnego. Tyle tylko, że to wyszukiwanie trzeba prowadzić jednocześnie w dwóch wymiarach.

4. Najcenniejsza ścieżka
Tu należy zastosować programowanie dynamiczne. Trudnością implementacyjną okazuje się odpowiednie odwzorowanie heksagonalnej planszy. Można wykorzystać do tego część dwuwymiarowej tablicy o wymiarach [2n-1][2n-1].

5. Taksówka na Manhattanie 6
Potrzebna wiedza: liczby kwadratowe wycentrowane, liczby trójkątne.
Gdyby nie to, że obszar, po którym porusza się taksówkarz jest ograniczony, to przy rosnącej odległości k liczba skrzyżowań w zasięgu tworzyłaby ciąg: 1, 5, 13, 25, 41,... (OEIS:A001844). Od tak wyznaczonej liczby należy odjąć skrzyżowania, które nie mieszczą się w dopuszczalnym obszarze (tu pojawiają się kwadraty liczb naturalnych). Trzeba jednak uważać, aby nie odjąć dwa razy tych samych skrzyżowań (liczby trójkątne). IMHO, dobry rysunek wart jest tysiąca słów.

6. Pomiary meteorologiczne
Potrzebna wiedza:współrzędne kartezjańskie i biegunowe, średnia arytmetyczna.
Zadanie sprawiło nadspodziewanie dużo trudności, tym którzy próbowali je rozwiązać (których to osób było jedynie kilka). Wystarczy jednak zwykła zamiana pomiędzy współrzędnymi biegunowymi i kartezjańskimi, przy wczytywaniu współrzędnych stacji, a odwrotnie przy wypisywaniu wyniku. Dodatkowym utrudnieniem była zapewne nadmiarowa informacja w postaci współczynników A, B i C pojawiających się we wzorach. Do znalezienia rozwiązania nie są one potrzebne. Należy zauważyć, że potrzebujemy znaleźć taki punkt, aby suma kwadratów odległości wszystkich stacji od niego była minimalna. Taką cechę ma średnia arytmetyczna.

7. Trzeci ogród króla
Potrzebna wiedza: programowanie dynamiczne, centralne liczby Delannoya, wyznaczanie odwrotności modulo.
Gdyby nie fontanna w środku ogrodu, wystarczyłoby (stosując programowanie dynamiczne) wyznaczyć wartość (N-1)-szej liczby Delannoya (wzór na OEIS: A001850). Aby uzyskać rozwiązanie należy zauważyć, że liczba możliwości ubywających z powodu fontanny, to podniesiona do kwadratu liczba Delannoya wyznaczona dla dwa razy (uwaga na parzystość/nieparzystość N) mniejszego ogrodu.
Ponieważ we wzorze występuje dzielenie, potrzeba wyznaczać odwrotność modulo 1000000007, do czego wykorzystać można np. rozszerzony algorytm Euklidesa.

8. Paintball
Potrzebna wiedza: algorytmy geometryczne.
"Brutalna" symulacja. Dla każdego gracza trzeba wyznaczyć listę potencjalnych celów, sprawdzając dla każdego z przeciwników czy nie jest zasłonięty przez żadną ze ścian ani innych zawodników. Dodatkowo należy mieć na uwadze, że taka lista będzie się dynamicznie zmieniać, bo wyeliminowanie jakiegoś zawodnika może odsłonić innego.
Aby poprawnie wyznaczyć potrzebne informacje, należy użyć klasycznych algorytmów geometrycznych: przynależność punktu do odcinka i przecinanie się odcinków.

9. System opłat drogowych
Potrzebna wiedza: struktura zbiorów rozłącznych lub DFS, szybkie potęgowanie modularne.
Jak się okazało - najtrudniejsze zadanie.
Po pierwsze należy zauważyć, że to, jak połączone są miasta, nie ma znaczenia. Ważne jest tylko, że system dróg tworzy drzewo.
Wprowadźmy funkcję F(A,B) oznaczającą, czy suma opłat za przejazd z miasta A do miasta B ma być parzysta (F=0) czy nieparzysta (F=1). Można zauważyć, że jeśli mamy regułę określające F(A,B) i F(B,C) to wynika zależna od nich reguła dla miast A i C: F(A,C)=F(A,B) xor F(B,C). Na podstawie wszystkich podanych warunków możemy zbudować drzewo (a może las), który następnie analizujemy stosując np. DFS. Musimy wykryć, czy każdy warunek jest zgodny z tym co wynika z innych warunków. W przeciwnej sytuacji wynikiem będzie 0. Można do takiej analizy wykorzystać też strukturę zbiorów rozłącznych i już w czasie budowy tego drzewa (lasu) sprawdzać zgodność warunków.
Jeśli nie ma sprzeczności, możemy obliczyć liczbę taryf.
Dla każdej spójnej składowej grafu zbudowanego z warunków, wyznaczamy liczbę krawędzi i sumujemy je. Ta suma S to liczba niezależnych od siebie warunków, więc dla tylu dróg trzeba wyznaczyć opłatę parzystą lub nieparzystą. Dla pozostałych N-1-S dróg można wyznaczyć dowolną (<= M) opłatę. Szukana wartość to

10. Pomiary meteorologiczne 2
Potrzebna wiedza: Drzewo przedziałowe.
Aby odpowiednio szybko aktualizować dane pomiarowe oraz generować raporty, należy zbudować dwuwymiarowe drzewo przedziałowe, w którym będziemy przechowywać informacje o maksymalnej, minimalnej i sumarycznej temperaturze oraz liczbie stacji, które dokonały pomiaru.
witman
Koordynator AlgoLigi
 
Posty: 78
Rejestracja: 10 kwie 2013, 21:03

Re: Runda 27 - omówienie zadań

Postautor: spectral_ » 02 maja 2016, 17:28

Zadania z biegunowym układem współrzędnych były przyjemną nowością. Ogólnie - jakość zadań Witolda jak zwykle na bardzo wysokim poziomie, jestem pod wrażeniem:)
spectral_
Organizator AlgoLigi
 
Posty: 18
Rejestracja: 15 lip 2014, 15:27

Re: Runda 27 - omówienie zadań

Postautor: Crucian » 03 maja 2016, 15:16

Mimo, że byłem testerem, nie uczestnikiem w tej rundzie to mi największą przyjemność sprawiło zadanie System opłat drogowych. Mimo, że najtrudniejsze, to prawie najłatwiejsze jeśli chodzi o implementację 8-)
Awatar użytkownika
Crucian
Organizator AlgoLigi
 
Posty: 37
Rejestracja: 07 sie 2014, 10:07


Wróć do Zadania

Kto jest online

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

cron