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.)

Maciej, mógłbyś w skrócie opisać to haszowanie?

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.

Ja dodałem weryfikację losowych pozycji liter. Ciekawi mnie jednak czy były jakieś testy antyhaszujące?

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{};
};

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.

To samo u mnie. Bez mydła dwa hashowania.

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.

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.

Ten uczuć kiedy zmierzysz na przykładowych uruchomieniach czasy tak by mieć czasy ~ 4 sekund, a następnie nie wyślesz prawdziwego zgłoszenia...

https://hastebin.com/buguqiyuha.m

Też miałem haszowanie i dostałem 2 punkty przez TLE. Dla każdego znaku wykonywałem potęgowanie modularne zamiast przechowywać wartość aktualnej potęgi. Na moim kilkuletnim bolidzie mieściłem się ze sporym zapasem w limitach czasowych na maksymalnych testach, ale najwidoczniej tutaj to podejście nie wystarczyło.

Niezłe to getchar_unlocked(), nie znałem tego. Ja dostałem akurat 4 punkty i miałem liniowe, ale boli dupę jakbym dostał 0.

@Krzysztof Wojtas
Toż to jakaś heura np abcacbacbabca
tzn szansa że ktoś uwali jest mała, ale nadal

U siebie również mieściłem się na max-testach ze sporym zapasem, na sprawdzaczce 2/10 :(

Również zrobiłem szybkie potęgowanie..
https://github.com/terjanq/Competitive/commit/6a8ef170bd9e776cc29d20331f4dd69d4be6b531

Uwazam, ze kara za logarytm przy potegowaniu jest zbyt duza. Rowniez patrzac na to rozwianie heurystyczne za 10 punktow...

Niestety ja dość boleśnie dowiedziałem się, że jest limit na ilość submitów rozwiązania (na ACM nie ma), więc może pochwalę się rozwiązaniem, które dostaje maxa w tym zadaniu.

Otóż łatwo widzieć, że istnieje wiele własności, które są zachowywane przez palindromy. Jednak kluczowa wydaje mi się obserwacja, że o ile dla każdej własności łatwo podać niepalindrom są spełniający, o tyle jest koszmarnie trudno przygotować testy bez znajomości tychże własności.

O jakich własnościach piszę? Otóż najprostsza - ilość każdej z liter palindromie parzystym musi być parzysta (w nieparzystym każdej z liter za wyjątkiem jednej). Inny przykład. Jeśli w palindromie o długości n mamy literę x na pozycji i, to na pozycji n-i też jest x. Zatem suma pozycji, na której występuje dana litera jest podzielna przez n. Oczywiście można tworzyć też inne statystyki. Np. suma trzech kolejnych liter. Jeśli mamy 26 liter, suma trzech kolejnych może być od 0 do 3x26-1. Liczymy dla każdej z tych wartości sumę miejsc wystąpień. Ogólnie można przyjąć, że jeśli p (p1, p2, ..., pn) jest słowem wejściowym, to można wziąć l kolejnych elementów ciągu wejściowego, wziąć współczynniki a1, a2, ... al i liczyć dla każdej pozycji liczyć (pi x (a1+al) + p(i+1) x (a2 + a(l-1)) ... + p(i+l-1) x (al + a1) ) % q i tyle.

Co więcej. Można też pogrupować litery w ciągi, np. trzyliterowe i dla każdego trzyliterowego ciągu zliczać sumę indeksów, na których występuje. W tym przypadku następnie trzeba brać pod uwagę wzajemne palindrowy, czyli f[abc] + f[cba] musi być podzielne przez n.

Jeśli ktoś by chciał mocno czarować, można by nawet współczynniki ai powyżej losować. W takim przypadku nie da się nawet zrobić testów znając heurystyki...

Reasumując, u mnie 10 pkt dostawało rozwiązanie, które:
- liczyło prostą sumę kolejnych 3, 8 i 13
- liczyło sumę pozycji wszystkich trójznaków
- liczyło sumę 7 kolejnych znaków z losowymi współczynnikami będącymi liczbami pierwszymi ze zbioru 13 pierwszych liczb pierwszych modulo 4096

A ja to zadanie robiłem tak:
Zwróćmy uwagę, że liczba możliwych półsłów wynosi 26**(10**7). Załóżmy, że mamy poprawne rozwiązanie R. R, po wczytaniu półsłowa ma jakiś stan RAM. Ponieważ liczba możliwych stanów RAM (2**(8 * 4 * 1024 * 1024)) jest mniejsza niż liczba możliwych półsłów, R musi mieć taki sam stan RAM dla jakichś dwóch półsłów A != B. To znaczy, że dla któregoś ze słów AA^T, AB^T, BA^T, BB^T zwróci złą odpowiedź (palindromami są tylko AA^T i BB^T). Sprzeczność z założeniem, że istnieje poprawne rozwiązanie R.

A więc skoro i tak, o ile testy będą dostatecznie dobre (a zwykle w potyczkach były), wszystko dostanie 0, można wysłać jakąś prostą heurę: ja zapisywałem (w systemie 32) pierwsze 4*10**6 liter i porównywałem z ostatnimi oraz sprawdzalem, czy liczba liter w pierwszym i drugim półsłowie się zgadza. To zadziałało na wszystkich testach ze znaną długością.

Da się to uogólnić do nieznanej długości, ale nie chcialo mi się tego pisać (bo i tak to tylko heura), więc nie wiem, czy dostałoby 10.

@Jan Gora niby tylko logarytm, ale z drugiej strony ze sporą stałą. Dopuszczenie rozwiązań 30-60 razy dłuższych niż referencyjny też by nie było dobre.

No i uint64_t. Sprawdzarka jest 32 bitowa*), więc long longi są ze dwa razy bardziej kosztowne w mnozeniu niż zestaw 2 hashy w uint32 (z odpowiednio małymi liczbami pierwszymi).
Spokojnie możesz mieć 2 razy szybszy komputer niż sprawdzarka. x4 za architekrurę. I już z 1s u Ciebie lokalnie robi się 8s na sprawdzarce.

