Przypomniałem sobie wspomniane wcześniej liniowe rozwiązanie.
Niech k będzie łączną liczbą kamieni. Okazuje się, że jednego kandydata na skok można sprawdzić w czasie O(k) (sprawdzić, czyli policzyć ile najwięcej kamieni da się zebrać wykonując daną długość skoku). Wystarczy przeiterować się po pozycjach kamieni, jeśli kamień jest na pozycji i, to zwiększamy w tablicy do zliczania komórki o indeksie i % d, gdzie d jest długością aktualnego skoku.
Przydatna będzie możliwość czyszczenia tej tablicy w czasie stałym. Jest to dosyć znana sztuczka, która polega na tym, aby w każdej komórce oprócz jej wartości, trzymać jeszcze jakieś id, które będzie świadczyło o tym czy komórka ta jest aktualna. Wtedy żeby wyczyścić tablicę wystarczy zwiększyć ostatnie id.
template<typename T>
class count_table {
private:
uint32_t last_id;
std::vector<T> value;
std::vector<uint32_t> id;
public:
count_table() : last_id(0), value(), id() {}
count_table(uint32_t n) : last_id(0), value(n), id(n) {}
T & operator [] (uint32_t i) {
if (id[i] != last_id) {
value[i] = 0;
id[i] = last_id;
}
return value[i];
}
void clear() {
last_id++;
}
};
No dobrze, ale kandydatów dalej jest potencjalnie O(n), więc łącznie mielibyśmy złożoność O(nk)... Otóż nie, okazuje się że kandydatów jest jedynie O(n / k)! Przypuśćmy, że pewne d jest kandydatem na długość skoku. Wtedy po pierwszym skoku będziemy co najmniej na pozycji d, po drugim co najmniej na pozycji 2d, po trzecim co najmniej na pozycji 3d, itd.
Przypomnę że wynik wynosi co najmniej k / 2 (wykonując skok długości 2), zatem żeby go poprawić, musielibyśmy skoczyć co najmniej k / 2 razy, a bylibyśmy wtedy gdzieś na pozycji kd / 2 lub dalej. Naturalne jest więc że zachodzi kd / 2 <= n, co prowadzi do wniosku d <= 2n / k, czyli mamy jedynie 2n / k = O(n / k) kandydatów do sprawdzenia! Każdego sprawdzamy w czasie O(k), zatem łączna złożoność to O(k · n / k) = O(n).