A(
Формулу для вычисления за O(1)?
Та само решение несложное - мне стало интересно, возможно ли вывести формулу.
Та само решение несложное - мне стало интересно, возможно ли вывести формулу.
с максимумом на префиксе мне кажется никак
Size: a a a
2021 January 18
A(
ну точнее точно сложнее, чем без него
D
Формулу для вычисления за O(1)?
Та само решение несложное - мне стало интересно, возможно ли вывести формулу.
Та само решение несложное - мне стало интересно, возможно ли вывести формулу.
По моему за О(1) нет, вы же все равно элементы массива меняете раз за разом, он будет линейным
E
Ребят, а возможно как-то вывести O(1) формулу для получения числа по номеру, если знаешь принцип построения последовательности?
arr[0] = 0, arr[1] = 1
arr[2*i+1] = arr[i] + arr[i+1]
arr[2*i] = arr[i]
0 <= i <= 100
nums[i] = max(arr[0] ... arr[i])
nums:
arr[0] = 0, arr[1] = 1
arr[2*i+1] = arr[i] + arr[i+1]
arr[2*i] = arr[i]
0 <= i <= 100
nums[i] = max(arr[0] ... arr[i])
nums:
0 1 1 2 2 3 3 3 3 4 4 5 5 5 5 5 5 5 5 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 11 11 11 11 11 11 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 15 15 18 18 18 18 18 18 18 18 19 19 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21
V🇺
тут явно ошибка, наверное arr[2*i] = 2*arr[i]
будь так, было бы arr[i] == i
P
Спасибо, интересно
A
День добрый! Не могу разобраться с одной проблемой: есть кривая, заданная непоследовательными 2D-точками. Точки записаны в вектор, собственно. Как можно посортить это дело по длине от начала кривой?
Евклидово расстояние мимо, так как самая дальная точка на кривой может быть ближе всего к её началу
Евклидово расстояние мимо, так как самая дальная точка на кривой может быть ближе всего к её началу
A
технически кривых можно провести очень много. Наверно есть еще ограничение на то, что кривая должна быть достаточно гладкой
A
но если самая дальняя ближе всего к началу, то мы можем случайно получить замкнутую кривую и вообще пойти по ней в "обратную" сторону
A
собственно отличить первую точку от последней вообще никак
A
Albyc
День добрый! Не могу разобраться с одной проблемой: есть кривая, заданная непоследовательными 2D-точками. Точки записаны в вектор, собственно. Как можно посортить это дело по длине от начала кривой?
Евклидово расстояние мимо, так как самая дальная точка на кривой может быть ближе всего к её началу
Евклидово расстояние мимо, так как самая дальная точка на кривой может быть ближе всего к её началу
Мб как-то так:
1) Ищем первоначальную точку (пусть она задана по условию)
2) Берём прямую, которая проходить вдоль этой точки и пытаемся найти вторую точку, минимальноудалённую - крутим под 360
3) Соединяем и проделываем то же самое для новой точки, вычеркнув прошлую из вектора
1) Ищем первоначальную точку (пусть она задана по условию)
2) Берём прямую, которая проходить вдоль этой точки и пытаемся найти вторую точку, минимальноудалённую - крутим под 360
3) Соединяем и проделываем то же самое для новой точки, вычеркнув прошлую из вектора
A
если есть хотя бы две точки, то третью можно найти как либо наиболее близкую, либо под наиболее подходящим углом к тому, что уже было
A
например если есть точки X1 и X2, то X3 можно выбрать такой, чтобы скалярное произведение X3-X2 на X2-X1 было минимальным
A
или не, не скалярное... ну вобщем чот в этом духе
A
да, скалярное надо максимизировать чтобы "как можно дальше в том же направлении", поэтому не совсем то
A
вот модуль векторного минимизировать это больше похоже на правду
A
да, скалярное надо максимизировать чтобы "как можно дальше в том же направлении", поэтому не совсем то
Ну да, нужно придумать метрику, которая максимальна, если точки максимально близко друг к другу + в одном направлении, если направление задаётся историей. Хотя направление может резко измениться, если шаг между точками большой - никто не говорил, что они, точки, распределенны равномерно на кривой))
A
вот модуль векторного минимизировать это больше похоже на правду
P
Albyc
Ну да, нужно придумать метрику, которая максимальна, если точки максимально близко друг к другу + в одном направлении, если направление задаётся историей. Хотя направление может резко измениться, если шаг между точками большой - никто не говорил, что они, точки, распределенны равномерно на кривой))
задача не определена но вообще в пойнт клаудах вроде принято расширять евклидовый шар из точки, и те точки которые попадут в него включать в соседи
P
то есть тупо включать ближайшие точки