FastPrep

Description

Solutions

Optimized Waffle Baking Championship Probability

📚RELATED PROBLEMS

Lily is in the final round of the Optimized Waffle Baking Championship hosted in Bieslau, Ida. Her opponent baked first and surprisingly has a high score, meaning that Lily must score an exact number of points to win. If she scores too many points, or too few points, her opponent will take home the championship trophy instead. Lily will have a finite number of chances (or "bakes") to make waffles for all the judges, and on each bake she can choose from any of her waffle mixes. Each waffle mix affords her a different probability to score anywhere from 1 to 5 points, or 0 points if she is unable to submit a waffle in time. She can use the same baking mix any number of times, and she does not have to use each of the mixes at all. At any point, Lily can choose to stop baking waffles; she would do this only if she reaches her target score before using up all of her chances, thereby avoiding going over. Having been an amateur baker most of her life, Lily knows the exact probability distribution of each of her available waffle mixes.

Assume that Lily takes an optimal strategy in her quest to win the championship, and that each bake is independent of the others. Implement the function getProbability to determine the probability that Lily takes home the championship trophy.

Function Description

Complete the function getProbability in the editor.

getProbability has the following parameters:

int[] scores: The array of scores that Lily can potentially earn with each of her waffle mixes.
int[] prob: The array of probabilities, in percentage points, that Lily will earn the number of points represented by the corresponding element in the scores array.
int n: The number of chances Lily has to bake waffles.
int x: The exact number of points Lily needs to win the championship.

Returns

double: The probability, as a double, that Lily wins the championship given the parameters.

Helper Functions

Two helper functions are available for calculating compound probabilities:

probabilityAND(double a, double b): Calculates the probability of two independent events both occurring.
probabilityOR(double a, double b): Calculates the probability of at least one of two independent events occurring.

Example 1:

Input:  scores = [2, 3, 5], prob = [10, 10, 20], n = 2, x = 6
Output: 0.013 
Explanation:
      
        Consider a scenario in which Lily has 2 bakes available, 3 waffle mixes from which to choose, and is trying to earn exactly 6 points. The probability distribution for the waffle mixes is as follows:
      
      
        Mix 1: 10% chance of 2 points, 10% chance of 3 points, 20% chance of 5 points.
        Mix 2: 20% chance of 1 point, 20% chance of 2 points, 20% chance of 3 points, 10% chance of 4 points, and 10% chance of 5 points.
        Mix 3: 20% chance of 1 point, 30% chance of 2 points, 20% chance of 3 points, 10% chance of 4 points, and 20% chance of 5 points.
      
      
        The final calculated probability is then 0.013.

Constraints:

TO-DO