Leetcode истребляет лягушек. 403. Frog Jump. Штурмуем топ.

Нет, это не HTTP 403 Forbidden, это просто номер задачи.

Итак, кто из олдскула помнит игрушку "Frogger", где надо было перепрыгнуть дорогу и реку и не попасть под машину или в пасть крокодилу и не утонуть, тому будет проще понять условие.

На вход дан упорядоченный список с позициями камней, расположенных вдоль оси (т.е. у них одна координата). Первый камень имеет позицию 0, второй - 1 (есть тесты, где это не так, и тогда надо возвращать неудачу).

Лягушка прыгает сначала на 1 позицию (с камня 0 на камень 1), а дальше она может прыгнуть на k - 1, k или k + 1 позиций, где k - длина её предыдущего прыжка (у неё есть инерция, и как видно из тестовых данных, лягушка может развивать космические скорости). Камней - не более 2000 шт, номера позиций - от 0 до INT_MAX.

Нужно вернуть true, если лягушка сможет доскакать до последнего камня, и false - если не сможет.

Уровень Hard. Полный текст задачи тут:
https://leetcode.com/problems/frog-jump/description/

Один из коварных тест кейсов полностью не может быть приведёт в силу объёма, поэтому выложен тут:
https://pastebin.com/BjBDigaf
Видим, что лягуха достигает последнего камня со скоростью, в 999 раз превышающей её начальную скорость. Это не снилось и сверхзвуковому истребителю, если принять скорость в начальном прыжке за 1 м/с.

"А я знаю, а я знаю, тут надо применять динамическое программирование" - скажет прошаренный алгоритмист... и получит от 80 до 1000+ ms execution time и чудовищный перерасход памяти, заняв почётное место в клубе посредственностей (82%) или лузеров (7%). Но мы же не хотим там оказаться, правда?

Поэтому основная проблема заключается в том, чтобы попасть в топ по времени выполнения и памяти. Например, с такими результатами:
Добавлю, что топовое решение - несколько неожиданное, и на первый взгляд выглядит, как экспонента. Но за счёт быстрого отсечения ненужных ветвей оно близко к линейному.

 class Solution 

{ 

	unordered_set stones; //перезапись массива для быстрого поиска 

	unordered_map mapa; //запоминание посещений (бесит что для pair нет хеша) 

	int last; 

public: 

	bool finder(pair dat) 

	{ 

		if (dat.first == last) return true; 

		if (dat.second last) return false; 

		if (!mapa.contains((size_t&) dat)) mapa[(size_t&)dat] = 

		(dat.second > 0 ? (finder({dat.first + dat.second, dat.second 

			}) or finder({ dat.first + dat.second - 1, dat.second - 1 })) : false)  

			or finder({ dat.first + dat.second + 1, dat.second + 1 }); 

		return mapa[(size_t&)dat]; 

	} 

 

	void fill(const vector& stone) 

	{ 

		last = stone.back(); 

		for (auto& i : stone) stones.emplace_hint(stones.begin(), i); 

	} 

 

	bool check(vector& nums) //предварительная оценка возможности прыжков  

	{ 

		int i = 0; 

		int max_dist = 0; 

		for (auto j = nums.begin() + 1; j != nums.end(); ++j) 

		{ 

			++i; 

			max_dist += i; 

			if (*j - *(j - 1) > max_dist) return false; 

		} 

		return true; 

	} 

 

	bool canCross(vector& nums) 

	{ 

		if (!check(nums)) return false; 

		fill(nums); 

		return finder({}); 

	} 

};