2
$\begingroup$

Say beauty pageants are judged based on 3 criteria: 1) Appearance 2) Personality 3) Talent. A contestant $C$ will beat another contestant $C'$ if she gets higher scores in ALL THREE of the criteria.

There are $n$ girls competing. Contestant $C_i$ is "Model Material" if $C_i$ is not beat by any other contestant $C_j$. Pretend you're the announcer and you have a collection of tuples: $(A_i, P_i, T_i)$ for $i = 1, 2,...,n$

The $i$th tuple contains the appearance, personality, and talent rating for $C_i$ (higher scores are better). Return a list of the "Model Material" contestants in in $O(n\log{n})$ time.

Given a data structure w/ a set $E$ of ints that, given an int $a$, --- (1) tells if a is in $E$ (2) finds smallest value > $a$ or largest value < $a$ in $E$ (3) inserts or removes a from $E$ in $O(\log{|E|})$ time.

I am trying to write pseudo-code for this algorithm but am lost trying to think of a correct algorithm that also runs in $O(n\log{n})$ time. I thought about starting initially with the $A_1$, $P_1$, and $T_1$ values for the first contestant, and if another contestant has a higher score in each category, remove the current tuple and replace it with the higher tuple, then repeat this process starting with a different contestant each time, but that's obviously not $O(n\log{n})$, and probably doesn't even work.

(This question was from my algorithms professor, and I can't find it online or in our textbook)

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE. What's the context in which you encountered this problem? Did you find it in a programming contest? Textbook? Course exercise? Can you edit the question to provide information on the source of the problem? $\endgroup$ – D.W. May 24 '17 at 20:24
  • $\begingroup$ It looks like you may have inadvertently created two accounts. I encourage you to register your account and create a password login, and merge your two accounts. This will ensure you retain access to your question and can edit it. $\endgroup$ – D.W. May 26 '17 at 18:10
1
$\begingroup$

You are asking for the Pareto-optimal front in 3D space. This is a well-studied problem.

In 2D, there are $O(n \log n)$ time algorithms: see, e.g., What are some interesting applications of the skyline problem?, An online algorithm to find the Pareto frontier elements, minimum subset of dominating 2D points.

In 3D, life is more complicated, but apparently it is still possible to solve this in $O(n \log n)$ using fancy methods. See the following paper:

On Finding the Maxima of a Set of Vectors. H.T. Kung, F. Luccio, F.P.Preparata. Journal of the ACM, vol 22 no 4, Oct 1975, pp.469--476.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.