Подсчитать "минимальные" значения

Проблема:

У меня есть вход 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<= n <= 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) для той же задачи.

Но потом я понял, что мой подход неверен (не в порядке, класс и <перегрузка), и mb идея конвертировать задачу в 1d совсем не годится.

Затем я нашел некоторую информацию о BIT и дереве сегментов для случая n-измерений, и я думаю, что смогу использовать их для решения этой проблемы. Но мне довольно сложно реализовать рабочий вариант (и даже понять принцип работы дерева сегментов более чем в 1d)

Может быть, кто-то может помочь с реализацией (или найти лучшее решение и объяснить его)?

Источник

2 ответа

Решение

Во-первых, нам потребуется упорядоченная структура данных ключ / значение, которую вы можете вставить, удалить и найти предыдущее / последнее значение, которое меньше или равно вашему собственному во времени. O(log(n)), Подумайте, красно-черное дерево или дерево или пропустить список.

Я буду использовать следующие придуманные обозначения для этой структуры данных. Я намеренно заставляю это не выглядеть как настоящий язык.

by_order.prev(key) дает пару кв, связанную с наибольшим ключом <= к key,by_order.prev(key).k дает самый большой ключ <= к key, Это может быть None,by_order.prev(key).v дает значение, связанное с наибольшим ключом key,by_order.next(key) дает пару kv, связанную с наименьшим ключом>= к 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))

Источник
Другие вопросы по тегам