There is a problem called Fox and Gemstone at topcoder: https://community.topcoder.com/stat?c=problem_statement&pm=14296
Basically, you have the ability to weigh individual gemstones against each other, but not whole bags of them. You must then determine if it's possible to determine the heaviest bag. You aren't given any actual numbers or comparisons, so you can't actually find which one is heaviest. You just need to have an algorithm which determines if it's possible given the set of information.
For example, if you have a bag containing gems A and B, and another bag containing gems A and C then the proper response is "Possible" because you can ignore A and just compare B and C to see which bag is heaviest.
However, the problem includes one example which is supposedly "Possible" which I can't wrap my head around. How is this problem possible:
{"AB","AC","AD","BC","BD","CD"}
Comparing AB and CD by themselves is impossible because there is nothing to compare. However, apparently if you have a bunch of other bags which it somehow makes it possible to order AB and CD without having to compare those bags to each other.
I understand that if we find that B < C and A < D then we know that AB < AC and AC < CD which means we can certainly say that AB < AC < CD.
However, I can't figure out how to extend that line of thinking to some sort of general algorithm that would allow me to order those 6 bags and then go further and solve the whole problem for the general case of any possible sets of bags. Remember that I don't actually know that B < C. If C < B then I can't actually sort those 3 because AC < AB ? CD.
I was thinking that perhaps it would be some sort of graph where each vertex would be a gemstone and each edge would be a bag, and the idea would be to determine if the graph was connected. However, even if that worked, it wouldn't help when the bags contained more than two gemstones.
If this problem type is a subset of other similar types of problems then ideally I'd like to know how to approach all problems of this type.
Um, the heaviest bag is going to be the bag with the heaviest stone and the second heaviest stone.
Compare by comparing gemstones, surely finding which is heaviest and second heaviest is obvious.