Moje rozwiązanie w czasie O(n log^2 n):

Najpierw zauważam, że jeśli wybiorę pewien zbiór polan, to najlepiej odwiedzić je wg rosnących a_i. Więc jeśli chcę w pierwszych k dni odwiedzić pewne polany (a1,b1), ..., (ak, bk), to liczba zebranych grzybów wyniesie:
b1 + (a2 + b2) + (2a3 + b3) + ... ((k-1)ak + bk)

To samo można napisać w takiej postaci, która nie zależy od kolejności:
suma_i b_i + suma_(i<j) max(a_i, a_j)

Teraz zauważam, że przechodząc od rozwiązania dla k dni do rozwiązania dla k+1 dni, nie opłaca się wyrzucać polan. Bo jeśli powiedzmy wyrzucimy 3 polany i zastąpimy je 4 innymi, to bardziej się opłaci wziąć te wyrzucone 3 zamiast trzech dodanych o najmniejszych a_i.

Sam algorytm: będziemy dla kolejnych dni znajdować polanę, którą najbardziej się opłaca dodać do zbioru.

Dla każdej polany chcemy trzymać x_i, czyli o ile zwiększy się suma jeśli wybierzemy tę polanę.

Początkowo x_i = b_i. Po dodaniu polany (a_m,b_m), x_i zwiększa się o max(a_m, a_i).

Wszystkie niedodane polany reprezentuję jako punkty na płaszczyźnie o współrzędnych (a_i, x_i).

W każdym kroku muszę zrobić tak:
1. znaleźć najwyższy punkt (największe x_i)
2. usunąć ten punkt (a_m, x_m)
3. wszystkie punkty na lewo od niego podnieść o a_m: (a_i, x_i) -> (a_i, x_i + a_m)
4. wszystkie punkty na prawo od niego przekształcić afinicznie (a_i, x_i) -> (a_i, x_i + a_i)

W tym celu trzymam te wszystkie punkty w pełnym drzewie binarnym posortowanym po a_i. W każdym wierzchołku wewnętrznym reprezentuję górną otoczkę wypukłą punktów poddrzewa, oraz przekształcenie afiniczne tego poddrzewa.

To pozwala znajdować najwyższy punkt wyszukiwaniem binarnym w czasie O(log n), i aplikować przekształcenia afiniczne na poddrzewach.

Po usunięciu punktu i zaaplikowaniu przekształceń afinicznych po obu stronach, muszę policzyć otoczki wypukłe w O(log n) wierzchołkach wewnętrznych. Ale dwie otoczki wypukłe można połączyć znajdując odpowiedni odcinek pomiędzy nimi (most). W każdym wierzchołku wewnętrzym drzewa trzymam tylko ten most.

Most można znaleźć patrząc na wzajemne ułożenie mostów lewej i prawej otoczki. Zależnie od tego, jak one wzajemnie się układają, można wyeliminować z rozważań połowę lewej lub połowę prawej otoczki wypukłej.

Więc szukanie jednej otoczki / jednego mostu zajmuje O(log n), a cała operacja na drzewie O(log^2 n).

