Count "minimal" values

Question

Problem:

I have an input of n vectors:

(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

The task is to count minimal vectors in input.

Source:

I found this problem in the task of local programming contest.

The (translated) formulation is:

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 Time limit: 1 sec.

My attempts & thoughts

First idea was to create class Result(for competitors results), overload operator > (or <) just like:

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;
}

and build whatever array based(min-heap for example) that allows to find min values(using <) and count them(i think i've just "recreated" a bad variant of heap-sort following this way). After i failed this attempt i've tried Fenwick tree(Binary indexed tree) for same task.

But then i've understood that my approach is incorrect (not ok class and < overload) and mb the idea of convert the task in 1d is not good at all.

Then i've found some info about BIT & segment tree for n-dimensions case, and i think that i can use them to solve this problem. But it's pretty hard for me to implement the working variant(and even understand the working principle of segment tree in more then 1d)

Maybe someone can help with the implementation (or find better solution and explain it)?

IMO this is https://www.geeksforgeeks.org/topological-sorting/ problem — PiotrNycz, Mar 01 '18 at 16:03
@PiotrNycz Hm... Can you explain a bit the idea of using topological sorting to solve this task? — bordus, Mar 01 '18 at 16:11
For me, it is unrelated to topological order... But not found solution better than O(#vector²) yet. How many vector do you expect Btw ? — Jarod42, Mar 01 '18 at 16:37
When you get to a resolution, please remember to up-vote useful things and accept your favourite answer (even if you have to write it yourself), so Stack Overflow can properly archive the question. — Prune, Mar 01 '18 at 17:15
Your definition of problem (this math stuff) is incorrect - I mean this part "but for ∀v1,v2 => x1≠x2, y1≠y2, z1≠z2" How do you know that? The order defined by task description - this is partial order : https://en.wikipedia.org/wiki/Partially_ordered_set . And topological sorting is based on partial order. So. you can somehow use topological sorting to find all max elements - see also https://en.wikipedia.org/wiki/Partially_ordered_set Algorithm is O(N*V) where nodes are result and vertices are only between nodes that can be compared ("v1>v2 if and only if x1>x2,y1>y2,z1>z2. ") — PiotrNycz, Mar 01 '18 at 17:15
@PiotrNycz "How do you know that?" mb I a bit "overthink" this math stuff and confused you, but you can read the source task(mb it's more demonstrative). And condition in this part is right(cause there is a bijection between competitor and place in one phase of competion) — bordus, Mar 01 '18 at 17:24
@PiotrNycz: Mainly the OP problem is to count nodes without output vertices. The sorting is not part of the solution. — Jarod42, Mar 01 '18 at 17:27
@PaulHankin Makes me feel silly for doing all the work of typing up a detailed explanation... — btilly, Mar 01 '18 at 17:43
@PaulHankin Thank you! Think, your answer will solve my problem! — bordus, Mar 01 '18 at 17:50
@btilly Oh, really appreciate your help! Gonna read you answer now carefully, and understand solution. — bordus, Mar 01 '18 at 17:52

score 1 · Answer 1 · answered Mar 01 '18 at 17:23

Idea I got:

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;
}

and then:

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();

Complexity is still in worst case n². (currently it is max(n log n, res.size() * n))

Hm, thank you! it's much better then just naive make n-1 compares for n points, but still it's not enought for me, i think :c Gonna figure out how to improve this method — bordus, Mar 01 '18 at 17:43
In 2 dimensions, we can only do the check with last entries. In 3D, I doesn't see how to not check with all minima :-/ — Jarod42, Mar 01 '18 at 18:27

score 1 · Accepted Answer · answered Mar 01 '18 at 17:41

First, we'll need an ordered key/value data structure that you can insert, delete, and find the prev/last value less than or equal to your own in time O(log(n)). Think red-black tree or btree or skip list.

I will use the following invented notation for that data structure. I am deliberately making it not look like any real language.

by_order.prev(key) gives the k-v pair associated to the largest key <= to key. by_order.prev(key).k gives the largest key <= to key. This can be None. by_order.prev(key).v gives the value associated to the largest key <= to key. by_order.next(key) gives the k-v pair associated to the smallest key >= to key with .k and .v meaning what they did before. by_order.add(key, value) adds a k-v pair. by_order.del(key) removes the k-v pair with value key.

The idea is this. We first sort by x then y then z. The first vector is minimal. Every vector after that is minimal if its value of z is less than the lowest value of z for any previous element with lower or equal y. We will use the by_order data structure to test that condition.

Assuming that I made no mistakes, here is pseudocode:

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)

The total time taken for the sort is O(n log(n)).

Followed by for each of n vectors a O(log(n)) lookup to see whether to insert it, possibly followed by a O(1) insert into the answer, a O(log(n)) lookup what still follows it (don't worry, I didn't lose track of the ones that got deleted), followed by a O(log(n)) insert, followed by a O(log(n)) check that finds this one needs to be deleted, followed by a O(log(n)) delete.

That's a lot of O(log(n)) terms, but the sum is still O(log(n)). n times.

The result is a O(n log(n)) algorithm for the whole problem.

Count "minimal" values

Problem:

Source:

My attempts & thoughts

2 Answers2