Potwierdzam

Potwierdzam.

Moje rozwiązanie wydaje mi się prostsze od obu opisanych wyżej (EDIT: oho, oczywiście jak to pisałem to się pojawiło parę nowych postów xd). Co prawda główna linia ataku taka sama, ale szczegóły uproszczone - w szczególności mam tylko jednego prostego seta. Aczkolwiek niestety jakoś nie jestem w humorze do dokładnego opisywania - wybaczcie - dlatego wrzucę jedynie kod https://ideone.com/CCvgl0 z krótkim poniższym komentarzem.
To co ja trzymam na tym secie to kolejne różnice pomiędzy wartościami wypukłego DP, które opisuje Bartek (tzn. to pierwsza współrzędna par w tym secie, bo druga to z którego miejsca pochodzi dany przedmiot - bo o dziwo - każda z tych różnic bierze się po prostu z któregoś konkretnego przedmiotu, a jest mi to potrzebne do odzyskania wyniku). Do tego trzymam jeszcze sumę liczb na secie i jakąśtam zmienną "shift". Summa summarum, wartość dp[k] (dla aktualnego prefiksu), to suma pierwszych k liczb na tym secie oraz właśnie tej zmiennej shift.
Btw imho 2A było dużo trudniejsze

Ja robiłem tak jak Krzysztof, ale chyba mam prostszego zachłana: trzymam seta par S={ile zyskam na zmianie B[idx]->A[idx]}. Ide po elementach B[i] i trzymam maksymalny sufiks obecnie, oraz wrzucam B[i]-A[i] do S. Jeżeli przekroczyłem maksymalnym sufiksem x to probuje za pomoca zmian, od najwiecej dajacych, zbic maksymalny sufkis do co najwyzej x.

Jeżeli obecny maksymalny sufiks to t, to nigdy nie uda mi sie go zbic ponizej zera, wiec musze wyrzucic elementy z S, od najmniejszego, tak zeby sumarczny zysk, ktory moglbym uzyskac byl co najwyzej t.

Z konstrukcji algorytmu widac, że wezme minimalna liczbe elementow z A (czyli znajde Kmin).

Złożoność: O(n log n log (nMAXA)).

@Bartłomiej Czarkowski Ja miałem dokładnie takie rozwiązanie, ale obserwacja jest taka, że możemy to robić na zwykłym secie różnic i kod jest bardzo krótki (około 20-30 linijek na tą funkcję).

Krzysztof – Umiesz jakoś uzasadnić, dlaczego zbiór wartości k, dla których odpowiedź <= x, jest przedziałem i dlaczego rozwiązanie zachłanne działa?

Mogę podzielić się zarysem rozwiązania, którego niestety nie byłem wstanie zaimplementować na czas. Zakładamy na początku, że bierzemy zawsze ten obraz który ma mniejszą wartość i dostajemy problem, gdzie musimy podmienić dokładnie K' obrazów na droższy (tylko jakiś podzbiór można podmieniać). Robimy binsearch po wyniku. Postaramy się przyspieszyć następujące DP[i][j] oznaczające minimalną wartość sufiksu o największej wartości na prefiksie od 1 do i zakładając, że podmieniliśmy już j obrazów. Dla stałego i kolumna tego DP jest wypukła, z czego skorzystamy. W przejściach DP możemy wypchnąć jakąś parę (i, j) do (i + 1, j) lub (i + 1, j + 1). Nie wchodząc w większe szczegóły sprowadza się to do zrobienia operacji max z 0 na wektorze, dodanie jakiejś stałej na nim i zmaxowanie do z samym sobą przesuniętym o 1 i zwiększonym o stałą (przejście do (i + 1, j + 1)). Takie połączenie jest zwykle nie do zrobienia na jakiejś strukturze, ale dlatego że obydwa mergeowane wektory są wypukłe, wynik to będzie prefiks jednego i sufiks drugiego, co możemy zrobić na treapie. Z informacji o długości tych prefiksów przy przecięciu można też odzyskać ciąg tych podmian. Sry, jeżeli zbyt ogólnikowo i jeżeli to w ogóle nie działa, bo ostatecznie jednak tego nie naklepałem.

Złożoność czasowa to O(n log^2 n).

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)

Binsearchujemy wynik. Żeby stwierdzić czy wynik jest <= x, znajdziemy sobie przedział [Kmin,Kmax] wartości k, dla których da się uzyskać wynik <= x. Powiedzmy, że chcemy ustalić Kmin, upperbound Kmax robimy symetrycznie.

Kmin znajdujemy konstruując rozwiązanie zachłannie, dodając kolejne obrazy do ciągu, tak by mieć cały czas jak najmniej obrazów Alicji. Gdy dodajemy kolejny obraz, to najpierw dodajemy obraz Boba. Jeśli nic się nie zepsuło to kontynuujemy. Jeśli coś się zepsuło to zepsuło się to, że max suma sufiksu > x. W takim wypadku, znajdujemy obraz Boba w ciągu, którego podmiana na obraz Alicji zmniejszy jak najbardziej maksymalną sumę sufiksu. Jeśli takiego obrazu nie ma to od razu zwracamy, że nie da się rozwiązania <= x uzyskać. Robimy takie podmiany dopóki max suma sufiksu nie spadnie do x lub niżej.

Teraz kwestia jak taki zachłan zaimplementować szybciej niż O(n^2). Po pierwsze będziemy potrzebowali szybko sprawdzać o ile podmiana obrazu poprawia max sumę sufksu. W tym celu trzymamy drzewko przedziałowe nad aktualnym ciągiem, które umożliwia nam zmienianie liści i pytanie o max sumę sufiksu.

Podzielmy sobie kandydatów na podmiany na 2 rodzaje. Powiedzmy, że możemy pewien obraz B podmienić na A i max suma sufiksu zmniejszy się po tym o C. Pierwsza sytuacja to taka, że C = B-A. Druga opcja to C < B-A. Jeśli kandydat jest w tej drugiej kategorii, to już nie wróci do pierwszej. Pozwala to trzymać kandydatów z pierwszej kategorii w kolejce priorytetowej sortowanej po B-A, i leniwie ich przerzucać do kategorii drugiej, gdy się okaże, że C < A-B (C sobie drzewkiem liczymy). Gdy szukamy kandydata na podmianę z pierwszej kategorii, to opłaca się najbardziej wziąć ten z wierzchu kolejki, który ma największe B-A. Jeśli natomiast kandydat należy do drugiej kategorii, gdzie C < A-B, to okazuje się że im jest dalej na prawo, tym większe jest C. W takim razie dla nich trzymamy sobie kolejkę sortowaną po pozycji w ciągu, by szybko znaleźć ten najbardziej na prawo. W ten sposób, będziemy sprawdzać tylko 2 kandydatów na podmianę.

Pozostaje jeszcze zrekonstruować ciąg. Po binsearchu mamy wynik x i przedział [Kmin;Kmax], dla którego optymalne odpowiedzi wszystkie są równe x. Dodatkowo zachłan ubocznie daje nam ciągi dla Kmin i Kmax. Zawsze jedno z nich możemy przekształcić do ciągu dla naszego docelowego k, podmieniając jedynie obrazy na tańsze - co nie pogorszy wyniku.

Całość działa w O(n log^2 n).

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

A tak w ogóle to outy potwierdzam, dobre są.

Dzięki wielkie za wszystkie odpowiedzi!

Potwierdzam

Potwierdzam.

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.