A ja szukałem z ciekawości SZE w Scheduling Zoo (http://schedulingzoo.lip6.fr/), ale nie znalazłem :)

@Tomek: mógłbyś w paru zdaniach omówić swoje rozwiązanie z otoczką?

Dodam tylko od siebie, że zadanie SZE znałem ze szkoły. Jakby kogoś interesowały takie problemy to w różnych wariantach (rodzaj dostępnych maszyn; podzielność, zależność zadań; funkcja kosztu) są opisane w książce Scheduling Algorithms Bruckera.

#include "cielib.h"

int last_idx;

int hot(int T[], int i) {
__int v;
__if (last_idx < 0) {
____v = czyCieplo(T); // initial query, know nothing
__} else if (i == last_idx) {
____v = czyCieplo(T); // only change at i
__} else {
____v = czyCieplo(T); // only change at i & last_idx
____last_idx = i;
__}
__return v;
}

int main(void) {
#ifdef LOOP
for (;;) {
#endif
__int D = podajD(), R = podajR(), delta, i, randomizer = 0;
__int Lo[D], Hi[D], A[D], B[D];

__for (i = 0; i < D; ++i) {
____Lo[i] = 0;
____Hi[i] = R;
____A[i] = B[i] = R / 2;
__}

__last_idx = -1;

__for (delta = R; delta; delta = (delta != 2) ? (delta - 1) / 2 : 1) {
____for (i = 0; i < D; ++i) if (Hi[i] - Lo[i] == delta) {
______int q1, q2;

______A[i] = Lo[i];
______B[i] = Hi[i];

______if (delta == 1) {
________if (A[i] > 0) {
__________--A[i];
__________hot(A, i);
__________q1 = hot(B, i);
__________q2 = 0;
________} else if (B[i] < R) {
__________++B[i];
__________hot(B, i);
__________q2 = hot(A, i);
__________q1 = 0;
________} else {
__________exit(1); // impossible with R >= 2
________}
______} else if (++randomizer & 1) {
________hot(A, i);
________q1 = hot(B, i);
________q2 = q1 ? 0 : hot(A, i);
______} else {
________hot(B, i);
________q2 = hot(A, i);
________q1 = q2 ? 0 : hot(B, i);
______}

______if (!q2) Lo[i] = (A[i] + B[i]) / 2 + q1;
______if (!q1) Hi[i] = (A[i] + B[i] + 1) / 2 - q2;
______A[i] = B[i] = (Lo[i] + Hi[i]) / 2;
____}
__}
__znalazlem(A);
#ifdef LOOP
}
#endif
__return 0;
}

Innym przypadkiem szczególnym jest odpowiedź 2**31 i za to obcinali już tylko jeden punkt...

(ogólnie to zakres odpowiedzi jest [0..2**31] czyli akurat się w int'cie nie mieści)

Jak robi się grzyby po deszczu?
Omówienie oglądałem, ale... "no to teraz piszemy jakieś BST i już działa". To chyba była największa trudność tego zadania. Czy mógłby ktoś przybliżyć swoją ideę?

Co się chyba redukuje do:

// chodzi o to żeby zawsze przez jedynkę przejść,
// inaczej dwójka by nam od razu do zera spadała
div2(delta) === (delta != 2) ? (delta - 1) / 2 : 1

for (delta = R; delta; delta = div2(delta))
__for i in [0..d)
____if Hi[i] - Lo[i] == delta
______reduce(i) // zlożoność O(1), 2..3 zapytania

Eh, to może się nawet da bez kopca w algorytmie zewnętrznym.

W sumie to Hi[idx]-Lo[idx] jest zawsze albo ścinane tak samo na pół i to połowa identycznej wielkości nie zależnie od tego czy dolna czy górna albo do 1 albo do 0.

Więc wystarczy pamiętać czy w danym wymiarze mamy delta > 1, == 1, czy == 0.

// delta(i) === Abs(Hi[i] - Lo[i])

until all delta(i)'s <= 1: // ie. up to log(r) times
__for i in [0..D): if delta(i) > 1: reduce(i)

once more:
__for i in [0..D): if delta(i): reduce(i)

i o ile się nie mylę to nadal działa.. a złożoność chyba spadła do O(d * log r * czas_zapytania)

Gdyby się jeszcze dało bardziej zbić czyCieplo() poniżej O(log d) to by było super...

#include "cielib.h"

static int LowerMid(int lo, int hi) { return (lo + hi) / 2; }
static int UpperMid(int lo, int hi) { return (lo + hi + 1) / 2; }

void solve(int D, int R) {
__int Lo[D], Hi[D], A[D], B[D];
__int delta, idx, q1, q2, i;
__int randomizer = 0;

__for (i = 0; i < D; ++i) {
____Lo[i] = 0;
____Hi[i] = R;
__}

__for (;;) {
____delta = 0;
____idx = 0;
____for (i = 0; i < D; ++i) {
______A[i] = B[i] = UpperMid(Lo[i], Hi[i]);
______if (Hi[i] - Lo[i] > delta) {
________delta = Hi[i] - Lo[i];
________idx = i;
______}
____}

____if (!delta) {
______znalazlem(A);
______return;
____}

____// delta === Hi[idx] - Lo[idx]

____A[idx] = Lo[idx];
____B[idx] = Hi[idx];

____if (delta == 1) {
______if (A[idx] > 0) {
________--A[idx];
________czyCieplo(A);
________q1 = czyCieplo(B);
________q2 = 0;
______} else if (B[idx] < R) {
________++B[idx];
________czyCieplo(B);
________q2 = czyCieplo(A);
________q1 = 0;
______} else {
________exit(1); // impossible with R >= 2
______}
____} else if (++randomizer & 1) {
______czyCieplo(A);
______q1 = czyCieplo(B);
______q2 = q1 ? 0 : czyCieplo(A);
____} else {
______czyCieplo(B);
______q2 = czyCieplo(A);
______q1 = q2 ? 0 : czyCieplo(B);
____}

____if (q1)
______Lo[idx] = LowerMid(A[idx], B[idx]) + 1;
____else if (q2)
______Hi[idx] = UpperMid(A[idx], B[idx]) - 1;
____else {
______int r = (delta + 1) / 2;
______if (A[idx] + r < Hi[idx]) Hi[idx] = A[idx] + r;
______if (B[idx] - r > Lo[idx]) Lo[idx] = B[idx] - r;
____}
__}
}

int main (void) {
__solve(podajD(), podajR());
__return 0;
}

Kod który wysłałem (bardzo prosty, binsearch d-wymiarowy) jest O(d + liczba pętli * d) gdzie w każdej pętli są 2 albo 3 zapytania, i pętli jest O(d * log r).

Czyli O(d + 2..3 * d * log r * (d + koszt_zapytania)) czyli przy zapytaniach O(d) to jest sumarycznie O(d^2 * log r)

Od początku widziałem, że to się da zoptymalizować (ale mi się nie chciało, bo po co)...

Duża część tego O(d) wewnątrz pętli mogłaby być przed pętlą bo się zmienia tylko dla jednego indeksu pod koniec pętli. To co jest bardziej skomplikowane to znalezienie maksimum Hi[i]-Lo[i] po d, ale tu starczy zwykły kopiec.

Wtedy:
- init = O(d)
- liczba pętli = O(d * log(r))
- czas w pętli = O(log(d)) [heap.extract-max + heap.insert + O(1)]
- zapytań 2-3 na pętlę, zapytania w pętli są typu A,B lub A,B,A, gdzie A i B różnią się jedną współrzędną.
- zapytanie ostatnie z pętli i i pierwsze z pętli i+1 różnią się max dwoma współrzędnymi.

Czyli czas O(d + 2..3 * d * log(r) * log(d)) + O(2..3 * d * log(r)) zapytań == O(d log r log d) o ile potrafimy zbić koszt zapytań do O(log d).

Jeśli cielib sobie wewnętrznie trzyma kopiec z deltami (po wymiarach) i ma wskaźniki z wymiaru do miejsca w kopcu to powinno być w stanie aktualizować kopiec w czasie O(zmienione wspolrzedne * log(d)) i odpowiadać heap.find-max < previous.

Więc owszem uważam że da się O(d log r log d) z poprawionym cielib.

Odnośnie pokrycia, zacznę od wersji która przyszła mi do głowy dopiero dzisiaj :)

Nasza kluczowa tablica DP2 chce dla każdego początkowego multizbioru/ciągu n jedynek {1,1,1,...,1} i właściwego zbioru wag (np. {8,2,1}) przechować liczbę sposobów (mod 2) na ile jesteśmy w stanie przeredukować {1,1,1,...,1} w {8,2,1}. Dla ustalenia uwagi, jeśli nasze redukcje będą brać pierwszą parę równych wag z lewej, to każdy ciąg redukcji dla n jedynek sprowadza się do redukcji pierwszych n-1 jedynek aż dojdziemy do właściwego zbioru, dołożenia ostatniej jedynki i redukowania dalej. Możemy więc przeiterować po wszystkich zbiorach "nieparzyście wiele razy otrzymanych" z n-1 jedynek, dla każdego z nich dołożyć jedynkę i dopisać do DP2 wszystkie właściwe zbiory otrzymane z tego nowego multizbioru.

Ale wszystkie zbiory "nieparzyście otrzymane" z n-1 jedynek możemy wziąć z DP2[n-1] :) Dla każdego z nich (np. {8,2,1}), multizbiór po dołożeniu ostatniej jedynki ({8,2,1,1}) może "nieparzyście zredukować się" do co najwyżej log n zbiorów ({8,2,1}, {8,2}, {8,4}), co daje zgrubne O(n log n) na obliczenie rzędu DP2[n] z rzędu DP2[n-1]. Ale po przyjrzeniu się bitom [1], okazuje się że tak naprawdę jest to O(n), i wypełnienie całej tablicy DP2[n][n] zajmie O(n^2) czasu z małą stałą. Cały kod: http://pastebin.com/wtxhLesW

