AP
уверен что можно за О(1) сделать, в худшем случае за логарифм
за O(1) это без просмотра входных данных? это сильно...
Size: a a a
2020 December 10
к
а я не знаю че за задача, я просто увидел выше фибоначчи на три элемента и предположил что наверняка должен быть O(1)
AP
не знаю про две минуты, я полчаса тупил 8)
я — с пол дня :)
AL
Но ведь для чисел фибоначчи не бывает O(1)
AP
Но ведь для чисел фибоначчи не бывает O(1)
да есть там левая формула с вещественными числами. Она не совсем точная, но на практике работает...
A
ну вот "фибоначчи на три элемента" это нечто, что получилось после примерно получаса размышлений с листочком бумаги
AL
да есть там левая формула с вещественными числами. Она не совсем точная, но на практике работает...
Мало ли что формула
AL
На заборе тоже формула написана
AL
Асимптотика времени вычисления этой формулы как раз логарифм есличо
AP
ну вот "фибоначчи на три элемента" это нечто, что получилось после примерно получаса размышлений с листочком бумаги
мы с коллегой вначале написали почти такую же формулу как у вас ( с точностью до базовых случаев), но потом в итоге выбросили. А что у вас
x? Количество единиц между тройками? У меня в итоге осталась формула, которая только один рекурсивный вызов делает, но я сам не понимаю как она работает, просто после длительного смотрения на примеры написалось...A
длина группы, в которой разность между соседними элементами равна 1.
AP
Асимптотика времени вычисления этой формулы как раз логарифм есличо
с моей точки зрения, если нет рекурсивного вызова, то сложность константная
AL
Но ведь возведение в огромную степень это не константа
A
собственно наблюдение показало, что расстояния есть 1 и 3, расстояний 2 во входных данных нет. Получаются блоки, у которых первый и последний должны присутствовать, а промежуточные можно как-то повыбрасывать без потери валидности.
A
для корректности получается, что впереди к списку я добавил 0, потому что "группа", которая начинается с 1 должна включать такой "фиксированный ноль" впереди
AP
Но ведь возведение в огромную степень это не константа
вообще, да, я забыл про степень. согласен
A
на примере, который там в тексте задачи приведен:
(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, (22) разбивается на (0 1) (4 5 6 7) (10 11 12) (15 16) (19) - 22 можно не писать, оно всегда на 3 больше конца последней группы.
(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, (22) разбивается на (0 1) (4 5 6 7) (10 11 12) (15 16) (19) - 22 можно не писать, оно всегда на 3 больше конца последней группы.
A
по длинам групп 2 4 3 2 1. Функция "фибоначчи на 3 числа" даст для них значения 1 4 2 1 1, которые надо перемножить и получается ответ 8.
A
по второму примеру получилось
AP
на примере, который там в тексте задачи приведен:
(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, (22) разбивается на (0 1) (4 5 6 7) (10 11 12) (15 16) (19) - 22 можно не писать, оно всегда на 3 больше конца последней группы.
(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, (22) разбивается на (0 1) (4 5 6 7) (10 11 12) (15 16) (19) - 22 можно не писать, оно всегда на 3 больше конца последней группы.
да, разбивать на группы очевидно, надо, просто я разбивал на группы уже разности (1 или 3), а не сами числа.