Runda 24 - omówienie zadań

[Crucian]

Koty
Trójkąty
Nowy komputer
Podsłowa, podsłowa wszędzie!
Gęstość w drzewie
Robot

[spectral_]

Symetria
Na 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ów
Zadanie 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ń 2
Zadanie 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 kolejkowa
Istnieją 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.


Zakupy
Zadanie, 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.

[znirzejskwarka]

Do listy spokojnie wchodziło O(n sqrt n)

[narbej]

Panowie gratuluję udanej rundy i wspaniałych zadań. Brawo.

Planowanie oes'ów.
Poległem na trym zadaniu i poddałem się - pojechałem na działkę po jabłka, ogórki, maliny i borówki kanadyjskie, a wróciłem chwilę po zamknięciu oesów.
Przyjąłem, że skoro przez punkty pośrednie można przejeźdżać i zawracać w nich, to można to robić również w punktach startu czy mety. Dodatkowo utwierdził mnie w tym przykład w treści zadania. Są dwie drogi o długości 6 odcinków, ale zauważyłem to dopiero teraz. Wcześniej widziałem tylko jedną drogę, może zrobiłem za mało staranny szkic odręczny, zamiast graphvizem?:
6-5-1-2-0-2-1
ta druga to oczywiście:
6-4-3-2-0-2-1

Może warto dobrać bardziej wyrazisty i bezkonfliktowy przykład do zadania?
Może warto napisać wprost, aby nie było wątpliwości, że start i metę odwiedzamy tylko raz?
A może zostawić jak jest?
Zadanie polega na chytrym [2x] zastosowaniu algorytmu grafowego więc czy warto dodatkowo je utrudniać?
A przy planowaniu oesu, gdy trasa jest zamknięta, to powtórny przejazd przez tą samą miejscowość [nie koniecznie linię mety/startu] nie byłby atrakcją?
Nie wiem, bo nigdy nie brałem udziału.

pozdrawiam i jeszcze raz gratulacje!

[spectral_]

Do listy spokojnie wchodziło O(n sqrt n)

Tak, to prawda, limit czasowy w tym zadaniu okazał się zbyt łagodny. A szkoda, bo wymyślenie rozwiązania z drzewem daję niewątpliwie większą frajdę

Może warto dobrać bardziej wyrazisty i bezkonfliktowy przykład do zadania?

To chyba najlepsze wyjście.

Zadanie polega na chytrym [2x] zastosowaniu algorytmu grafowego więc czy warto dodatkowo je utrudniać?

Bardziej niż o grafy, chodziło mi w tym zadaniu o wyciągnięcie z treści maksimum informacji. Winy należy upatrywać w słabej treści, która nie dawała precyzyjnego opisu zadania, chociaż wydawało mi się, że tak jest. Kierowałem się tym, że jeśli coś jest albo a albo b albo c, to zgodnie z logiką nie może być a i b, lub a i c lub b i c jednocześnie. Wiedząc, że meta nie może być punktem pośrednim, podczas dobierania punktów pośrednich nie powinniśmy jej uwzględniać, ponieważ najpierw wybieramy start i metę, a potem punkty pośrednie. Skoro punkt kontrolny jest metą to już nie może być punktem pośrednim - wydobycie z treści takiej informacji miało być haczykiem w tym zadaniu. Ale chyba nie do końca wyszło tak jak chciałem.

[narbej]

Przejazd [powtórny] przez metę/start może i byłby ztrakcyjny z punku widzenia organizatorów, ale z punktu widzenia .. stopnia trudności zadania szalenie uprościł by je.

- k jest tak duże, że każdy wierzchołek ma fizyczną szansę znaleźć się w trasie z a do b

Wtedy wystarczyłoby sprawdzić, czy k>= n-1 i jeżeli graf jest spójny [ale to też nie wynika z treści?], to wszystkie punkty byłyby ok i byłoby za łatwo

[znirzejskwarka]

Co do zadania Robot, to wymyśliliśmy z Mateuszem Puczelem całkiem proste rozwiązanie o złożoności O(n^3) które przechodzi w czasie 0.00
Wystarczy zauważyć że programowanie dynamiczne dla jednego wymiaru można zrobić w czasie n^3, tak że stanem będzie (liczba wykonanych ruchów, szerokość odkrytych już pól, pozycja z odkrytych pól na której się znajdujemy)

I gratuluję dobrej rundy z ciekawymi zadaniami

[Crucian]

Gratulacje znalezienia lepszego rozwiązania.
Wrzuciłem tu zadanie Robot z większymi wymaganiami wymagające właśnie złożoności O(n³).

[narbej]

Planowanie oes'ów.
Można i wystarcz wykonać tylko dwa BFS. Wszystkie trzy przypadki sprowadzają się tak naprawdę do jednego, albo są punkty do wyrzucenia, łącznie z metą, bo start jest zawsze potencjalnie ok, albo nie ma takich pkt.
Czy kogokolwiet to interesuje!?

Użyłem [lekko/mocno] modyfikowanych BFS, a szczególnie drugi - jest inny niż pierwszy. Drugi od razu wykorzystuje to co zostawił pierwszy, a nie na koniec porównywanie czasów z obu BFS.

Pomyśl, czy gdyby zadanie polegało na znalezieniu punktów ok, a nie na odrzucaniu pkt bee [złych], to czy nie byłoby łatwiej? Jeżeli tak, to odwrócenie sytuacji dopiero potem jest też już później łatwe.

Zaliczyłem zadanie [na razie najlepszy czas] ale teraz widzę, że można je zrobić jeszcze ciut lepiej. [może kiedyś poprawię]
No i niestety, aby się zbliżyć do najlepszego czasu, użyłem fast +i/-o ;-(

[narbej]

Nowy komputer

Muszę stwierdzić, że bardzo pomogła mi podpowiedź Crucjana, o ilości różnych liczb. Natomiast opis obliczania sumy:
w podzpowiedzi jest dla mnie niezrozumiały i dlatego zrobiłem to inaczej.
Wpiszmy do wolframalpha http://www.wolframalpha.com:

sum j=1 to n x^j

Prawie natychmiast uzyskujemy odpowiedź [ładniej zapisaną, bo ja nie znam na tyle tex'a]:

Jeżeli będziemy szybko potęgować modularnie, to nie możemy wyniku "normalnie" dzielić. Dzielenie musimy zastąpić mnożeniem przez odwrotność. Dobry opis, jak to zrobić, jest na przykład na blogu kokoska, przy zadaniu o trzech królach.