Need help with excellent engineers from kattis OJ

Revision en1, by AnotherRound, 2017-06-26 21:41:05

Some time ago I stumbled upon the following problem:

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)?


  Rev. Lang. By When Δ Comment
en1 English AnotherRound 2017-06-26 21:41:05 1093 Initial revision (published)