Dzień 13 - chińskie twierdzenie o resztach

Zadanie Shuttle Search rozłożyło mnie na łopatki. Popełniłam dwa błędy:

1. 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.
2. 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... Wniosek na przyszłość: przejrzyj algorytmy przydatne w poprzednich latach.

Wtedy zauważyłam, że numery autobusów są liczbami pierwszymi...

Przypomniałam sobie, że istnieje coś takiego, jak chińskie twierdzenie o resztach (bardziej rozbudowana wersja angielska), w oparciu o które mogłabym może znaleźć timestamp przyjazdu moch autobusików. I zaczęłam czytać, przy okazji robiąc notatki (tutaj).

Układ kongruencji w moim zadaniu zbudowałam w oparciu o następującą obserwację: jeśli szukany timestamp t podzielę przez numer autobusu ai, otrzymam jako resztę ilość czasu, o jaką ten autobus przyjedzie później względem pierwszego autobusu a0 (a0 przyjeżdża w czasie t).

Dla przyładowych danych:

$7,13,x,x,59,x,31,19$

mam takie równania:

$ t = 0 \oplus 7 $

$t = 1 \oplus 13$

$t = 4 \oplus 59$

$t = 6 \oplus 31 $

$t = 7 \oplus 19$

W Pythonie reprezentuję je jako tablicę par (krotek o długości 2), których pierwszym elementem będzie numer autobusu, a drugim - pozycja autobusu (a więc reszta z dzielenia t przez numer autobusu).

Kod obliczający t w Pythonie korzysta właśnie z algorytmu wyznaczania rozwiązania takiego układu kongruencji (funkcja ctr jest opisana we (wspomnianym już wpisie).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    def solve_buses(buses_line):
      congruences = []
      buses = buses_line.split(",")

      for i in range(len(buses)):
          if (buses[i] == 'x'):
              continue
          current = int(buses[i])
          congruences.append((current, current - i))

      result = crt(congruences)
      return result

I tak w końcu, z dużym opóźnieniem, udało mi się zdobyć dwie gwazdki :)