SS
Nikolay
Есть 2 строки. Над одной из них можно делать одно из 3х действий - удалить символ, изменить символ, вставить. Надо проверить , что из них можно сделать равные строки
Так это 3 задачи
Size: a a a
2020 August 20
SS
На каждое из действий
N
Буйный Виталя
Изменить на любой какой захочется? Или местами менять?
Да, но действие только одно. Это как расстояние ливенштейна равно 1 между словами.
EZ
Nikolay
Да, но действие только одно. Это как расстояние ливенштейна равно 1 между словами.
посчитай расстояние левенштейна, если получаешь больше 1, то нет
N
посчитай расстояние левенштейна, если получаешь больше 1, то нет
Есть предположение , что можно проще решить. Не хочется писать универсальный алгоритм
EZ
Nikolay
Есть предположение , что можно проще решить. Не хочется писать универсальный алгоритм
Ну для начала проверь длину, это тебе даст действие
EZ
Потом на первом несовподающем примени его
2020 August 22
J
банные алгоритмы, как же я устала
S
Выпуклая оболочка ведь за O(NlogN) решается?
(если учитывать что сортировка выполняется за O(NlogN))
(если учитывать что сортировка выполняется за O(NlogN))
A
Можно за k*n - иногда быстрее
S
Можно за k*n - иногда быстрее
Можно линк на paper или название метода?
S
A
Такого не знаю, вроде как
А в чем проблема?
А в чем проблема?
S
Такого не знаю, вроде как
А в чем проблема?
А в чем проблема?
Показалось в какой-то момент, что придумал идею как сделать выпуклую оболочку за линию.
Однако не был уверен, что её стоит додумывать.
Однако не был уверен, что её стоит додумывать.
A(
А за линию без учёта ребёр на оболочке есть?
нет, ибо к ней можно свести задачу сортировки
A(
или наоборот, я что-то неверно сказал кажется, но что-то около того
A(
а да взять точки (a[i], a[i]^2) вроде
A
Можно решить задачу two closest points на линии за O(n)? каким-нибудь хитрым рандомизированным алгоритмом, к примеру?
Т.е. просто даны n чисел и нужно найти два ближайших по модулю
Т.е. просто даны n чисел и нужно найти два ближайших по модулю
2020 August 23
NB
Можно решить задачу two closest points на линии за O(n)? каким-нибудь хитрым рандомизированным алгоритмом, к примеру?
Т.е. просто даны n чисел и нужно найти два ближайших по модулю
Т.е. просто даны n чисел и нужно найти два ближайших по модулю
Если координаты точек - целочисленные - отсортировать поразрядной сортировкой.