English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
A może to zadanie też już ktoś zrobił i chętnie porówna wyniki ?
https://www.mimuw.edu.pl/~ms337666/PA/rykmax.in
https://www.mimuw.edu.pl/~ms337666/PA/rykmax.out
https://www.mimuw.edu.pl/~ms337666/PA/rykmax.in
https://www.mimuw.edu.pl/~ms337666/PA/rykmax.out
W bonusie brakuje składnika O(zakres). Masz więc Świstak bruta :D
Czy mógłby ktoś pochwalić się MAG?
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.
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.
Super zadanko, o co wam chodzi?
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)
A czy jest rozwiązanie bez wczytywania wszystkich elementów w niektórych węzłach?
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
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
OEIS A008949 linkuje do tego artykułu http://capone.mtsu.edu/dwalsh/subcount.pdf
[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.
@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) ?
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.
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.
A nie, rzeczywiście. Ja miałem odczyty, a nie zapisy. To może być znacznie szybsze ze względu na cache.
To już nie bug tylko feature, istnieje od poczatku tej wersji strony.
https://loj.ac/problem/6386
seems like a notorious coincidence
seems like a notorious coincidence