Ok. Czy ja robie cos glupiego w B, czy kazdy ma poprostu czas wczytac wszystko (3.5s) a potem ma 2.5 s zeby zajac sie soba i wyslac reszcie.
w A natomiast:
kluczem jest wzorek f(n, n-k) = sum_(j=0)^(n-k) (k+j-1 po j) 2^(n-k-j)
co pozwala podzielić sumę na kawałki w których nie ma n.

Potem tylko optymalizacja liczenia odwrotnosci mod p.
Trochę mnie martwi, że działa mi 2.5s na probnym (u mnie powinno dzialac tak samo niezaleznie od testu).

Można wszystko wczytać, maxczasy na tes około 1s... Limit raczej wygórowany, jak się zdaje.

Zależy, co się wstawi w funkcję GetElement(). Przy czym zgadza się, że nie może to być nic dłuższego niż 0.035 mikrosekundy.

W TEA ja mam zrobione tak:

Najpierw rozdaje kazdej instancji kolejne bloki tablicy. Nastepnie, kazda z instancji liczy liczbe inwersji w swoim bloku (zrobilem to drzewem BIT, bo szybsze niz mergesort tu chyba bedzie) jak policzy to wysyla do mastera. Master, po odebraniu wszystkich podwynikow ze wszystkich instancji najpierw dodaje te podwyniki do koncowego wyniku i jedyne co mu pozostaje pozniej to policzenie inwersji pomiedzy elementami w roznych blokach. Robie to tak: wczytuje wszystkie elementy tablicy od pierwszego do ostatniego, ale w kawalkach odpowiadajacych dlugosciom blokow oraz utrzymujac dwie tablice: cnt[x] := ile razy widzialem x, larger[x] := ile razy widzialem wartosci wieksze od x. Teraz, dla kazdego wczytanego elementu x, dodaje do wyniku wartosc larger[x] oraz dodaje 1 do cnt[x]. Jak skoncze przerabiac kawalek dlugosci bloku, to przeliczam na nowo tablice larger uzywajac wartosci z cnt. Poniewaz liczymy tylko inwersje pomiedzy elementami roznych blokow, to tablice large przeliczamy po przerobieniu kazdego bloku, a ze wszystkie wartosci sa nie wieksze niz 10^6 to wszystkie przeliczenia takiej tablicy zajmuja sumarycznie O(10^6 * liczba blokow).

W FUT nie wpadlem na ten wzorek, ktory pozwala podzielic sume na kawalki, w ktorych nie ma n, i mam tylko rozwiazanie, w ktorym kazda instancja musi znac n. Uzywalem wzorka bin(n, k) = bin(n, k-1) * (n+1-k) / k, a kazda instancja liczyla swoja sume iloczynow i ostatni mnoznik jaki policzyla, a takze unikala robienia odwrotnosci modulo. Na koncu master to wszystko scalal.

Coś więćej o tym wzorku powiesz? Zwłąszcza, co to f(.) - ta nasza suma?

Ja, po zorientowaniu się, że jednak nie mogę N po prostu rozesłać do innych instancji ;-) kombinowałem tak:

Zafiksujmy sobie k, nie będę go co chwila pisał.
Nasz ciąg S_n = nasz ciąg = \sum_0^k C(n,k)
S_k = 2^n (a wcześniejsze nas nie obchodzą).
S_{n+1} = 2 S_n - C(n,k ) (to jest wprost z trójkąta Pascala, linijka, która nas interesuje to suma linijki wyżej i linijki wyżęj, ale bez ostatnoiego elementu, który poszedł w prawo).
Na C(n,k) też jest przyjemna rekurrejcnaj, C(n,k)= C(n-1,k)n/(n-k), oznacze sobie to C_n

