English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Temat: [MOP] rozwiązanie/spostrzeżenia
Hej, byłby ktoś chętny podzielić się jakimiś wskazówkami, a jeszcze lepiej rozwiązaniem?
Kompletnie byłem bez pomysłu, nawet na podzadania.
Kompletnie byłem bez pomysłu, nawet na podzadania.
Ja chyba (?) rozwiązałem podzadanie z ai < 300:
Wtedy sumarycznie nigdy nie przekroczymy p. Zatem znajdujemy wszystkie najmniejsze parzyste przedziały np
0 | 1 0 1 | 1 3 | 2 | 6
wynik to 2^ilosc_podzialek % p
Wtedy sumarycznie nigdy nie przekroczymy p. Zatem znajdujemy wszystkie najmniejsze parzyste przedziały np
0 | 1 0 1 | 1 3 | 2 | 6
wynik to 2^ilosc_podzialek % p
O(n^2):
1) liczymy sumy prefiksowe (modulo)
2) przechodzimy pętlą po każdej wartości o indeksie i, mniejszym od n
3) przechodzimy pętlą po każdej wartości o indeksie j, mniejszym od i
4) jeżeli przedział (j ... i] jest modulo parzysty (co sprawdzamy w czasie stałym, dzięki sumom prefiksowym), to jest już dość dobrze,
bo do podzielenia został nam przedział [0 ... j], dla którego liczbę wszystkich możliwych podziałów mamy już policzoną, więc po prostu dodajemy ją do wyniku dla przedziału [0 ... i].
5) Zapisujemy wynik dla [0 ... i]
6) W momencie, w którym i = n, mamy policzone
1) liczymy sumy prefiksowe (modulo)
2) przechodzimy pętlą po każdej wartości o indeksie i, mniejszym od n
3) przechodzimy pętlą po każdej wartości o indeksie j, mniejszym od i
4) jeżeli przedział (j ... i] jest modulo parzysty (co sprawdzamy w czasie stałym, dzięki sumom prefiksowym), to jest już dość dobrze,
bo do podzielenia został nam przedział [0 ... j], dla którego liczbę wszystkich możliwych podziałów mamy już policzoną, więc po prostu dodajemy ją do wyniku dla przedziału [0 ... i].
5) Zapisujemy wynik dla [0 ... i]
6) W momencie, w którym i = n, mamy policzone
O(n log n)
Iterujemy się od lewej do prawej licząc cały czas sumy prefixowe modulo M, chcemy dla każdego prefixu policzyć wynik.
Jeżeli widzimy sumę x na [0, i), to przedziały [j, i) są dobre jeśli suma prefixowa [0, j) jest albo tej samej parzystości co x i mniejsza równa niej, albo przeciwnej i ostro większa. To trzymamy na wskaźnikowym drzewie przedziałowym, czy czymś podobnym, indexowanym wartością sumy prefixowej sumy elementów na parzystych i na nieparzystych indexach i po prostu odpytujemy o sumę, by dostać wartość na danym przedziale, i dodajemy w punkcie, żeby zaktualizować strukturę o aktualny prefix.
Iterujemy się od lewej do prawej licząc cały czas sumy prefixowe modulo M, chcemy dla każdego prefixu policzyć wynik.
Jeżeli widzimy sumę x na [0, i), to przedziały [j, i) są dobre jeśli suma prefixowa [0, j) jest albo tej samej parzystości co x i mniejsza równa niej, albo przeciwnej i ostro większa. To trzymamy na wskaźnikowym drzewie przedziałowym, czy czymś podobnym, indexowanym wartością sumy prefixowej sumy elementów na parzystych i na nieparzystych indexach i po prostu odpytujemy o sumę, by dostać wartość na danym przedziale, i dodajemy w punkcie, żeby zaktualizować strukturę o aktualny prefix.
To ja mogę wytłumaczyć podzadania.
Jeśli ai <= 100 to suma wszystkich elementów jest mniejsza niż 10^9 + 7
To znaczy, że dowolna suma jest mopadulo jeśli po prostu jest parzysta.
Tutaj możesz już spróbować napisać dynamika T[ i ] [ p / n ] = ile jest możliwości na które można podzielić a[1 .. i] na przedziały które są parzyste, oprócz ostatniego bloku który jest parzysty [p] lub nieparzysty [n].
Jak się przypatrzysz temu rozwiązaniu to zauważysz, że wynikiem zawsze jest potęgą dwójki.
Niech P oznacza liczbę parzystą a N liczbą nieparzystą.
Rozważmy ciąg:
P | P | N P N | N N | P
Jak widzisz pionową kreską oznaczyłem wszystkie prefiksy, które są parzyste.
Ilość możliwości podziałów w takim ciągu wynosi 2^4 (bo 4 to liczba kresek).
Jeśli n <= 3000 to rozwiązanie O(n^2) ma szansę zadziałać.
Robimy algorytm dynamiczny V[i] oznacza na ile możliwości można podzielić ciąg a[1 .. i].
Każdą wartość liczymy w czasie liniowym.
Zaczynamy od ustawienia V[i] = 0
Dla każdego 1 <= j <= i patrzymy czy a[j] + a[j+1] + ... + a[i] jest mopadulu.
Jeśli tak to do V[i] dodajemy V[j-1].
Jeśli ai <= 100 to suma wszystkich elementów jest mniejsza niż 10^9 + 7
To znaczy, że dowolna suma jest mopadulo jeśli po prostu jest parzysta.
Tutaj możesz już spróbować napisać dynamika T[ i ] [ p / n ] = ile jest możliwości na które można podzielić a[1 .. i] na przedziały które są parzyste, oprócz ostatniego bloku który jest parzysty [p] lub nieparzysty [n].
Jak się przypatrzysz temu rozwiązaniu to zauważysz, że wynikiem zawsze jest potęgą dwójki.
Niech P oznacza liczbę parzystą a N liczbą nieparzystą.
Rozważmy ciąg:
P | P | N P N | N N | P
Jak widzisz pionową kreską oznaczyłem wszystkie prefiksy, które są parzyste.
Ilość możliwości podziałów w takim ciągu wynosi 2^4 (bo 4 to liczba kresek).
Jeśli n <= 3000 to rozwiązanie O(n^2) ma szansę zadziałać.
Robimy algorytm dynamiczny V[i] oznacza na ile możliwości można podzielić ciąg a[1 .. i].
Każdą wartość liczymy w czasie liniowym.
Zaczynamy od ustawienia V[i] = 0
Dla każdego 1 <= j <= i patrzymy czy a[j] + a[j+1] + ... + a[i] jest mopadulu.
Jeśli tak to do V[i] dodajemy V[j-1].
Zauważmy, że gdyby modulo bylo parzyste to pytalibysmy sie o ilosc sum prefiksowych na lewo o tej samej parzystosci, to wynika z rozw w O(n^2). Teraz to co zmienia nam modulo nieparzyste to fakt, ze po obrocie zmieniaja nam sie parzystosci. Stad
jesli reszta w sumie prefiksowej jest parzysta to albo chcemy odjac mniejsza/rowna reszte parzysta albo wieksza reszte nieparzysta - i sie przekrecic raz
jesli reszta nieparzysta to na odwrot
No i takie przekrecenie wykonujemy oczywiscie max 1 - mozna sobie zapisac liczby jako k * mod + r, gdzie r to reszta.
To ile takich jest mozemy dostac np z drzewa przedzialowego sum w log n. Tylko musimy jeszcze miec przeskalowane reszty do n, bo MOD jest za duze.
jesli reszta w sumie prefiksowej jest parzysta to albo chcemy odjac mniejsza/rowna reszte parzysta albo wieksza reszte nieparzysta - i sie przekrecic raz
jesli reszta nieparzysta to na odwrot
No i takie przekrecenie wykonujemy oczywiscie max 1 - mozna sobie zapisac liczby jako k * mod + r, gdzie r to reszta.
To ile takich jest mozemy dostac np z drzewa przedzialowego sum w log n. Tylko musimy jeszcze miec przeskalowane reszty do n, bo MOD jest za duze.
Dzięki wielkie za wszystkie odpowiedzi!
dp[n] -> na ile sposobów można ogarnąć prefix o długości n
dp[n] = sum k < n dp[k] * ok(k + 1, n)
co to znaczy, że jakiś przedział jest ok?
że jego suma modulo mod daje liczbę parzystą
zauważmy, że ta parzystość nie zmienia się jak zmodulujemy sumę liczb na przedziale przez (mod * 2)
trzymamy sobie 2 drzewa przedziałowe, jedno dla prefiksów o sumie wartości parzystych, drugie o sumie nieparzystej, w punkcie jest informacja ile wynosi dp[końce takich prefiksów, że dają tę wartość modulo mod * 2]
dla jakiegoś x pytamy o przedziały w stylu [x; x + mod] na jednym drzewku i [x + mod + 1; x + 2 * mod] na drugim (oczywiście modulujemy po drodze, więc 2-3 zapytania na pozycję)
wszystko oczywiście wskaźnikowo
dp[n] = sum k < n dp[k] * ok(k + 1, n)
co to znaczy, że jakiś przedział jest ok?
że jego suma modulo mod daje liczbę parzystą
zauważmy, że ta parzystość nie zmienia się jak zmodulujemy sumę liczb na przedziale przez (mod * 2)
trzymamy sobie 2 drzewa przedziałowe, jedno dla prefiksów o sumie wartości parzystych, drugie o sumie nieparzystej, w punkcie jest informacja ile wynosi dp[końce takich prefiksów, że dają tę wartość modulo mod * 2]
dla jakiegoś x pytamy o przedziały w stylu [x; x + mod] na jednym drzewku i [x + mod + 1; x + 2 * mod] na drugim (oczywiście modulujemy po drodze, więc 2-3 zapytania na pozycję)
wszystko oczywiście wskaźnikowo
n log (n)
Niech K[i] oznacza liczbę kombinacji spełniająca warunki zadania dla przedziału [a_1...a_k]. Interesuje nas K[n], mamy dane K[0]=1 (pusty przedział istnieje na jeden sposób:)).
Aby policzyć K[j] rozważamy wszystkie odcinki [i+1...j], jeśli spałnia on warunek modparzystości, to dokładamy do K[j] wartosć z K[i] (czyliz wykły dynamik). Wartosć odcinka [i+1...j] sprawdzamy patrząc na S_i = sumy skumolowane a_i. Wartosć takiego odcinka to bedzie S[j]-S[i], liczymy mod M, a potem mod 2. Do daje nam n^2.
Przydałoby się szybciej, jakoś zbiorczo trzymać te wszytkie sumy.
Dzięki modulo
S[j] - S[i] = S[j] + M - S[i], i jeśli w tabelce S[.] mamy już wartosći mod P, takie wyrazenie jest >=0 i <2P.
Mamy więc dwa przypadki:
S[j] + M- S[i] < M, wtedy . S[j] + M- S[i] ma być parzsyte
S[j] + M- S[i] >=M, wtedy S[j] + M- S[i] ma być nieparzyste.
Te warunki przekształcają się na
S[j]< S[i]
oraz
S[j]>=S[i]
Zróbmy wiec drzewko przedziałowe, osobno dla parzystych i osobno dla nieparzystych wpisów w S[i],
ktore przechowuje wartości liczby kombinacji K dla danych indeksow i w czasie logarytmicznym pozwala
wyciagnać, Jaka jesy suma K[j] dla indeksów o S[i] < (lub wieksza) od zadanego S. I oczywiście w czasie
logarytmicznym updatujemy drzewko nowymi wartośćiami K[i].
Teraz, gdy rozpatrzujemy nowy K[j], w zzaleśnośći od parzystości S[j] odczytujemy sumę K[i] dla S[i] nieparzysty większych i parzystych mniejszych od S[j], albo parzysty większych i nieparzystych mniejszych (i trzeba się zastanowić, gdzie idą równe).
Niestety, najpierw próbowałem być za mądry (da się ro zrobić jednym drzewkiem!) i jak zaorałem kod i zaczałem pisać prościej, skończyłem 5 min przed... skończyłem poza jednem małym bugiem, ktorego znaalzłem 3min po polnocy ;-(
https://pastebin.com/RtHY3pPw (oba drzewka mają takie same indeksy jak posortowane sumy skumulowane, róznią się tylko tym, ktore k[i] w nie wpisuję, parzyste czy nieparzyste. Indeksy oryginalne tłumaczy na wspołrzędne po posortowaniu tablica tworczo nazwana indexy)
Niech K[i] oznacza liczbę kombinacji spełniająca warunki zadania dla przedziału [a_1...a_k]. Interesuje nas K[n], mamy dane K[0]=1 (pusty przedział istnieje na jeden sposób:)).
Aby policzyć K[j] rozważamy wszystkie odcinki [i+1...j], jeśli spałnia on warunek modparzystości, to dokładamy do K[j] wartosć z K[i] (czyliz wykły dynamik). Wartosć odcinka [i+1...j] sprawdzamy patrząc na S_i = sumy skumolowane a_i. Wartosć takiego odcinka to bedzie S[j]-S[i], liczymy mod M, a potem mod 2. Do daje nam n^2.
Przydałoby się szybciej, jakoś zbiorczo trzymać te wszytkie sumy.
Dzięki modulo
S[j] - S[i] = S[j] + M - S[i], i jeśli w tabelce S[.] mamy już wartosći mod P, takie wyrazenie jest >=0 i <2P.
Mamy więc dwa przypadki:
S[j] + M- S[i] < M, wtedy . S[j] + M- S[i] ma być parzsyte
S[j] + M- S[i] >=M, wtedy S[j] + M- S[i] ma być nieparzyste.
Te warunki przekształcają się na
S[j]< S[i]
oraz
S[j]>=S[i]
Zróbmy wiec drzewko przedziałowe, osobno dla parzystych i osobno dla nieparzystych wpisów w S[i],
ktore przechowuje wartości liczby kombinacji K dla danych indeksow i w czasie logarytmicznym pozwala
wyciagnać, Jaka jesy suma K[j] dla indeksów o S[i] < (lub wieksza) od zadanego S. I oczywiście w czasie
logarytmicznym updatujemy drzewko nowymi wartośćiami K[i].
Teraz, gdy rozpatrzujemy nowy K[j], w zzaleśnośći od parzystości S[j] odczytujemy sumę K[i] dla S[i] nieparzysty większych i parzystych mniejszych od S[j], albo parzysty większych i nieparzystych mniejszych (i trzeba się zastanowić, gdzie idą równe).
Niestety, najpierw próbowałem być za mądry (da się ro zrobić jednym drzewkiem!) i jak zaorałem kod i zaczałem pisać prościej, skończyłem 5 min przed... skończyłem poza jednem małym bugiem, ktorego znaalzłem 3min po polnocy ;-(
https://pastebin.com/RtHY3pPw (oba drzewka mają takie same indeksy jak posortowane sumy skumulowane, róznią się tylko tym, ktore k[i] w nie wpisuję, parzyste czy nieparzyste. Indeksy oryginalne tłumaczy na wspołrzędne po posortowaniu tablica tworczo nazwana indexy)
Można też na samym początku wykonać transformację, która (troszkę) ułatwia tego dynamika.
Całe to zadanie odbywa się w grupie addytywnej mod p, więc zastosowanie dowolnego automorfizu tej grupy na początku nie zmienia odpowiedzi. Możemy w szczególności zrobić tak (przykład dla p=11):
0 -> 0
2 -> 1
4 -> 2
6 -> 3
8 -> 4
10 -> 5
1 -> 6
3 -> 7
5 -> 8
7 -> 9
9 -> 10
To przekształcenie to po prostu x -> (6*x) % 11 czyli w jakims sensie x -> x/2 i po jego wykonaniu parzyste liczby przechodzą na <= 5, a nieparzyste na > 5. Dostajemy nowe zadanie, w którym zamiast o parzyste przedziały pytamy o <= 5 i to jest trochę mniej zamotane.
Całe to zadanie odbywa się w grupie addytywnej mod p, więc zastosowanie dowolnego automorfizu tej grupy na początku nie zmienia odpowiedzi. Możemy w szczególności zrobić tak (przykład dla p=11):
0 -> 0
2 -> 1
4 -> 2
6 -> 3
8 -> 4
10 -> 5
1 -> 6
3 -> 7
5 -> 8
7 -> 9
9 -> 10
To przekształcenie to po prostu x -> (6*x) % 11 czyli w jakims sensie x -> x/2 i po jego wykonaniu parzyste liczby przechodzą na <= 5, a nieparzyste na > 5. Dostajemy nowe zadanie, w którym zamiast o parzyste przedziały pytamy o <= 5 i to jest trochę mniej zamotane.