Podzadanie ze znamym N jest warte 5 punktów w zadaniu FUT.

Okazuje się, że całe zadanie FUT da się zrobić na jednej maszynie w O(sqrt(P) * log(P)) z jakimiś wielomianami i FFT. Nie mieliśmy o tym pojęcia i na szczęście niewielu zawodników znało taką metodę.

Rzeczywiście można było wczytać całe wejście w TEA w 3.5s, ale trzeba było być bardzo szybkim w reszcie kodu. W szczególności, linia "for(int i = 0; i < N; ++i) ++count[GetElement(i)]" może nawet przekroczyć 5s. Bezpieczniej było napisać rozwiązanie w O(N log (N) / sqrt(100)) lub ewentualnie podzielić ciąg na nierówne przedziały w rozwiązaniu z czytaniem całego wejścia - maszyny, które mają przeczytać prawie cały ciąg, powinny dostać mniejszy przedział do policzenia inwersji w środku.

Bonus: Zadanie TEA da się zrobić w O(N / sqrt(100) + N log(N) / 100).

"Okazuje się, że całe zadanie FUT da się zrobić na jednej maszynie w O(sqrt(P) * log(P)) z jakimiś wielomianami i FFT. Nie mieliśmy o tym pojęcia i na szczęście niewielu zawodników znało taką metodę."

Ja coś takiego znalazłem (nie mylić z zaimplementowałem) do obliczania silni, ale jak to daje radę rozwiązać całe zadanie?

Też chętnie się dowiem. Co do silni w O(sqrt(P) log(P)) to można ją znaleźć tutaj: https://codeforces.com/blog/entry/63491 ale nie chciało mi się wnikać w szczegóły nie wiedząc jak to wykorzystać.

https://discuss.codechef.com/questions/84205/how-to-calculate-sum-of-binomial-coefficients-efficiently

https://min-25.hatenablog.com/entry/2017/08/03/062450

https://loj.ac/problem/6386

A jakieś ETA na wyniczki?

Ja nie mam pojęcia. W poprzednich latach to pewnie było kilkanaście godzin nawet.

A okej, dzięki.

>for(int i = 0; i < N; ++i) ++count[GetElement(i)]

Czemu miałoby to zająć ekstra 1.5s? Coś takiego mi w testach zajęło 0.49s, wraz z liczeniem GetElement (=i%1000000 +1). Czy jednak zadanie testowe nie jest miarodajne? :>

Po operacji ++count[GetElement(i)] spodziewałbym się, że jest ograniczona przez dostęp do pamięci. Nie byłbym w najmniejszym stopniu zdziwiony dwukrotnym spowolniem w sytacji w której dane pochodzą z pamięci.

Ale dużo ciekawsza pułapka mogła czekać w FUT. Umieszczenie w kodzie "int GetP() { return 123456789; }" spowoduje, że kompilator nie będzie generował dzieleń dla %p, ale zamieni je w mnożenia. W faktycznej sprawdzarce niemal napewno ta dana pochodzi z pliku wejściowego i wymaga wykonywania dzieleń (a przynajmniej kompilator nie zrobi tego za nas).

Marcin, iterowanie się kolejno po elementach tablicy jest dużo szybsze niż skakanie po pamięci.

A nie, rzeczywiście. Ja miałem odczyty, a nie zapisy. To może być znacznie szybsze ze względu na cache.

A czy jest rozwiązanie bez wczytywania wszystkich elementów w niektórych węzłach?

Ja mam złożoność z bonusa (w której brakuje czynnika sqrt(nodes)*zakres) i wczytywałem ~30 mln, a dość prosto da się wczytywać koło 15 mln tylko wtedy płaci się za to kosztem posiadania n log n / sqrt(nodes) zamiast n log n / nodes, co wydaje się że jednak byłoby dość opłacalną zamianą (tym bardziej że rozw też istotnie prostszy od mojego)

W bonusie brakuje składnika O(zakres). Masz więc Świstak bruta :D

This is a really awesome and helpful article for me. I really appreciate your work for providing such useful information, thank you so much!
https://kexing-chemical.com/product/carbon-molecular-sieve/