Jeśli moglibyśmy jechać od początku, (tzn S_k=2^k, C(k,k)=1) prosto, ale liniowo i sekwencyjnie wyliczymy S_n. Ale można zrobić coś więcej, to wszytko są liniowe operacje, da się policzyć, że jeśli na poziomie n1 mamy jakieś S_n1, C_n1 (nie znając ich!) to ileś poziomów niżej, na n2: C_n2 = br C_n1, S_n2 = sr S_n1 + ar C_n1.
Na wspołczynniki sr,ar,br można napisać rekurencję, przelecieć zakres n1..n2 wykonując głowną cześć pracy, i dopiero pod koniec odczytać Sn_1 i C_n1, który przypełzły z instancji wcześniejszej, w pakiecie wraz z liczbą N. Jeśli N jest w zakresie [n1,n2] to obliczamy Sn i wyrzucsamy w sieć wynik, jeśli było wcześneij, forwardujemy wcześniejszy wynik, jeśli dopiero będzie, oblicamy S_n2 i C_n2, aby nakarmić kolejną instncję. Ostatnia instancja wypisuje.

Cała praca jest robiona najpierw, a potem informacja leci w kółeczko. Niestety, nie pozbyłem się odwrotnośći modulo, bo trzeba było zająć się i teatrem, więc może się nie zmieścić.

teatr:
92 instancji pracuje na takich kratkach na "kostce" gdzie na bokach są widzowie.
xxxx
xxx
xx
x
Każda kosteczka ma doki o dlugości ~n/14. Zliczam w niej inwersji na obu tych bokach i inwersje pomiędzy bokami, w instancji 0 skladam ( wszystkie 'cross inwersje', wszystkie wewnętrzne z jednego boku, oraz jedna z boku prostopadłego, o której zapomnialem:) )

Ok to ja napiszę coś więcej:
0. f(n,k) to jest to co liczymy. tzn. f(n, k) = sum(j=0...k) C(n, j).
1. Jest taka dualność oczywista f(n, k) + f(n, n-k) = 2^n + C(n, k).
2. Wzorek na f(n, n-k) można zapisać jako: f(n, n-k) = 2^(n-k) sum_(j=0)^(n-k) C(k+j-1, j ) 2^(-j)
Jaki z tego profit?
Składniki, które sumujemy nie mają w sobie n, n jest tylko w granicy sumowania.

Więc teraz standardowo, i-ty gostek dostaje
przedział [i*10^7, (i+1)*10^7) i liczy tam prefixy tej sumy (w liniowym czasie * czas odwrócenia modulo), a potem wysyła co 2000 prefix do pierwszego. A pierwszy mając te prefixy już składa sobie odpowiedź doliczając brakujące fragmenty samemu.

Jak optymalizować odwracanie modulo to osobna historia, bo optymalizacja tam, pozwoliła mi zejść z 7s do 2.5s.

@Maciej Mógłbyś pokazać dlaczego f(n, n-k) = 2^(n-k) sum_(j=0)^(n-k) C(k+j-1, j ) 2^(-j) ?

[TEA] założyłem że skoro wczytanie to max 3.5 s to nie kombinowałem. Każdy nod zliczał konflikty użytkowników o wzroście w przedziale o długości 10000 za pomocą drzewa licznikowego. Dodatkowo obsłużyłem przypadek <= 5. Jedyny problem byłby gdyby wszystkie osoby były w jednym przedziale wiec zrobiłem statystykę na próbce 1000 elementów żeby wykryć newralgiczny przedział. Jednak nie zdążyłem tego dokończyć i najdłuższy czas to było 4.2 sekundy.

OEIS A008949 linkuje do tego artykułu http://capone.mtsu.edu/dwalsh/subcount.pdf

