xmoonlight, Особенность этого варинта в безразмерности. Т.е. если вы растянете все числа так, что любое расстояние между соседними больше года или сожмете все точки в одну микросекунду, разбиение на кластеры будет точно таким же.
Если в вашей задаче это не вяжется, можно вместо просто после сортировки отсечь по какой-то выбранной вами константе.
Никита, Если массив упорядочен по убыванию, то каждая пара чисел даст инверсию. Всего пар n(n-1)/2. В int помещается 2^31. Решаем уравнение n(n-1)/2=2^31. Или n(n-1)=2^32. Для больших чисел можно грубо прикинуть просто взяв корень, получим, что n~2^16=65536. На самом деле ответ где-то между 65536 и 65537, т.е. я на 1 ошибся - для переполнения нужно 65537 упорядоченных по убыванию чисел.
У вас в задаче может быть 100 тысяч чисел, что больше 65 тысяч, поэтому на максимальном тесте ваше решение переполнит счетчик инверсий и выдадет неправильный ответ.
Поменяйте number_of_inversitions на 64-битный тип и должно заработать.
xmoonlight, Можно жадно - не надо даже дихотомии и динамики. Отсортируйте все соседние расстояния и сливайте эти 2 соседних числа в один кластер, считая метрику.
В вашем примере сначала объединим 9.5 и 10 (разность 0.5), потом 8 и 8.7 (0.7), потом 8.7 и 9.5 (0.8), потом 5 и 6 (1). При слиянии смотрите отношение текущего расстояния и следующего и минимум его тут 1/2.
Можно даже не сливать по пути, а просто найти все разности, отсортировать, найти пару с максимальным отношением и запомнить большее. Потом все точки, с расстоянием меньше этого числа - объединить в один кластер за еще один проход.
xmoonlight, максимальное расстояние между соседними берется по всем кластерам. Да, в {8, 8.7, 9.5, 10} расстояние 0.8, но есть же еще {5, 6}. Идея в этой метрике - мы смотрим как близко точки бывают в одном кластере и как близко бывают точке вне кластеров. Эти 2 множества должны быть хорошо разделены - в кластрерах точки рядышком, а сами кластеры далеко друг от друга.
Требование иметь хотя бы 2 точки в кластерах не влияет на подсчет метрики, и его нужно включить в алгоритм. Например, во время динамики вы не смотрите на варианты, когда последний кластер состоит из одной точки - и все.
Например в {1, 3, 5, 6, 8, 8.7, 9.5, 10, 12}, если разбить на {1, 3, 5, 6}, {8, 8.7, 9.5, 10}, {12}, то максимальное расстояние в кластере между соседними будет 2 (5-3), а расстояние между кластерами - тоже 2 (8-6 или 12-10). Итого метрика - 2/2=1.
Если разбить {1}, {3}, {5, 6}, {8, 8.7, 9.5, 10}, {12}, то максимальное расстояние между соседними будет 1 (это для каждой точки берем минимум по всем в том же кластере, а потом из этого всего берем максимум). А минимальное расстояние между кластерами будет 2 (тупо минимум по всем парам из разных кластеров). Итого метрика 1/2 лучше. Но тут если количество кластеров не ограничено, то можно вообще каждую точку отдельным кластером сделать и будет 0.
xmoonlight, Нет, непонятно. Может эти числа - это числовое обозначение цвета тома словаря, в котором это слово описывается. То, что зеленый выпал на 11, а красный на 12, и они как бы рядом - просто повезло.
Или вы делаете фильтр мата и эти числа - это какая-то мера матерности слова. В этом случае вам нужно именно 2 кластера.
Еще раз - без физического смысла величины и цели кластеризации - вопросы о корректности и оптимальности кластеризации не имеют смысла.
Magneto903, Нет, достаточно простой двоичной кучи. с Фиббоначиевой там получше ассимптотика чуть чуть, но это имеет смысл делать только если у вас очень много ребер. В вашем же графе это не нужно.
Осталось реализацию дейкстры исправить не с массивом visited самих номеров вершин и линейным поиском в нем, а массив из N пометок 0/1.
Там уже сложность операций в множителе 10 заложена. Попробуйте инкрементировать переменную.
Ну и, 400ms значит, что вы 40% времени будете тратить на эти поиски. Если построение графа в оставшиеся 60% влезает, то вы все успеваете.
Magneto903, javascript - боль. Ну блин, там в дейкстре надо 160 раз пройтись по всем вершинам и выбрать минимум, переписать пару значений в массивах и пройтись по всем ребрам суммарно по одному разу. У вас там что, цикл до 160*160*60*10=15m целую секунду выполнятся будет?
Поищите другую реализацию, без всяких объектов, преобразования к строкам.
Хотя, у меня вообще подозрение, что операция ```visited.includes(node)``` выполняется за линию в shortestDistanceNode. Что там за ```let visited = []``` в которую делается ```visited.push(node)```? это же массив, да? Если вместо этого использовать тупо массив из 160 булов и там помечать обойденность вершины, то будет работать в ~160 раз быстрее. Или на Set заменить хотябы.
Adamos, Вам следует изменить свой ответ, чтобы явно указать. что это будет приближение, а не оптимальный ответ. Не все заглядывают в комменты и ваш ответ в таком виде ошибочен.
Magneto903, Ну вот есть у вас несколько самых далеких вершин от двух красных ботов, по разные стороны от зеленого. куда ему бежать?
Да, кстати, а кто за кем гоняется? у каждого зеленого бота свой красный, или красный гонится за ближайшим зеленым?
Так-то дейкстра на 160 вершинах 60*4 раз в секунду особо не должна нагружать ничего. Тем более, если с кучей делать. Можно в 100 раз больше в секунду успесть сделать на не самом мощном железе. Что-то у вас не так, возможно, в релизации.
Но, попробуйте флойдом на статичном графе. Еще предподсчитайте для каждой вершины самую далекую. Тогда приближение для красных вершин будет перебрать все исходящие ребра, прибавить к ним расстояние до самой далекой в графе и из этих чисел брать максимум. Потом вам надо для каждой зеленой и каждой самой далекой точки найти путь. Опять же, просто для зеленой перебирайте все ребра и берите минимум из длина ребра + длина пути в матрице.
Да, самые далекие точки нужно только статические смотреть.
A* дает неплохой прирост в скорости, когда у вас есть конечная вершина. А тут вам надо найти расстояния от одной до всех, чтобы найти самую далекую точку. Можно второй этап заменить А* вы из самой далекой вершины идете к зеленой.
Но вообще, нужно же всего 2 дейкстры, на самом деле. Одна - найти самую далекую вершину от всех красных. Вторая - нужно найти кратчайшие пути от этой самой далекой до всех вершин графа. И вы сразу нашли пути для всех зеленых.
Можно схалтурить и проннать флойда только для статичных вершин, а потом для поиска самой далекой вершины просто припихать каждую красную к ближайшей соседней статичной вершине. А потом просто перебрать все вершины, посчитать расстояния по матрице флойда и взять максимум.
А для зеленых - нужно просто перебрать все ребра и взять то, путь через которое до конечной наикротчайший.
Этот жадный алгоритм не работает. Тут вообще нет жадности.
вот пример 2 станка, 5 работ {10,9,3,2,2} - ваш алгоритм вернет {{10,2},{9,3,2}}. максимум 14. Хотя можно 3 положить не к 9, а к 10, и получить {{10,3},{9,2,2}} - максимум 13.
То, что вычисления совпали у меня в firefox но не у вас говорит лишь о том, что firefox оптимизирует возведение в целую степень через логарифмы, а chrome - считает через ряды. Custom функция чуть ближе к правде, но все-равно 10-ый знак вычислен не правильно.
Видимо, в хроме менее точно работает возведение в степень. Вернее, с другой ошибкой. Ошибка в 11 знаке для степени почти миллион - выгладит не страшным багом.
float дело такое... Достаточно порядок операций поменять и чуть по другому считать, и уже ошибка в другую сторону получится.
Если в вашей задаче это не вяжется, можно вместо просто после сортировки отсечь по какой-то выбранной вами константе.