Connection Status:
Competition Arena > FoxAndGemstone

FoxAndGemstone

2016 TCO Algo Parallel 2B · 2016-03-24 · by cgy4ever

2016 TCO Algo Parallel 2B · 2016-03-24 · by cgy4ever · Dynamic Programming, Sorting
Class Name: FoxAndGemstone
Return Type: String
Method Name: isPossible
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Fox Ciel has a collection of bags. Each of those bags contains some gemstones. You are given the contents of the bags as a String[] bags. Each element of bags represents one of the bags. Different characters represent different gemstone types. For example, if bags[2]="ABAC", we know that bag 2 contains two gems of type A, one gem of type B, and one gem of type C.

There are at most 16 different types of gems. Gems of the same type always have the same weight. Gems of different types always have different weights. Each weight is some positive real number.

Fox Ciel wants to identify the heaviest of all her bags. (It is possible that multiple bags are tied for being the heaviest. In that case, Ciel wants to identify any one of those bags.)

Ciel has only one tool she can use while solving this task: a tiny balance scale. The scale is so small that the only thing she can do is to compare the weights of two gems. I.e., in each weighing she will take two gems of different types, place each of them onto one of the pans of the scale, determine which type of gems weighs more, and then she'll return both gems to their original places. Ciel can use the scale arbitrarily many times.

You are given the String[] bags, but you don't know anything about the weights of the gems. Return "Possible" if you can be sure that Ciel will be able to identify the heaviest bag. Otherwise, return "Impossible". In other words, return "Impossible" if there is some combination of weights of gemstone types such that Ciel won't be able to determine with certainty which bag is the heaviest one.

Constraints

  • bags will contain between 2 and 50 elements, inclusive.
  • Each element in bags will contain between 1 and 50 elements, inclusive.
  • Each character in bags will be one of the first 16 uppercase English letters ('A'-'P').
Examples
0)
{"AB", "AC"}
Returns: "Possible"

Ciel just needs to compare a gem of type B and a gem of type C. If B is heavier, bag 0 is the heaviest bag. Otherwise, bag 1 is the heaviest bag.

1)
{"A", "BC"}
Returns: "Impossible"

This is an interesting situation. For some combinations of weights Fox Ciel will find the heaviest bag. For example, if she discovers that A < B, she can be certain that the bag "BC" is heavier than the bag "A". However, there are some combinations of weights for which Ciel won't be successful. For example, suppose she weighs the gems and she finds out that A > B > C. Given the above information, it is possible that A > B+C, but it is also possible that A < B+C. In this situation, Ciel has no way of telling which bag is the heavier one.

2)
{"A", "B", "C", "AB", "AC", "BC", "ABC"}
Returns: "Possible"

Here Ciel doesn't need the scale at all, she can simply choose the last bag.

3)
{"AB","AC","AD","BC","BD","CD"}
Returns: "Possible"
4)
{"AB", "CD"}
Returns: "Impossible"

Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FoxAndGemstone with a public method string isPossible(vector<string> bags) · 100 test cases · 2 s / 256 MB per case

Submitting as anonymous