Fut miałem inaczej:
Niech s_m = sum[i = 0 to k] m choose i
s_(m + 1) = s_m * 2 - (m choose k) (prosty wniosek z (m + 1 choose k) = (m choose k) + (m choose k - 1), albo przez interpretację kombinatoryczną)
s_k = 2^k
(n + 1 choose k) = (n choose k) * (n + 1) / (n - k + 1) (rozpisujemy silnie, albo też intepretacja kombinatoryczna
Z tego mamy
(s_i, k choose i) ((2, 0) (-1, (i + 1) / (i - k + 1))) = (s_{i+1}, k choose i + 1) (macierz razy wektor)
To niech A_i = ((2, 0) (-1, (i + 1) / (i - k + 1)))
Chcemy policzyć (2^k, 1) * A_k * A_{k+1} * A_{k+2} * ... A_{n-1}
dzielę przedział [k, MAX_N] ta 99 mniej więcej równych przedziałów, instancje 1-99 liczą iloczyn macierzy na swoim przedziale, instancja 0 wybiera przedział w którym będzie n i liczy iloczyn macierzy z odpowiedniego prefixu tego przedziału.
Następnie odbiera iloczyny macierzy na blokach, liczy iloczyn bloków które w całości mieszczą się w przedziale [k, n) i obliczonego prefiksu ostatniego bloku. Następnie przemnaża to przez wyjściowy wektor i dostaje odpowiedź.
I żeby nie liczyć dużo razy odwrotności modulo trzymam macierz jako: krotkę ((a, b), (c, d), e) i reprezentuje to macierz ((a / e, b / e), (c / e, d / e)), odwrotność modulo liczę raz na sam koniec przy mnożeniu przez wektor

EDIT: fut1e OK 0.77s / 3.00s
I to trochę dlatego, bo tak to napisałem, że dzielę cały przedział [k, MAX_N) na 99 przedziałów, a nie na 100 i odrzucam ostatni, czyli wyniki policzone przez instancję 99 nigdy nie zostaną wykorzystane

Tomasz Bochyński - Ja podobnie, dzielę dziedzinę [1..10^6] na 100 przedziałów. Nie dzieliłem jednak na równe przedziały - uznałem, że jak podzielę naiwnie na przedziały [i*10^4, (i+1)*10^4), to mogę nic nie zyskać, gdy np. połowa elementów będzie w jednym przedziale. Jak sobie z tym poradziłeś?

Moje przedziały są o w miarę równej (+- O(100*100), albo może O(10^6)?) liczbie pozycji w tablicy. W pierwszej fazie, węzeł k liczy na przedziale (k*10^6, (k+1)*10^6] 100 statystyk pozycyjnych: 10^4-ty element, 2*10^4-ty, etc. Te statystyki są wysyłane do lidera, i spośród otrzymanych 100*100 wartości, lider wybiera 100-tą, 200-tą etc, i to one służą jako końce. Przy czym, przedziały postaci [a..a] są obsługiwane szczególnie - upewniam się, że "a" jest liczone raz, i nie występuje w żadnym innym przedziale.

@Krzysztof wrzucisz kod, bo zupełnie nic nie rozumiem?

@Krzysztof - jeśli tylko połowa elementów jest w jednym przedziale to też coś zyskasz bo zchodzimy z zakresu 2^20 do 2^14 więc czas na przeliczenie skaca się o 2/3 co +/- już mogło wystarczyć. Gorzej jak wszystkie są w jednym przedziale. Ja nawet nie rozbijałem próbkowania na węzły tylko każdy liczył tą samą próbkę i ustalał czym się zająć(przesłanie kosztuje tyle samo albo więcej), ale jak pisałem nie zdążyłem dopracować algorytmu (min sytuacja jak są mało unikalne wartości) i wolałem stracić kilka punktów na TLE niż wszystkie na WA. Na szczęście w tym roku zadania i przypadki testowe są bardziej przystępne niż w zeszłym roku :)

W TEA łatwo można było ograniczyć liczbę porównań między blokami do połowy: na węźle i-tym blok i-ty porównujemy z blokami na lewo w odległości nieparzystej, a na prawo w odległości parzystej. To wystarczyło na 10pkt: max. 5.47s.