Na zapytania można odpowiadać w czasie log n jak w opracowaniu (i kodzie powyżej), albo [EDIT: zignorujcie, bez przygotowania też amortyzuje się do O(1)/zapytanie jeśli pytamy o wszystkie możliwe k dla zadanego N] całkiem zbić złożoność przygotowując odpowiedzi offline, korzystając z [1] - to daje całkowity czas O(n^2 + Q).

Moje zasubmitowane rozwiązanie ma przy ograniczeniach z zadania pesymistyczną złożoność o chyba jeden log więcej, ale pozwalało na obliczenie pojedynczego rzędu DP2 (włącznie z wykorzystywanymi rzędami) w czasie O(n log n). Korzystało z obserwacji przedstawionej przez Krzysztofa - jako startowe multizbiory dla n=13 nie rozpatrywałem 13 jedynek ({1,1,....1}), tylko zbiory {a_1, a_4, a_8}, gdzie a_8 jest pojedynczym wierzchołkiem, który możemy "nieparzyście otrzymać" z grupki ośmiu jedynek itd. Ponownie, wszystkie nieparzyście otrzymane zbiory ze wszystkich {a_1, a_4}, to dokładnie DP2[5]. Tym razem zamiast dokładania jednej jedynki, musimy rozpatrzeć wszystkie potencjalne a_8, stąd dodatkowy log.

