MOKIP 24 stycznia 2013

Omówienie zadań z MOKIP Contestu

1. Minimalna liczba

Sposobów jest wiele. Tak czy siak warto psortować zbiór liczb. Potem można albo sprawdzać kolejne wielokrotności k czy są w zbiorze (funkcja STL binary_search lub po swojemu, tylko nie setem!) - to daje O(n log n), albo przechodzić po kolejnych elementach i sprawdzać, czy najmniejsza wielokrotność k większa od danej liczby nie jest nastepną liczbą w zbiorze O(sort + n) lepsze od O(n log n) - tak jest w moim kodzie.

2. Bug

Modyfikujemy Dijkstrę. Dla każdego wierzchołka zapamiętujemy długość najkrótszej ścieżki parzystej i nieparzystej. Warto pamiętać, że nieparzysta odległość źródła od źródła nie moze być róna 0! Przebieg algorytmu normalnie - tylko dla każdej krawędzi sprawdzamy, czy nie polepsza parzystej lub nieparzystej odległości (trzeba dodać wagę do dp[x] i dnp[x] i obie wartości sprawdzić). Parzyste i nieparzyste odległości zostaną poprawnie wyznaczone.
Prawdopodobnie działa to także dla przypadku, gdy długość ścieżki musi spełniać inny warunek niż parzystość (np. być podzielna przez 7 - wtedy chyba też wystarczą tylko dwie tablice, a już na pewno 7), ale nie znam dowodu.

3. Szezlongi

Okazuje się, że "genialne" Szezlongi to zadanie niemal identyczne jak Domki z dawnego MOKIP contestu.

1. Rozwiązanie uniwersalne, które warto przemyśleć:
Do kolejki BFS wrzucamy wszystkie liście (wyróżnione wierzchołki). Odpalamy BFS. Dla każdego nowoodwiedzonego wierzchołka zapamiętujemy liść (źródło), z którego do niego doszliśmy. Jeśli przyjdzie nam odwiedzić powtórnie wierzchołek do którego dotarliśmy już z innego liścia, oznacza to, że liść-przodek aktualnego wierzchołka i następnego są najbliższymi liścmi w grafie.
Jest to przykład wykorzystania falowej natury BFS.

2. Rozwiązanie wzorcowe, działające tylko dla drzew:
Tym razem używamy DFS. Zaczynamy od dowolnie wybranego liścia, aby miał dokładnie jedno poddrzewo. Przy powracaniu do przodka przekazujemy mu informację o dwóch najbliższych liściach (taką informację pamiętamy dla każdego wierzchołka) i aktualizujemy tę informację (w przodku). Po zgromadzeniu informacji o najbliższych liściach sprawdzamy odległości między tymi parami liści, a także odległości liści od korzenia i wyznaczamy rozwiązanie.

4. Tasowanie

Rozwiązanie jest harde i mało przydatne na przyszłość. Wykorzystuje fakt, że składanie parmutacji zachowuje się jak potęgowanie.
1. Za pomoca czegoś podobnego do DFS dzielimy permutację na cykle (taktujemy ją jak graf skierowany) i grupujemy cykle jednakowej długości (ja nie pogrupowałem i dostałem 20, bo było za wolno)
2. Dla każdej grupy równych cykli wyznaczmy doświadczalnie (sprawdzamy kolejne i w czasie O(l)) rozwiązanie równania: (1+T*i)%l==0, gdzie T to dlugość cyklu.
3. Podnosimy wszystkie cykle do potęgi k=(1+T*i)/l, czyli dla każdego elementu grupy znajdujemy element oddalony o k na cyklu.
4. Koniec.
Można też poczytać o tym zadaniu (ale jest to jeszcze trudniejsze) w Niebieskiej Książeczce z X OI.