Runda 26 - omówienie zadań

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

Runda 26 - omówienie zadań

Postautor: kaspro » 27 gru 2015, 18:41

kaspro
Koordynator AlgoLigi
 
Posty: 69
Rejestracja: 13 kwie 2013, 21:01

Re: Runda 26 - omówienie zadań

Postautor: mario » 27 gru 2015, 21:07

Powierzchnia prostokąta

Dla nieparzystego n nie istnieje prostokąt o całkowitych bokach, w pozostałych przypadkach, poza jednym wyjątkiem, maksymalizujemy wartość funkcji
kwadratowej połowy długości obwodu. Rozwiązaniem jest n/=2; n/2*(n-n/2)

************

Nie do pary

Ponieważ wąskim gardłem na sprawdzarce jest wczytywanie danych, więc rozwiązań jest tu kilka. Ale najprostszym i zarazem właściwym rozwiązaniem, jest wykorzystanie operacji bitowych na liczbach, tzn. należało zauważyć, że XOR dwóch takich samych liczb równy jest 0. Złożoność takiego podejścia jest liniowa.

************

Alfabet

Niech alfabet składa się n liter. W każdym słowie nad tym alfabetem mogą wystąpić co najwyżej 3 takie same litery, dlatego długość słowa będzie równa co najwyżej 3n. Rozważmy dwie litery a, b oraz podciąg najdłuższego słowa zawierający tylko a i b. Bez straty ogólności niech pierwsze wystąpienie a poprzedza b, wówczas istnieją tylko dwie możliwe sekwencje aaabbb i aababb, gdzie jedna powstaje przez zamianę środkowych liter drugiej.<br />Rozważmy teraz najdłuższe słowo nad alfabetem złożonym z n uporządkowanych liter. Dla każdej pary kolejnych liter można dokonać zamiany lub nie, co daje nam 2^(n-1) możliwości. Ponieważ istnieje n! uporządkowań liter, mamy w sumie 2^(n-1) * n! najdłuższych słów.

Ponieważ zapytań w zadaniu jest dużo, należy przygotować odpowiedzi dla całego zakresu tak, aby na zapytanie odpowiadać w czasie stałym. W innym przypadku zabraknie czasu na wykonanie się programu.

************

Pole minowe

W tym zadaniu potrzeba i wystarcza uruchomić przeszukiwanie wszerz i za każdym razem zjadać jeden napotkany poziom sektorów z minami. Potrzebujemy jeszcze dodatkowej kolejki, która będzie przechowywała nam pozycje brzegowe tego przeszukiwania tak, aby nie rozpoczynać za każdym razem z punktu A, bo nie zmieścimy się w wyznaczonym czasie. Niestety, z uwagi na duży rozmiar diagramu, przeszukiwanie w głąb zakończy się komunikatem SIGSEGV. Oczywiście przeszukiwanie realizujemy za pomocą Flood fill.

************

KOD

Do realizacji tego zadania potrzebna jest rekurencja z powrotami. Z uwagi na własności tworzonych permutacji, rekurencja wykonuje się szybko, bo różnice
między sąsiednimi wyrazami są nieduże. Oczywiście dla przedziałów, w których liczba wyrazów jest nieparzysta, nie należy wchodzić w rekurencję, bo wówczas wykonywać się ona będzie po wszystkich wyrazach, a to skończy się przekroczeniem limitu czasu. Przedziały, w których liczba wyrazów jest parzysta,
a mimo wszystko nie istnieje permutacja, są to przedziały niewielkie, maksymalnie kilkunastowyrazowe i tu też nie ma problemu.

************

Permutacja

Wypisując permutacje [1,n], dla parzystego n, zauważamy, że od pewnego n, ciągi mają podobne cechy i tylko niewielki sufiks jest zmienny.
Na podstawie tej obserwacji łatwo wydrukować niemal cały ciąg niemalże liniowo. Ostatnie wyrazy można wyszukać lekko zmodyfikowanym algorytmem z zadania KOD, lub też wyszukać go na własnej maszynie i wkleić go do kodu, by go później wypisać jako sufiks.

************

Saper

To zadanie jest na tyle złożone, nie da się tu coś mądrego napisać w dwóch zdaniach. Ogólnie problem jest NP-trudny, ale dla podanych rozmiarów możliwy
do zrealizowania w podanych limitach czasowych, a dla losowych danych, tak jak to w przypadku gry systemowej, nieszczególnie trudne. Zadanie pojawi się na polskim SPOJ-u jako zadanie, w którym będzie dostęp do wyników poszczególnych testów.

************
mario
Koordynator AlgoLigi
 
Posty: 59
Rejestracja: 10 kwie 2013, 21:21

Re: Runda 26 - omówienie zadań

Postautor: pm12 » 27 gru 2015, 21:43

W zadaniu "Pole minowe" nie mogę zrozumieć, w jaki sposób uda się to zadanie zrobić BFS-em (próbowałem użyć algorytmu Dijkstry, ale miałem TLE).
pm12
 
Posty: 3
Rejestracja: 09 lip 2015, 13:53

Re: Runda 26 - omówienie zadań

Postautor: narbej » 27 gru 2015, 22:22

Gratulacje, super, brawo!


PS
@pm12
flood fill
narbej
Koordynator AlgoLigi
 
Posty: 169
Rejestracja: 07 kwie 2013, 14:51

Re: Runda 26 - omówienie zadań

Postautor: mario » 27 gru 2015, 22:24

To może przykład, startujemy z A i z każdym uruchomieniem BFS poruszamy się po kropkach zjadając jeden poziom iksów. To jest bardzo szybkie, szybsze od Dijkstry.

Kod: Zaznacz cały
xxxxxxxxx
xxxxxxxxx
xxxxxxxxx
xxxx.xxxx
xxxxAxxxx
xxxxxxxxx
xxxxxx.xx
xxxxxxxxx
xxxxxxxxB

1 krok
xxxxxxxxx
xxxxxxxxx
xxxx.xxxx
xxx.o.xxx
xxx.A.xxx
xxxx.xxxx
xxxxxx.xx
xxxxxxxxx
xxxxxxxxB

2 krok
xxxxxxxxx
xxxx.xxxx
xxx.o.xxx
xx.ooo.xx
xx.oAo.xx
xxx.o.xxx
xxxx.x.xx
xxxxxxxxx
xxxxxxxxB

3 krok
xxxx.xxxx
xxx.o.xxx
xx.ooo.xx
x.ooooo.x
x.ooAoo.x
xx.ooo.xx
xxx.o..xx
xxxx.xxxx
xxxxxxxxB

4 krok
xxx.o.xxx
xx.ooo.xx
x.ooooo.x
.ooooooo.
.oooAooo.
x.ooooo.x
xx.oooo.x
xxx.o..xx
xxxx.xxxB

5 krok
xx.ooo.xx
x.ooooo.x
.ooooooo.
ooooooooo
ooooAoooo
.ooooooo.
x.oooooo.
xx.oooo.x
xxx.oo.xB

6 krok
x.ooooo.x
.ooooooo.
ooooooooo
ooooooooo
ooooAoooo
ooooooooo
.oooooooo
x.oooooo.
xx.oooo.B

mario
Koordynator AlgoLigi
 
Posty: 59
Rejestracja: 10 kwie 2013, 21:21


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