Potwierdzam wszystko.
Mateusz1: 1.04s :S

+1 :(

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

Lol, tak xD. Miałem dobrze tylko odpaliłem stary zły program 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.

Mam 904213664.

"nie można tam ... yyy ... stawiać apostrofów pomiędzy cyframi długich liczb i ... yyy ... czegośtam z constexprami robić i .... yyy ... z perspektywy competitive programmingu to raczej tyle"

To dla kompletności dorzucę, czego z nowych feature'ów mi brakowało już przy pierwszych zadaniach:

std::optional
dedukcja typu zwracanego funkcji
std::string_view
arg1 && … && args (folding)
std::rbegin, std::rend

Plus na pewno przydają się:
inicjalizacja krotek za pomocą nawiasów kwadratowych
lambda z argumentami auto
inicjalizacja w ifie
dedukcja typów w argumentach szablonów

Owszem, można sobie bez tego radzić, ale w wielu sytuacjach kod wychodzi gorszy… A wierzę, że można wykorzystywać competitive programming, żeby pisać elegancki kod.

Jeden mały teścik:

In:
20 3 999999197
Out:
374886448
EDIT:
Out:
904213664

Potwierdzi ktoś?

Czy jest prawdą:
Odpowiedź jest 0 wtedy i tylko wtedy, gdy istnieje prosta przecinająca wszystkie odcinki między dwoma wieżami tego samego maga? (pod przecinanie łapie się też przechodzenie przez jeden z końców, lub pokrywanie się)
Ktoś ma od ręki dowód/kontrprzykład?

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?

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

Chciałbym sprawdzić odpowiedzi na maxtestach, jednak mój komputer ma zbyt mało RAMu. Zwiększenie/zmniejszenie liczby instancji nie pomaga. Czy może zostać dodana możliwość zobaczenia out'ów na testrunie (tym zadaniu TES)?

PS: Pobranie więcej ramu ze strony downloadmoreram.com nie pomaga.

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

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.

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