Pochwali się ktoś?

+1
Ja prawie miałem n*log^2(n), ale nagle mózg mi zaczął pękać, więc zostałem przy n^2logn :(.

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).

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).

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?

@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ę).

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)).

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

@Jakub Kądziołka

> dlaczego zbiór wartości k, dla których odpowiedź <= x, jest przedziałem
Niech f(k) będzie funkcją wyniku od k. Gdybyśmy nie zwracali uwagi na k, to optymalnie jest wziąć tańszy obraz z każdej pary - powiedzmy, że w takiej sytuacji wybralibyśmy k0 obrazów Alicji. Twierdzimy teraz, że f(k) jest nierosnąca dla k <= k0 i niemalejąca dla k >= k0. Dlaczego jest nierosnąca dla k <= k0? Jeśli mamy optymalny ciąg dla f(k) dla k < k0, to na pewno możemy zamienić w nim jeden obraz Boba na tańszy obraz Alicji (bo wzięliśmy k obrazów alicji, a jest k0 par z tańszymi od Boba). Jeśli go podmienimy to dostaniemy niegorsze rozwiązanie dla k+1, zatem f(k) >= f(k+1) dla każdego k <= k0. Dla k >= k0 analogicznie. W takim razie jak binsearchujemy, to przedział wartości k będzie spójny.

> dlaczego rozwiązanie zachłanne działa
Nie mam tu szybkiego argumentu niestety, wyszło po dłuższym kminieniu że "powinno być OK", więc naklepałem go w O(n^2 log n) i sprawdziłem, że działa xd.

Co do powyższych pytań o poprawność, to pozwolę sobie wspomnieć niezwykle pomocne stwierdzenie, że jak się zrozumie o co chodzi z tym wypukłym DP, to oba te claimy są oczywiste xD

Ja robię podobnie jak Jacek:

Wybieram najtańsze obrazy. Teraz wiem ile mam zamienić z B na A (lub odwrotnie).

Wyszukuję binarnie najmniejszy koszt. Za każdym razem jadę od lewej do prawej, trzymając wartość największego sufiksu (bez poprawek), oraz zbiór możliwych poprawek z B na A. Sprawdzamy, czy uda się zrobić odpowiednią liczbę poprawek, mieszcząc się w koszcie.

Jeśli sufiks stanie się ujemny, to zeruję sufiks, ale przy okazji "za darmo" akceptuję najmniej kosztujące poprawki. Jedna z poprawek nie zostanie w pełni zaakceptowana, ale jej koszt się zmniejszy.

Jeśli sufiks + suma wszystkich poprawek jest za duża, to odrzucam najbardziej kosztowne poprawki.

Na końcu akceptuję wszystkie pozostałe poprawki.

Jelle van Vucht, better known online as Jelly, is a Dutch YouTuber known for his gaming videos and vlogs. Jelly was a member of the group Robust along with Slogo, IamSanna, and Kwebblekop, but now he plays with Crainer and Slogo instead of Kwebbelkop. The Netherlands-based gamer is one of the most-streamed content creators on the planet. Buy Official Jelly Merch here! #jellymerch #jellymerchandise #jellytshirt
Website: https://www.jellymerch.net/
Others Website link:
https://www.behance.net/jellymerch
https://medium.com/@jellymerch
https://www.buzzfeed.com/jellymerch
https://www.goodreads.com/user/show/155934572-jelly-merch
https://www.wattpad.com/user/jellymerch
https://www.figma.com/@jellymerch
https://www.quora.com/profile/Jelly-Merch
https://hubpages.com/@jellymerch
https://seekingalpha.com/user/57203670/comments
https://www.minds.com/jellymerch/
https://www.producthunt.com/@jellymerch
https://angel.co/u/jelly-merch
https://www.pearltrees.com/jellymerch1
https://www.deviantart.com/jellymerch