Runda 30 - omówienie zadań

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

Runda 30 - omówienie zadań

Postautor: witman » 07 lis 2016, 13:58

1. Anagramy
To czy dwa wyrazy są anagramami można stwierdzić porównując liczbę wystąpień każdej litery. W obu wyrazach dla każdej litery ta liczba musi być taka sama.
Przy tak małej ilości danych jaka jest w zadaniu dobra jest też druga metoda - posortować ciągi liter tworzące wyrazy i porównać je.

2. Enigma w wersji light po raz piąty
Prosty szyfr przestawieniowy. Nie podam rozwiązania :)

3. Sklejanie liczb
Dla każdego przypadku testowego można algorytmem O(log n) obliczyć potrzebną sumę cyfr, np. zliczając ile we wszystkich liczbach jest cyfr jedności, dwójek, czwórek itd.
Można też skorzystać ze wzoru podanego w encyklopedii ciągów: https://oeis.org/A083652

4. ITPW
Wygrywająca strategia wynika z twierdzenia Sprague'a-Grundy'ego i polega na obliczeniu nim-sumy wszystkich liczb, a następnie znalezieniu stosu, który można tak zmniejszyć, aby nim-suma wynosiła 0 (jeśli to możliwe). W obliczeniach kluczowe jest zastosowanie operacji xor (alternatywa wykluczająca).

5. Podróż do stolicy
Rozwiązanie tego zadania wymaga zastosowania znanego algorytmu znajdowania najniższego wspólnego przodka w drzewie. Można wykorzystać np. algorytm opisany na Wikipedii bazujący na DFSie i wyszukiwaniu binarnym lub algorytm Tarjana opierający się na strukturze zbiorów rozłącznych.

6. Pomiary meteorologiczne 3
Do znalezienia poszukiwanej wartości można zastosować wstępnie programowanie dynamiczne. Jeśli mamy znalezioną wartość dla pewnej długości okresu d, to możemy znaleźć ją dla d+1, obliczając jedynie różnice pomiędzy pomiarami odległymi o d i wybierając maksimum. Tak przygotowane wstępnie wartości pozwalają później odpowiadać na zapytania w czasie stałym. Dostajemy więc rozwiązanie .
Można też wykorzystać algorytm opisany tutaj, który wykorzystuje kolejkę dwustronną i ma złożoność dla jednego zapytania.
Próby rozwiązania zadania z użyciem drzewa przedziałowego kończyły się komunikatem TLE.

7. Taksówka na Manhattanie 7
Rozwiązaniem jest tu wyznaczenie (za pomocą programowania dynamicznego) wartości liczb Delannoya.

8. Escape cube
Rozwiązanie tego najtrudniejszego w rundzie zadania, bazuje na przedstawieniu sześcianu jako grafu, który musimy wielokrotnie przeszukiwać stosując np. DFS.
Na początku zbieramy informacje z liczb oznaczających pokój startowy i pokoje sąsiednie na temat "bezpiecznych reszt". Możemy wtedy przejść przez wszystkie pokoje oznaczone liczbami dającymi tylko takie bezpieczne reszty. Jeśli w czasie takiego przeszukiwania trafimy na liczbę, która daje jakąś resztę, o której nie wiemy czy jest bezpieczna, ale wiemy (z wcześniejszych odwiedzin), że pokój po drugiej stronie przejścia jest bezpieczny, to taka reszta jest na pewno resztą bezpieczną. W tym momencie można przeszukiwanie zacząć od nowa, bo będzie więcej pokojów, do których możemy bezpiecznie wejść. Po pewnym czasie pozostanie tylko jedna reszta, którą nie był oznaczony żaden odwiedzony pokój - ta reszta oznacza pokoje z pułapkami.
witman
Koordynator AlgoLigi
 
Posty: 78
Rejestracja: 10 kwie 2013, 21:03

Re: Runda 30 - omówienie zadań

Postautor: narbej » 10 lis 2016, 11:13

Jesteś wielkiWitold ogromne gratulacje i podziękowania, za wspaniałą rundę!

7. Taksówka na Manhattanie 7
Czy naprawdę chodzi tu o wartości liczb Delannoya?

[EDIT]
Tak, zmyliła mnie intepretacja graficzna na stronie wikipedi - ilość różnych ścieżek od punktu SW do NE

6. Pomiary meteorologiczne 3
Czy z podpowiedzi wynika, że mamy albo:
O(n^2+q) albo q*O(n) == O(n*q) ?
Jeżeli wzorcówka [i moje rozwiązanie] jest tej klasy [>1sek] to są też dużo lepsze rozwiązania [<0.1 sek].

Mam oczywiście pomysł [małej?] optymalizacji, ale opiszę dopiero gdy ją ewentualnie pozytywnie zastosuję.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 30 - omówienie zadań

Postautor: narbej » 11 lis 2016, 10:47

Witold nie zmieniam zdania, nadal uważam, że jesteś wielki, naprawdę ;-)

Ale teraz mam takie pytanie. Skoro liczby Delannoya mogą dodatkowo być interpretowane w taki sposób jak w twoim zadaniu, więc spokojnie możnaby ich użyć także do rozwiązania zadania: http://pl.spoj.com/problems/AL_12_02/ ? A przecież tam wychodzą inne wartości już dla promienia 3 = 29 a liczby Delannoya [3 2] = [2 3] = 25
Czy jestem w błędzie i się mylę?
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 30 - omówienie zadań

Postautor: witman » 11 lis 2016, 11:10

Dziękuję za docenienie.

narbej pisze:6. Pomiary meteorologiczne 3
Czy z podpowiedzi wynika, że mamy albo:
O(n^2+q) albo q*O(n) == O(n*q) ?
Jeżeli wzorcówka [i moje rozwiązanie] jest tej klasy [>1sek] to są też dużo lepsze rozwiązania [<0.1 sek].

Mam oczywiście pomysł [małej?] optymalizacji, ale opiszę dopiero gdy ją ewentualnie pozytywnie zastosuję.


Ja miałem wzorcówkę O(qn), więc wg tego dobrałem limity, tak aby nie przechodziły drzewa przedziałowe. Na konkursie niektóre osoby zrobiły O(n^2+q) i One mają dużo lepsze czasy niż ja.

Ale teraz mam takie pytanie. Skoro liczby Delannoya mogą dodatkowo być interpretowane w taki sposób jak w twoim zadaniu, więc spokojnie możnaby ich użyć także do rozwiązania zadania: http://pl.spoj.com/problems/AL_12_02/ ? A przecież tam wychodzą inne wartości już dla promienia 3 = 29 a liczby Delannoya [3 2] = [2 3] = 25
Czy jestem w błędzie i się mylę?


No niestety mylisz się :cry:. W tamtym zadaniu jest metryka euklidesowa. Punkty w zasięgu taksówki w dwóch wymiarach trzeba liczyć w metryce miejskiej (Manhattan). Tu jest odpowiedni rysunek: https://en.wikipedia.org/wiki/Centered_square_number
witman
Koordynator AlgoLigi
 
Posty: 78
Rejestracja: 10 kwie 2013, 21:03

Re: Runda 30 - omówienie zadań

Postautor: narbej » 11 lis 2016, 14:35

Niestety, nikt nie jest nieomylny, ale nie wierzyłem [coś sobie ubzdurałem], że to Ty się nie pomyliłeś. Jestem człowiekiem małej wiary ;-)
Dzięki za wyjaśnienia.
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51


Wróć do Zadania

Kto jest online

Użytkownicy przeglądający to forum: Google [Bot] i 2 gości

cron