English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Temat: [WDP] checker
Z ciekawości. Jak działa tutaj checker? Hashuje zbiór odwiedzonych punktów, czy jakoś mądrzej?
Hashuje zbiór odwiedzonych krawędzi, czyli mądrzej. Ciekawostka: u nas można było zaczynać w dowolnym punkcie, gdyż na początku źle przeczytaliśmy treść z OIJ i myśleliśmy, że tam też.
Ja też jestem zaciekawiony jak checker działa :)
Mogę podzielić się tym jak ja zaklepałem checker, podejrzewam że orgowie robili coś podobnego.
Dla wygody zakładamy, że ruchy mapują się na takie wektory:
\ |
.\|
--x--
..|\
..| \
i przeskalowuję je tak, aby środek każdego takiego wektora był w punkcie kratowym.
Narysowane odcinki możemy reprezentować teraz jako (multi)zbiór tych środków, a te możemy sobie wygodnie hashować w następujący sposób:
- hash punktu (x, y) to A^x * B^y mod P (dla zafiksowanych A, B, P),
- hash zbioru to suma hashy jego elementów.
Taki sposób hashowania pozwala wygodnie przesuwać cały zbiór punktów o dowolny wektor.
Teraz chcemy policzyć hashe następujących rzeczy - a) piramidy o boku n; b) tego co narysuje żółwik
a) to po prostu jakaś wzorkologia, ja to liczyłem czymś w stylu szybkiego potęgowania
b) to jest ta ciekawsza część. Główna obserwacja jest taka, że dowolna sekwencja ruchów wygeneruje nam jakiś zbiór punktów + przesunie żółwika o jakiś offset (zależny tylko od tej sekwencji). Dzięki temu możemy sobie szybko radzić z sekwencjami postaci N[...]. Wystarczy policzyć hash i offset tego co jest w środku, a wówczas hash N[...] możemy policzyć korzystając z tego że potrafimy szybko przesuwać zbiory o ten offset.
Dokładniej wychodzi coś w stylu hash(N[S]) = hash(S) * (1 + A^x B^x + A^(2x) B^(2x) + ... + A^((N-1)x) B^((N-1)y)), gdzie (x, y) to offset po wykonaniu S.
Dla wygody zakładamy, że ruchy mapują się na takie wektory:
\ |
.\|
--x--
..|\
..| \
i przeskalowuję je tak, aby środek każdego takiego wektora był w punkcie kratowym.
Narysowane odcinki możemy reprezentować teraz jako (multi)zbiór tych środków, a te możemy sobie wygodnie hashować w następujący sposób:
- hash punktu (x, y) to A^x * B^y mod P (dla zafiksowanych A, B, P),
- hash zbioru to suma hashy jego elementów.
Taki sposób hashowania pozwala wygodnie przesuwać cały zbiór punktów o dowolny wektor.
Teraz chcemy policzyć hashe następujących rzeczy - a) piramidy o boku n; b) tego co narysuje żółwik
a) to po prostu jakaś wzorkologia, ja to liczyłem czymś w stylu szybkiego potęgowania
b) to jest ta ciekawsza część. Główna obserwacja jest taka, że dowolna sekwencja ruchów wygeneruje nam jakiś zbiór punktów + przesunie żółwika o jakiś offset (zależny tylko od tej sekwencji). Dzięki temu możemy sobie szybko radzić z sekwencjami postaci N[...]. Wystarczy policzyć hash i offset tego co jest w środku, a wówczas hash N[...] możemy policzyć korzystając z tego że potrafimy szybko przesuwać zbiory o ten offset.
Dokładniej wychodzi coś w stylu hash(N[S]) = hash(S) * (1 + A^x B^x + A^(2x) B^(2x) + ... + A^((N-1)x) B^((N-1)y)), gdzie (x, y) to offset po wykonaniu S.