2

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.

HappyEngineer
  • 175
  • Without thinking too hard, I don't see the general algorithm, but note that you don't have to order all of the bags; I might not be able to tell you whether $AB$ or $CD$ weighs more, but perhaps I can tell you that $AD$ weighs more than either. For instance, in the given case, just take the bag containing the two heaviest types of gems. – Milo Brandt Jun 18 '16 at 00:46
  • Aha! If every single possible pairing exists then you can find the heaviest by simply choosing the one with the two heaviest stones. (This requires that all stone types are unequal in weight. That appears to be the case.) I'm both happy that this solve that specific problem, but it doesn't give me any further framework for solving the problem as a whole. Perhaps there isn't a framework and I just have to come up with all possible rules? – HappyEngineer Jun 18 '16 at 00:57
  • Comparing individual stones you can find which stones are lighter or heavier so if you label the stones x,y,z,w and you know x < y < z < w then then you know zw is the heaviest bag. – fleablood Jun 18 '16 at 06:56

1 Answers1

0

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.

fleablood
  • 124,253