English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
Czy ktoś też miał haszowanie i mu nie weszło czasowo? Chętnie zobaczyłbym rozwiązanie z haszami i jakie miało maksymalne czasy.
Na 10 pkt wystarczyły 3 testy:
1. Sprawdzenie parzystości częstości liter (plus jedna nieparzysta częstość dla napisów o nieparzystej długości).
2. Zliczanie par liter występujących bezpośrednio po sobie w napisie i sprawdzenie, czy częstość pary (x,y) jest równa częstości pary (y,x).
3. Zapamiętanie w wektorze bitowym pozycji ustalonej litery (użyłem pierwszej litery napisu) i sprawdzenie, czy taki wektor bitowy jest palindromem.
1. Sprawdzenie parzystości częstości liter (plus jedna nieparzysta częstość dla napisów o nieparzystej długości).
2. Zliczanie par liter występujących bezpośrednio po sobie w napisie i sprawdzenie, czy częstość pary (x,y) jest równa częstości pary (y,x).
3. Zapamiętanie w wektorze bitowym pozycji ustalonej litery (użyłem pierwszej litery napisu) i sprawdzenie, czy taki wektor bitowy jest palindromem.
To samo u mnie. Bez mydła dwa hashowania.
Ja nie dodawalem niczego specjalnego, dwa hasze o podstawie 31, oba modulo jakies niezbyt popularne liczby pierwsze wieksze niz 10^9, wydaje sie ze przeszlo.
Da się w ogóle zrobić taki test antyhaszujący? Ja założyłem, że nie wymyślą testów pod moje trzy losowe liczby pierwsze, więc się bawiłem bez soli. U mnie podstawa to było 26. Niestety, w pośpiechu zapomniałem o sync_with_stdio, więc i tak większych testów nie przejdzie…
Główny hasher poniżej:
template<long long p>
struct hasher
{
..void hash(char znak)
..{
....hash_left = (hash_left * 26 + (znak - 'a')) % p;
....hash_right = ((znak - 'a') * power + hash_right) % p;
....length++;
....power = (power * 26) % p;
..}
..bool is_symmetrical() const
..{
....return hash_left == hash_right;
..}
..long long hash_left{};
..long long hash_right{};
..long long power{1};
..int length{};
};
Główny hasher poniżej:
template<long long p>
struct hasher
{
..void hash(char znak)
..{
....hash_left = (hash_left * 26 + (znak - 'a')) % p;
....hash_right = ((znak - 'a') * power + hash_right) % p;
....length++;
....power = (power * 26) % p;
..}
..bool is_symmetrical() const
..{
....return hash_left == hash_right;
..}
..long long hash_left{};
..long long hash_right{};
..long long power{1};
..int length{};
};
Ja dodałem weryfikację losowych pozycji liter. Ciekawi mnie jednak czy były jakieś testy antyhaszujące?
Traktuję ten napis jako liczbę w systemie o podstawie 27. Idę od lewej do prawej i trzymam tę liczbę modulo p i liczbę czytaną od prawej do lewej modulo p.
Jak dostaje literke C to poprostu
h1 = 27*h1 + C,
h2 = h2 + 27^dl*C.
Na koncu sprawdza czy h1 = h2. Jak tak to palindrom, jak nie to nie.
Oczywiscie sole to wszystko. tzn 27 zmieniam na losowa liczbe > 27, dodaje jakies losowe cos do literek i robie to dla trzech roznych liczb pierwszych. Zeby mnie nie zlapali na jakims tescie antyhaszujacym.
Jak dostaje literke C to poprostu
h1 = 27*h1 + C,
h2 = h2 + 27^dl*C.
Na koncu sprawdza czy h1 = h2. Jak tak to palindrom, jak nie to nie.
Oczywiscie sole to wszystko. tzn 27 zmieniam na losowa liczbe > 27, dodaje jakies losowe cos do literek i robie to dla trzech roznych liczb pierwszych. Zeby mnie nie zlapali na jakims tescie antyhaszujacym.
Maciej, mógłbyś w skrócie opisać to haszowanie?
W oczekiwaniu na wyniki.
Było coś mądrzejszego w B niż haszowanie?
Czy A to jest po prostu przecięcie półpłaszczyzn? (btw u mnie long double ma 16 bajtow, a na sprawdzaczce 12 bajtow troche mnie to martwi.)
Było coś mądrzejszego w B niż haszowanie?
Czy A to jest po prostu przecięcie półpłaszczyzn? (btw u mnie long double ma 16 bajtow, a na sprawdzaczce 12 bajtow troche mnie to martwi.)
Potwierdzam
Potwierdzam paczkę Kajetana i nie potwierdzam testów Jana (test yes kończy się 0).
Potwierdzam :)
Ależ ja mam tego świadomość - od #5287 zaznaczyłem, że interesuje mnie już jedynie odpowiedź na pierwsze pytanie. Dzięki :)
+3
Czasy z test runa: 0.58s, 0.81s, 0.25s.
Czasy z test runa: 0.58s, 0.81s, 0.25s.