Zadanie Shuttle Search rozłożyło mnie na łopatki. Popełniłam dwa błędy: Najpierw długi czas rozwiązywałam całkiem inne zadanie (pozycję autobusu na liście wejściowej traktowałam jako różnicę czasu do poprzedniego zamiast to pierwszego autobusu). Wniosek na przyszłość: czytaj dokładnie treść zadania. Póżniej zauważyłam, że moje naiwne przesuwanie iteratorów działa tylko dla danych testowych - dla danych właściwych zwisa na długie minuty (dłużej nie czekałam...). Widocznie istnieje jakiś lepszy algorytm niż brute force.

krótkie przypomnienie chińskiego twierdzenia o resztach

Co za zbieg okoliczności. Wczoraj przygotowałam wpis na temat sortowania topologicznego (zauważyłam nowy moduł w Pythonie 3.9), a dzisiejsze zadanie właśnie takego przesortowania wierzchołków wymagało. Przyznam się, że zrozumiałam to dopiero wtedy, gdy moje naiwne rozwiązanie, które sprawdziło się dla danych testowych, zupełnie zwisnęło na właściwych danych. Czekam, czekam, a tu nic. W moim grafie, reprezentowanym jako dict, z wierzchołkiem (nominalną wartością zasilania przejściówki) związana była lista tych wierzchołków/przejściówek, do których można dany wierzchołek wpiąć.

Wpis i graphlib i sortowanie topologiczne w pythonie

kilka słów na początek