*) w którymś poprzednim zadanku prawie się na to naciąłem od innej strony, kwadratopwanie size_t przekręcało licznik, uruchomienie próbne mnie uratowało.

Większość czasu, który mogłęm poświecić na [her] poszłą na uparte próby liczenia hashy do i od środka, zapamiętując tylko potrzsebny fragment ciągu - 1/4 długości. Dodając kompresję 6 literek w int, wychodziło <4MB, i się zafiksowałem, że to musi być poprawne rozwiązanie. Piękną fifo napsiałem:) Ale limity ubijały. Jak w końcu zaskoczyłem, nie mogłęm uwierzyć w swoje zaćmienie. https://pastebin.com/1gUnp5mP (edit: 3 hashe 32 bitowe, podstawy 29 i 31, mod pierwsze z okolic 30-40k, max 1.07s)

Ja w PAL zrobiłem 2 hasze 64bit i dostałem 6/10 przez TLE. Sprawdzałem na próbnym uruchomieniu dla max. danych (10MB) i miałem 2.29s, więc stwierdziłem że dla rzeczywistych max danych (20MB) w 5s się zmieści, co niestety okazało się nieprawdą. Co ciekawe dla testów o podobnych rozmiarach dostawałem dość mocno różniące się czasy, np.:

19546756 pal10a.in -> 4.35s
17221905 pal10c.in -> 4.84s

Prosiłem o retest, i dostałem odpowiedź że wyniki były takie same. Ktoś może się domyślać przyczyny takiego zachowania się sprawdzarki?

Dla porównania u siebie miałem czasy bardziej proporcjonalne do wejścia:

19546756 pal10a.in -> 1.762s
17221905 pal10c.in -> 1.528s

Ale Wy macie farta z tymi heurami... Układający testy się bardzo nie postarał. Ja rozumiem, że heury się uwala łatwiej mając je przed oczami. Ale o ile po przeczytaniu heury Krzyśka uważałem, że aby coś takiego uwalić to nawet jej nie znając nie trzeba się aż tak bardzo starać aby ją uwalić, to to co napisał Sygi to mnie zupełnie rozwaliło. Wystarczy wziąć długi palindrom i swapnąć dwie literki blisko środka :|...Did opracowujący even try? Czy testy to było "wylosuj długie słowo X i jako test daj albo X albo XX^r" xd?

