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

Question

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

Папа Высший разум (154448), закрыт 1 год назад

Нет, это не 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%). Но мы же не хотим там оказаться, правда?

Поэтому основная проблема заключается в том, чтобы попасть в топ по времени выполнения и памяти. Например, с такими результатами:

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

Answer 1

Что-то задели меня эти жабы, так что отвел вечер для борьбы с ними)
Решил с результатом 21мс( 99.20% ) и 26мб (85%). Вполне удовлетворен.

 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<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& 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({}); 
	} 
};

1 вариант без карты посещений - тайм лимит.
2 вариант добавил карту и check - 21 мс. Как оказалось
предварительная оценка check почти на 50% снижает время.
без нее - 40 мс.
Не знаю что там за фокус насчет синхронизации stdin, может было бы еще быстрее, но в целом задачи получить 8 мс не стояло, поэтому этот вариант не оптимизировал.

Answer 2

Терр Онтал Мудрец (14570) 1 год назад

странно, почему-то наивное решение на Go выдает лучший (чем на c++) результат по памяти...

ПапаВысший разум (154448) 1 год назад

С рекурсией, что ли? Что-то не вижу, как там в Go переключиться.

Терр Онтал Мудрец (14570) Папа, нет, дп как раз