Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Funny programming problem that I can't solve since a couple of days. I would be very grateful for help:

There is a tournament of $n\le 50000$ cakes. $i$-th cake is described by three numbers $\langle a_i, b_i, c_i \rangle$ (from interval $0...10^9$) which stand for: chocolate, fruit and cream. What is maybe very relevant we have $\forall_{i\neq j} \ a_i\neq a_j \wedge b_i\neq b_j \wedge c_i\neq c_j$. We know that iff $a_i<a_j$ and $b_i<b_j$ and $c_i<c_j$ then $i$-th cake is worse than $j$-th, otherwise we don't know anything and we have to try them both to decide which one is better. The problem is to count the minimal number of cakes we need to try to decide which cake is the best.

for example when we have cakes: $\langle 1,1,1 \rangle, \langle 6,2,2 \rangle, \langle 5,3,3 \rangle $, then we have to try $2$ cakes to decide which one is the winner.

It is very difficult I think.

share|improve this question
    
Does the name "vertex-cover problem" ring a bell? –  gt6989b Mar 8 '13 at 19:52
2  
This problem is likely to have many answers, because of the many possible meanings of the question. To start clarifying: Are we given the numbers $a_i,b_i,c_i$ to start with, or does finding these numbers count as "trying" cake $i$? If we tried two cakes, say $i$ and $j$ to decide which is better, if we now want to decide which of (the same) $i$ and (a different) $k$ is better, do we have to try cake $i$ again to compare it with $k$, or do we "remember" cake $i$ and only need to try $k$? Is it guaranteed that "better" is transitive? (I hope so; otherwise there might be no "best" cake.) –  Andreas Blass Mar 8 '13 at 20:13
    
@AndreasBlass Yes, we are given the numbers $a_i,b_i,c_i$. I think that "better" is transitive. –  xan Mar 8 '13 at 20:21
    
@gt6989b, never heard of it. Thanks then for the info! :-) –  xan Mar 8 '13 at 20:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.