Подсчет «минимальный» ценности
У меня есть вход n векторов:
(x, y, z): x ∈ {1..n},y ∈ {1..n},z ∈ {1..n} (every "dimension" is set(1..n))
*I mean that in one vector x,y,z can be the same(x=y=z),
but for ∀v1,v2 => x1≠x2, y1≠y2, z1≠z2
v1>v2 if and only if x1>x2,y1>y2,z1>z2.
lets denote vector v1 "minimal" if and only if ∄v ∈ input: v>v1
Задача — подсчитать минимальные векторы на входе.
Я нашел эту проблему в задании местного конкурса по программированию.
(Переведенная) формулировка:
n people participeted in competion. competion had three phases(every competitor
took part in every stage). denote that the participant is better then
participant b, if a ranks in all three stages is higher then participant b ranks.
participant c is the best, if there is no such participant who is better
than participant c. output the number of best participants.
1<= п<= 100000
Ограничение времени: 1 сек.
Первой идеей было создать класс Result (для результатов конкурентов), оператор перегрузки> (или <) как:
bool operator > (const Score &s) const
{
if (first_result > s.first_result)
if (second_result > s.second_result)
return third_result > s.third_result;
return false;
}
и построить любой массив на основе (например, min-heap), который позволяет находить минимальные значения (используя <) и посчитать их (я думаю, что я просто «воссоздал» плохой вариант сортировки кучи следующим образом). После того, как я потерпел неудачу в этой попытке, я попробовал дерево Фенвика (Binary indexed tree) для той же задачи.
Но потом я понял, что мой подход неверен (не хорошо, класс и < перегрузка) и мб идея конвертировать задачу в 1d совсем не годится.
Тогда я нашел информацию о БИТ & дерево сегментов для случая n-измерений, и я думаю, что могу использовать их для решения этой проблемы. Но мне довольно сложно реализовать рабочий вариант (и даже понять принцип работы дерева сегментов более чем в 1d)
Может быть, кто-то может помочь с реализацией (или найти лучшее решение и объяснить его)?
Решение
Во-первых, нам потребуется упорядоченная структура данных ключ / значение, которую вы можете вставить, удалить и найти предыдущее / последнее значение, которое меньше или равно вашему собственному во времени. O(log(n)), Подумайте, красно-черное дерево или дерево или пропустить список.
Я буду использовать следующие придуманные обозначения для этой структуры данных. Я намеренно заставляю это не выглядеть как настоящий язык.
by_order.prev(key) дает пару k-v, связанную с наибольшим ключом <= для key,
by_order.prev(key).k дает самый большой ключ <= для key, Это может быть None,
by_order.prev(key).v дает значение, связанное с наибольшим ключом <= для key,
by_order.next(key) дает пару k-v, связанную с наименьшим ключом> = к key с .k а также .v имея в виду то, что они делали раньше.
by_order.add(key, value) добавляет k-v пара.
by_order.del(key) удаляет k-v пара со значением key,
Идея заключается в следующем. Сначала мы сортируем по x затем y затем z, Первый вектор минимален. Каждый вектор после этого минимален, если его значение z меньше, чем самое низкое значение z для любого предыдущего элемента с меньшим или равным y, Мы будем использовать by_order структура данных для проверки этого условия.
Предполагая, что я не ошибся, вот псевдокод:
sort(vectors) by x then y then z
Declare and initialize your empty ordered data structure by_order
// NOTE: by_order[val] will be the value of the largest key <= val
answer = [] // ie an empty list
answer.push(vectors[0])
by_order.add(vectors[0].y, by_order[vectors[0].z)
for v in vectors:
z_best = by_order.prev(v.y).v
if z_best is None or v.z < z_best:
answer.push(v) // Yay!
// Clear anything in by_order that we are an improvement on
while True:
pair = by_order.next(v)
if pair.v is not none and pair.k < v.z:
by_order.del(pair.v)
else:
break
// and now we add this one to by_order.
by_order.add(v.y, v.z)
Общее время, необходимое для сортировки O(n log(n)),
Вслед за каждым из n векторы O(log(n)) поиск, чтобы увидеть, нужно ли вставить его, возможно, сопровождается O(1) вставить в ответ O(log(n)) ищите, что все еще следует за этим (не волнуйтесь, я не упустил из виду те, которые были удалены), сопровождаемый O(log(n)) вставить, а затем O(log(n)) проверьте, что это нужно удалить, а затем O(log(n)) удалять.
Это много O(log(n)) сроки, но сумма все еще O(log(n)), n раз.
Результатом является O(n log(n)) Алгоритм для всей проблемы.
Другие решения
Идея у меня появилась:
struct Point {
int x;
int y;
int z;
};
bool operator < (const Point& lhs, const Point& rhs) {
return std::tie(lhs.x, lhs.y, lhs.z) < std::tie(rhs.x, rhs.y, rhs.z);
}
bool dominate(const Point& lhs, const Point& rhs) {
return lhs.x < rhs.x && lhs.y < rhs.y && lhs.z < rhs.z;
}
а потом:
std::vector<Point> res;
const std::vector<Point> points = {...};
std::sort(points.begin(), points.end());
for (const auto& p : points) {
if (!std::any_of(res.begin(), res.end(), [](const auto& m) { return dominate(m, p);})) {
res.push_back(p);
}
}
return res.size();
Сложность все еще в худшем случае n², (в настоящее время это max(n log n, res.size() * n))