Some time ago I stumbled upon the following problem: https://open.kattis.com/contests/g9yde4/problems/excellentengineers
In short: we are given a set of N people. They are ranked in 3 skills, each one has rank for the skills a natural number from 1 to N. A person is interesting iff there is no other person who has better rank in all three skills. Find the number of interesting people. N <= 100 000.
First I tried to solve the problem when each person has only 2 ranks. If this is the case, then the problem becomes easy — we first sort people in descending order of the first skill, then if a person is interesting then his second skill's rank must be better than that of all before him, so we can simply keep maximum. However, I can't think of a way to generalize this apart from keeping some sort of 2D segment tree which will be quite big to fit in memory and will be not so easy to code. So can anybody tell me a better/easier solution? Also additional question: can we generalize this in more than 3 dimensions(let's say K)?
http://codeforces.net/problemset/problem/12/D
Sort them by their third skill and scan from right to left maintaining a maximum segment tree.
Take a close look at engineer x. Due to our sort order, all the candidates that might be better than him are listed to the right, i.e x + 1, x + 2...
Now the thing you wanna know: is there someone who is better than x at first and second skills at the same time? That's why you need a segtree. The values of second skill will be segtree indexes whereas values of first will be segtree values. The only thing left is to take max value on [engineer[x].second + 1, n] and check whether it's greater that engineer[x].first.
Updates are quite obvious imo :)
Hmm, that's a good algorithm, thanks. Sadly, it seems that for higher dimensions(>=4) we'll need 2D segtree :(
Yep. As far as I understand, for K-dimensional problem we need a (K — 2)-dimensional segment tree :)