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%). Но мы же не хотим там оказаться, правда?
Поэтому основная проблема заключается в том, чтобы попасть в топ по времени выполнения и памяти. Например, с такими результатами:
Добавлю, что топовое решение - несколько неожиданное, и на первый взгляд выглядит, как экспонента. Но за счёт быстрого отсечения ненужных ветвей оно близко к линейному.
Что-то задели меня эти жабы, так что отвел вечер для борьбы с ними)
Решил с результатом 21мс( 99.20% ) и 26мб (85%). Вполне удовлетворен.
class Solution
{
unordered_set<unsigned> stones; //перезапись массива для быстрого поиска
unordered_map<size_t, bool> mapa; //запоминание посещений (бесит что для pair<int int> нет хеша)
int last;
public:
bool finder(pair<int, int> dat)
{
if (dat.first == last) return true;
if (dat.second<0 or !stones.contains(dat.first) or dat.first > 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<int>& stone)
{
last = stone.back();
for (auto& i : stone) stones.emplace_hint(stones.begin(), i);
}
bool check(vector<int>& 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<int>& nums)
{
if (!check(nums)) return false;
fill(nums);
return finder({});
}
}; 1 вариант без карты посещений - тайм лимит.
2 вариант добавил карту и check - 21 мс. Как оказалось
предварительная оценка check почти на 50% снижает время.
без нее - 40 мс.
Не знаю что там за фокус насчет синхронизации stdin, может было бы еще быстрее, но в целом задачи получить 8 мс не стояло, поэтому этот вариант не оптимизировал.
Ответ удалён странно, почему-то наивное решение на Go выдает лучший (чем на c++) результат по памяти...