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?

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

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

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

#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;
}