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.