Zdecydowanie jedno z moich ulubionych zadań :)

[1] Tylko co druga liczba ma na końcu jedynkę, tylko co czwarta ma dwie, itd.

To ja napiszę luźne uwagi o zadaniu Ciepło-Zimno.

Omówienie zadania proponuje rozwiązanie wykonujące około 2d · (log d + log r) zapytań, którego złożoność obliczeniowa wynosi O(d · liczba zapytań) = O(d^2 · (log r + log d)). Wydaje mi się, że można zaproponować rozwiązanie wykonujące około 2d · log r zapytań, którego złożoność obliczeniowa wynosi O(liczba zapytań) = O(d · log r). Pewnie zresztą część z Was wysłała właśnie takie rozwiązanie.

Słabym punktem całego procesu pozostają wielokrotne wywołania funkcji czyCieplo, z których każde wykonuje się w czasie O(d). Jeśli uwzględnić złożoność wywołań funkcji czyCieplo w całym algorytmie, to rozwiązanie wzorcowe będzie miało złożoność O(d^3 · (log r + log d)), natomiast rozwiązanie szybsze - złożoność O(d^2 · log r).

W moim rozwiązaniu można jednak ułatwić pracę funkcji czyCieplo, podając oprócz aktualnej pozycji również listę wymiarów, w których współrzędne zmieniły się od ostatniego wywołania funkcji. Dzięki temu amortyzowana złożoność pojedynczego wywołania funkcji czyCieplo spada do O(log d), a złożoność całego rozwiązania z uwzględnieniem złożoności funkcji czyCieplo wynosi O(d · log d · log r).

Postanowiłem przerobić bibliotekę cielib tak, aby można było podpowiadać jej, które współrzędne zmieniły się od ostatniego razu. Testy 100 razy większe niż limit ustalony w zadaniu (d=50000 zamiast d=500) zajmują mojemu laptopowi około 4s. W przypadku niezmienionej biblioteki cielib potrzeba na to 1m14s, jednak o ile dobrze rozumiem omówienie wzorcowego rozwiązania, to opisany tam algorytm wykonywałby się ze dwie godziny? (Rozwiązanie z przerobioną biblioteką w 1m20s potrafi rozwiązać losowy test wielkości d=1'000'000, używając 62'000'000 zapytań.)

Jeśli nie macie nic lepszego do roboty, to tu jest zip z implementacją mojego algorytmu (w wersji z przerobioną biblioteką cielib) i z przykładowym testem dla d=50000: https://www.plustransfer.com/download.php?id=d704b6872f40b0b9cbce95e155a5e32d
Można to wszystko zbudować w standardowy sposób:
g++ -std=c++11 -O2 fast_cielib.c fast_cie.cpp -lm -o fast_cie
Kod praktycznie nie ma komentarzy, więc jeśli ktoś będzie go próbował przeczytać, to żeby nie było że nie ostrzegałem.

Czy ktoś z Was potwierdza, że jego rozwiązanie ma lepszą złożoność niż wzorcowe? Czy może coś gadam od rzeczy?

No, pechowo.

Co do doboru testów to mam wrażenie, że chyba jury stara się generalnie dawać częściowe punkty bardziej za poprawne ale wolne rozwiązania, a nie za rozwiązania błędne w niektórych przypadkach.

P.P.S @Tomek Moim zdaniem osiągnięcie jakiejkolwiek znaczącej liczby punktów nie testując jest prawie niemożliwe :P

Uznałem, że ręczne sprawdzenie całej ścieżki dla n<=2 wystarczy, ale nie zauważyłem, że na końcu powinno być (0, 1) zamiast (1, 0) (całkiem podobnie wyglądają). Jak sprawdziłem ręcznie, to uznałem, że w sumie to nie ma potrzeby pisania bruta (bardzo nie chciało mi się go pisać), zwłaszcza jak działa na testach Marka (bo jakby coś w rekurencji nie działało, to byłoby duże prawdopodobieństwo, że coś pójdzie nie tak). Wydaje mi się, że te decyzje brzmiały wtedy rozsądnie.

Jednak nauczyłem się, że sprawdzanie ręczne jest beznadziejne, bo brut by dał inną odpowiedź.

P.S Brut też jakiś ładny chyba nie jest