Temat: Tapczany

Ma ktoś już coś na tapczany?
Piszę tutaj bo nie ma odpowiedniego wątku na forum jeszcze.
Strasznie trudne jest, więc warte tych punktów.
Słyszałem, że za tapczany jest w tym.roku awans do finału
Za wzorcówke przeskakuje się drugi etap, a jeśli nie ma sety to dolicza się punkty.
Link do zadania :
https://sio2.mimuw.edu.pl/c/oi22-1/p/tap/
Tapczany nie takie trudne jak się wydaje na pierwszy rzut oka...
Wystarczy ODPOWIEDNIO coś zrobić ;)
[spoiler]
Ej, ale czy to zadanie nie redukuje się przypadkiem do problemu minimalnego pokrycia wierzchołkowego?
Znajdzie się na to algorytm szybszy niż o złożoności n(n^2-1)?
Nie można podawać złożoności!
Ja słyszałem, że niektórym się ono nie wyświetla, ja mam, a jak u was?
U mnie nie ma, ale dostałem dobry link :)
.
Ale da się szybciej
Na forum nie podajemy rozwiązań, ani nie oceniamy ich skuteczności.
Mógłby ktoś wstawić jakąś dobrą paczkę testów wydajnościowych?
Wrzucę wieczorem.
Przez zwykłe zgłaszanie rozwiązań (https://sio2.mimuw.edu.pl/c/oi22-1/submit/) nie idzie wysłać tapczanów, ale listownie już poszło :)
Ja jutro z rana idę na pocztę. Szkoda że Komitet Olimpiady nic z tym nie robi ;/
Ja liczę w sumie na 700 pkt, a wy ?
Chce się ktoś podzielić rozwiązaniem? Bo ja nie jestem pewna czy moje to przypadkiem nie heura :/
http://pastebin.com/U4R0My3c
Napisanie całości trwało troche czasu, ale dla dodatkowych 200 pktów było warto.
Jan Omeljaniuk: Piękne i klarowne rozwiązanie! Wielkie dzięki!

Moje niestety nie jest tak czytelne, więc dzielić się nie będę.