TopCoder problem "WeighingScale" used in SRM 361 (Division I Level Three)



Problem Statement

    

Little George has found an old-fashioned balance scale and a set of weights in the attic. The scale has two weighing pans and it allows you to check if the content of the left pan is heavier, lighter, or the same weight as the content of the right pan. The box where the weights were kept says that each of them weigh 10, 20, or 30 grams, but the faded paint makes it impossible to tell which is which.

George started playing with the scale by comparing one weight against another, and noting down all his results. After a while he got bored with that, and came up with a new experiment. He put the A-th and B-th weights on the left pan and tried to guess what would happen when he put another two weights on the right pan.

You are given a String[] measures with the results of the previous experiments. The j-th character of the i-th element represents the result of comparing the i-th weight against the j-th weight, and it can have one of four values:

  • '+' - the i-th weight is heavier than the j-th weight.
  • '-' - the i-th weight is lighter than the j-th weight.
  • '=' - both weights have the same weight.
  • '?' - the two weights weren't compared.
Return a int[] containing exactly three integers in the following order: the number of different pairs of weights you can put on the right pan to make it lighter than the left pan, the number of pairs to make both pans the same weight, and the number of pairs to make the left pan lighter. Two pairs of weights are different if one pair contains at least one weight with an index that's not contained in the other pair. You should only consider the pairs that make the result unambiguously predictable based on the results in measures.

 

Definition

    
Class:WeighingScale
Method:count
Parameters:String[], int, int
Returns:int[]
Method signature:int[] count(String[] measures, int A, int B)
(be sure your method is public)
    
 

Notes

-Since the weights with indices A and B are already on the left pan you should only consider pairs that contain neither A nor B for the right pan.
 

Constraints

-measures will contain between 4 and 50 elements, inclusive.
-Each element of measures will contain exactly N characters, where N is the number of elements in measures.
-Each element of measures will contain only '+','-', '=', or '?'.
-The i-th character of the i-th element of measures will be '?'
-If the j-th character of the i-th element of measures is '+' than the i-th character of the j-th element will be '-' and vice versa.
-If the j-th character of the i-th element of measures is '=' or '?' than the i-th character of the j-th element will be the same.
-There will exist at least one way to assign values to the weights that will match the results in measures.
-A will be between 0 and N-1, inclusive, where N is the number of elements in measures.
-B will be between 0 and N-1, inclusive, where N is the number of elements in measures.
-A will be different than B.
 

Examples

0)
    
{"?+????","-?+???","?-????","????+?", "???-?+","????-?"}
1
4
Returns: {1, 4, 1 }
We have the following weight relations:
w0 > w1 > w2
w3 > w4 > w5
It can only be true if the values are (30,20,10,30,20,10). The left pan contains weights 1 and 4 with total weight 20+20=40. There is one pair (0,3) heavier than that, one pair (2,5) lighter than that and the remaining four pairs have the same weight.
1)
    
{"?+?????","-?+????","?-?????","????+??", "???-?+?","????-??", "???????"}
0
3
Returns: {10, 0, 0 }
The first six weights are the same as in example 0 (30,20,10,30,20,10). We know nothing about the 7th weight, but still, putting the two 30 gram weights on the left pan assures that it will be heavier than any other pair.
2)
    
{"?+?????","-?+????","?-?????","????+??", "???-?+?","????-??", "???????"}
1
4
Returns: {1, 4, 1 }
With the same measures as in the previous example, now weights 1 and 4 lie on the left pan, for a total weight of 40. We can predict what will happen only if the pair on the right pan doesn't contain the 7th weight; otherwise it's impossible to tell.
3)
    
{"??+?", "???+", "-???", "?-??"}
0
1
Returns: {1, 0, 0 }
We know that w0 > w2 and w1 > w3 thus w0+w1 must be heavier than w2+w3.
4)
    
{"??+??", "???+?", "-???=", "?-???", "??=??"}
0
1
Returns: {3, 0, 0 }
5)
    
{"?+???++?????++","-??=?=???????=","??????????=???","?=??+?==??????",
"???-???-???-??","-=????????????","-??=???=?-+???","???=+?=???????",
"??????????????","??????+???????","??=???-????-??","????+?????+???",
"-?????????????","-=????????????"}
6
2
Returns: {1, 10, 36 }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8025

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10773&pm=8025

Writer:

slex

Testers:

PabloGilberto , Yarin , Olexiy , ivan_metelsky

Problem categories:

Graph Theory, Search