SymetriaNa początek warto rozpisać sobie kilka przypadków dla małych wartości
m i zobaczyć jak wyglądają binarne liczby symetryczne i jakie jest górne ograniczenie na
n dla poszczególnych
m. Eleganckie rozwiązanie problemu zapewniają operatory bitowe, ponieważ samą odpowiedź można zbudować właśnie na podstawie bitowej reprezentacji liczby
n.
Oczekiwana złożoność:
Planowanie oesówZadanie okazało się dość kontrowersyjne (być może mogłem je troszkę lepiej sformułować, ale to poddaję Waszej ocenie), gdyż tylko jedna osoba odkryła już przy pierwszym zgłoszeniu pułapkę czyhającą w treści, ale z powodu błędu technicznego nie zaliczyła tego zadania (cóż za ironia losu...). Oto bardzo szczegółowe omówienie, aby nie było żadnych wątpliwości:
Z treści zadania wiemy, że:
- mamy do czynienia ze spójnym nieważonym grafem nieskierowanym
-
a!=
b, czyli punkt startu nie może być jednocześnie metą
- jeśli jakiś punkt jest startem lub metą, to nie może być punktem pośrednim (albo... albo... albo); innymi słowy ze startu wychodzimy raz i już tam nie wracamy, do mety wchodzimy tylko raz na końcu oesu
- punkty pośrednie na trasie mogą się powtarzać pomiędzy startem i metą, tzn. możemy przejechać więcej niż jeden raz przez dowolny wierzchołek będący punktem -pośrednim
-
k jest maksymalną liczbą krawędzi jakie możemy przebyć na trasie, zatem oes to po prostu ścieżka od
a do
b w której przechodzimy 1, 2, 3... lub
k krawędzi.
Ogólnie mogą wystąpić 3 sytuacje:
- ograniczenie na
k jest za bardzo restrykcyjne i nie da się przejechać z
a do
b używając co najwyżej
k krawędzi, wtedy wypisujemy wszystkie wierzchołki grafu
-
k jest tak duże, że każdy wierzchołek ma fizyczną szansę znaleźć się w trasie z
a do
b-
k jest tak dobrane, że możemy wykreślić część wierzchołków z grafu, bo niezależnie jak będziemy kombinować z trasą nie możemy skorzystać z tych wierzchołków, właśnie te wierzchołki należy wypisać wtedy na wyjście.
Należy każde zapytanie obliczać osobno i podawać wyniki. Algorytm wzorcowy opiera się na trzech przejściach BFS przez dany graf dla każdego zapytania.
W pierwszym przejściu sprawdzamy minimalną odległość z
a do
b. Jeśli jest ona mniejsza/równa
k to wiemy, że należy badać sytuację dalej, w przeciwnym wypadku wypisujemy wszystkie wierzchołki.
W drugim przejściu puszczamy BFS z
a, ale przed tym faktem zaznaczamy, że odwiedziliśmy
b. Czyli przechodzimy przez graf omijając
b. W czasie przechodzenia obliczamy minimalne odległości z
a do wszystkich wierzchołków, do których weszliśmy.
W trzecim przejściu puszczamy BFS z
b, ale przed tym faktem zaznaczamy, że odwiedziliśmy
a.
Czyli przechodzimy przez graf omijając
a. W czasie przechodzenia obliczamy minimalne odległości z
b do wszystkich wierzchołków, do których weszliśmy.
Teraz sumujemy minimalne odległości dla każdego wierzchołka obliczone w 2 i 3 BFSie. Czyli np. jeśli do jakiegoś wierzchołka
v minimalna odległość od
a wynosi 2, a minimalna odległość od
b wynosi 5, to obliczamy 2+5 = 7. Jeśli 7<=
k to wiadomo, że wierzchołek ten może być użyty do wyznaczenia oesu. Należy też uważać na to, że w czasie 2 i 3 przejścia BFS może zdarzyć się tak, że nie wejdziemy do jakiegoś wierzchołka, pomimo tego, że cały graf jest spójny. Wtedy oczywiście taki wierzchołek automatycznie jest skreślony z listy i należy go wypisać.
Oczekiwana złożoność:
Wyznacz promień 2Zadanie można rozwiązać na co najmniej 2 sposoby:
1) rozwiązując układ równań liniowych z wykorzystaniem Twierdznia Cramera; jeśli dobrano poprawnie zestawy danych testowych, to wyznacznik jest zawsze niezerowy;
2) nie znamy rachunku macierzy, wiec rozwiązujemy siłowo, tj. wyznaczamy jakąś zmienną z jedego równania i wstawiamy do pozostałych, aż do skutku. Ten sposób może prowadzić do dzielenia przez 0 w niektórych przypadkach, ale jeśli zawsze można znaleźć rozwiązanie to wystarczy permutować kolejność punktów z wejścia aż do skutku: maksymalnie 24 kombinacje.
Wynik należy zaokrąglić do dwóch miejsc po przecinku. Wykorzystujemy zaokrąglenie do najbliższej wartości.
Oczekiwana złożoność:
Lista kolejkowaIstnieją dwie drogi prowadzące do akceptowalnego rozwiązania. Pierwsza, trudniejsza, to jak sugeruje treść, należy wymyślić algorytm obsługujący zapytania w trybie online, czyli równolegle do danych wejściowych (bierzemy kolejne dane z wejścia, patrzymy co trzeba zrobić, obliczamy i wypisujemy odpowiedź itd.). Jest to niewątpliwe wyzwanie algorytmiczne i napisanie takiego zgłoszenia świadczy o wysokich umiejętnościach programistycznych. Ale możemy wykazać się odrobiną sprytu i spróbować całkowicie innego podejścia – offline. Nikt nam nie zabrania wczytać całego wejścia, a dopiero potem kombinować nad odpowiedziami. I ten sposób okazuje się o wiele łatwiejszy w implementacji, gdyż cały problem możemy oprzeć o dość dobrze znane drzewo przedziałowe. Wystarczy skonstruoować odpowiednie funkcje do obsługi każdego rodzaju zapytań.
Oczekiwana złożoność: Obsługa zapytań w czasie ~logarytmicznym względem danych wejściowych.
ZakupyZadanie, którym chciałem zwrócić uwagę na dość mało znany algorytm, ale godny uwagi i warty zapamiętania. Wszystko znajdziecie w Internecie, rzucę tylko hasłem – metoda węgierska.