TopCoder problem "IngredientProportions" used in SRM 429 (Division I Level Two , Division II Level Three)



Problem Statement

    

Your friend has invented a splendid cocktail consisting of N ingredients. However, she has forgotten the amount of each ingredient that goes into the recipe.

For N-1 pairs of ingredients, she remembers the proportion in which the ingredients within each pair should be added to the cocktail. Fortunately, these N-1 proportions are sufficient to restore the recipe of the entire cocktail.

You are given a String[] proportions containing the N-1 proportions. Each element is formatted "#<a> and #<b> as <p>:<q>" (quotes for clarity), which means that the mass of ingredient <a> divided by the mass of ingredient <b> in the cocktail must be equal to <p>/<q> (all ingredients are 0-indexed). Return a int[] containing exactly N elements, where the i-th element is the mass of ingredient i, such that all the given proportions are satisfied and the total mass is as small as possible. The total mass must be greater than 0.

 

Definition

    
Class:IngredientProportions
Method:getMasses
Parameters:String[]
Returns:int[]
Method signature:int[] getMasses(String[] proportions)
(be sure your method is public)
    
 

Constraints

-proportions will contain between 1 and 9 elements, inclusive.
-proportions will contain exactly N-1 elements, where N is the number of ingredients in the cocktail.
-Each element of proportions will contain exactly 16 characters.
-Each element of proportions will be formatted as described in the statement.
-Each <a> will be between 0 and N-1, inclusive.
-Each <b> will be between 0 and N-1, inclusive.
-Each <p> will be between 1 and 9, inclusive.
-Each <q> will be between 1 and 9, inclusive.
-The information given in proportions will be sufficient to restore the recipe of the cocktail uniquely up to a constant factor.
 

Examples

0)
    
{"#0 and #1 as 6:4"}
Returns: {3, 2 }
Taking 6 units of ingredient #0 and 4 units of ingredient #1 would satisfy the proportion, but it wouldn't give the smallest possible total mass. To minimize the total mass, divide the masses by 2.
1)
    
{"#0 and #1 as 9:8","#1 and #2 as 9:8"}

Returns: {81, 72, 64 }
2)
    
{"#4 and #0 as 1:1", "#4 and #1 as 3:1", "#4 and #2 as 5:1", "#4 and #3 as 7:1"}
Returns: {105, 35, 21, 15, 105 }
The mass of ingredient #4 should be divisible by 3, 5 and 7. The smallest such number is 105.
3)
    
{"#2 and #3 as 6:8", "#0 and #1 as 9:3", "#3 and #0 as 7:5"}
Returns: {60, 20, 63, 84 }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13520&pm=8729

Writer:

darnley

Testers:

PabloGilberto , Olexiy , ivan_metelsky

Problem categories:

Graph Theory, Simple Math, String Parsing