Autorzy testów/zadania skupili się na uwalaniu nlogn zamiast weryfikacji poprawnosci rozwiązania. Wystarczyloby dostatecznie duzo malych testow zeby odsiac te "prostsze" heury. Tym bardziej 2/10 boli.

@Bartłomiej Szczygieł
Usunięcie fastpow przyspieszylo program jedynie 10-krotnie (miescilby sie w limicie juz bez problemu). Wyglada na to, ze dostalem ~10sekund na maxtescie na sprawdzaczce. Bardzo mozliwe ze samo usuniecie long longow by wystarczylo na wiecej punktow... 60% punktow to bylaby uczciwa ocena IMO, szczegolnie ze z tego co pamietam schodzenie z O(n) do O(nlogn) rzadko kiedy praktycznie zerowalo punkty.

@Jan Gora
Wystarczy że ktoś zrobi program:
tekst krótszy niż 1e7 zrób normalnie;
tekst dłuższy niż 1e7 zapuść heurę.
I już nie sprawdzisz czy nie ma heury.
Uwalanie modul czy heur jest bez sensu, bo istnieje pierdyliard innych podejść których już nie uwalisz, a to dość niesprawiedliwe.

No a że nlogn nie wchodzi to raczej standardowe limity czasu (w końcu na ogół w zadaniach na nlogn zachodzi n < 5e5) + nietrudno sprawdzić czy to nie jest za wolno jak zauważysz że to mocno naciągane.

@Jakub Sygnowski
rewind(stdin) i cały dowód się sypie

Czy dało się użyciem rewind zhackować zadanie?

Czy mógłby ktoś pochwalić się MAG?

@Bartłomiej Szczygieł: Co do PAL, to ja sobie po prostu upakowalem te literki w:
struct Packed16Chars {
unsigned int c0:5,c1:5,c2:5,c3:5,c4:5,c5:5,c6:5,c7:5,c8:5,c9:5,c10:5,c11:5,c12:5,c13:5,c14:5,c15:5;
} __attribute__((packed));
zeby sie w pamieci zmiescilo. I przeszlo.

@Tomasz Jarosik: To nie wystarczy dla najdłuższych słów. @Jakub Sygnowski obliczył że w 4MB się nie zmieści pół najdłuższego słowa nawet jak upakujesz najgęściej jak się da (w długą liczbę o podstawie 26). Potrzeba na to dokładnie log(26^(10^7))/log(2^(8*2^20)) MB =~ 5.6 MB.

Bardzo ciekawy wątek! Myślałem, że będzie chodziło o jakąś magiczną kompresję 1. połowy.
Nie tylko pakowanie, ale może wciągnięcie kawałka, zrobienie statystyk itp. i następnie jakiś huffman czy coś.
Liczenie na jakiekolwiek punkty za wersję dla słów o długości do 2 * limit_pamięci (na statycznej tablicy char'ów) było złudne.

Um Probleme mit dem Penis zu lösen, ist es Zeit, dass Sie versuchen, Ihre Aufmerksamkeit auf diese Seite zu lenken https://mannapotheke.de/levitra/, Dank kotormou ich immer bekommen, um Probleme dieser Art zu lösen

Thanks for the update and quick reply. I'll be sure to keep an eye on this thread. Looking for the same issue. Bumped into your thread. Thanks for creating it. Looking forward for solution.
https://www.mypascoconnect.website/

Helllo Friends My name is Bill Pop and I leave in Los Angeles, California and try to bring new entertainment shows. Bally Sport It is an OTT platform, which streams the entire Bally Sport content. It offers TV shows at the global level for the different age of people. You can enjoy Bally Sport shows and movies with Android TV. You can also activate Bally Sport on your Apple TV too. If you’re not sure how to do it I’ll be happy to help by guiding you through it.

http://ballysportcomactivate.com/
https://www.facebook.com/profile.php?id=100085889195628
https://twitter.com/BillPop53264022
https://www.linkedin.com/in/bill-pop-133532250/
https://www.pinterest.com/billcarsshow/