Saturday, July 29th

How will we finish all this soup?

Given the volumes of 2 types of soup, and 4 kinds of operations to reduce the amounts of soup, determine probabilities of how the soups will be finished



When thinking about how the soup will be consumed, we can imagine reaching the same amounts in different ways.  For instance, if we first eat 75ml of soup A and 25ml of B, then eat 25ml of A and 75ml of B, this would lead to the same amounts as if we consumed 50ml of A and B, twice.  

Considering these overlapping subproblems, dynamic programming is an appropriate technique for solving the problem.  The two states to consider are the amounts of soup for A and B

Let's approach the problem with top-down dynamic programming, which will utilize memoization.  First we initialize the memo:

vector<vector<double> > memo; //global variable

double soupServings(int n) {
        memo=vector<vector<double> >(n+1, vector<double>(n+1,-1));
    }

Then we will create our recursive function that answers the problem, namely, the probability that A will be emptied first, plus half the probability A and B finish together.  The recursive function takes the two state variables, the amounts of the soup.  Let i be the amount of soup A, and j be the amount of soup B

double dp(int i, int j) {
        ...
    }

With a recursive function, we open with the definition of a base case.  Considering the values of i and j, we return the probability of achieving our goal.  If i <= 0 and j > 0, the probability of A being empty while B remains is equal to 1.  If both i and j are <= 0, then by the problem's definition, the probability is 0.5.  If j <= 0 but i > 0, then return 0, as this is not a state we are looking for.

    if(i<=0 && j<=0) return 0.5;
else if(i<=0) return 1;
else if(j<=0) return 0;

Since we're using memoization, we check if a given state has already been calculated

if(memo[i][j]!=-1) {
return memo[i][j];
}

Now we come up with our recurrence relation.  A given state can lead to 4 different states, depending on how much soup is consumed of both soups.  These 4 states are reached with an equal probability.  So we calculate the probability of each state, sum it up and divide by 4. 

    double ans=0;
ans+=dp(i-100, j);
ans+=dp(i-75, j-25);
ans+=dp(i-50, j-50);
ans+=dp(i-25, j-75);
ans /= 4

To complete the dynamic programming recursive function, we set the memo equal to the answer and return it

    emo[i][j] = ans;
return memo[i][j];

This solution works for the simple test cases, but runs into problems, like memory limits, for larger values of n.  This can be solved in 2 ways:

  • Empirically observe what happens at larger values of n
  • Program in tests for when answers differ by less than the stated error range
When n gets large, the probability approaches 1 that soup A will finish first.  Considering the law of large numbers, this makes sense because soup B cannot draw 100ml, so the different soup consumptions lean towards soup A finishing first.  Through experiments, it can be discovered that around 5000 ml the answer is 1.  So we put this check in our main function

    double soupServings(int n) {
if(n>5000) return 1;
memo=vector<vector<double> >(n+1, vector<double>(n+1,-1));
return dp(n,n);
}

Interesting use of probability with dynamic programming

Thank you to salonadubey for an approach that doesn't reduce the volume of soup to servings

Comments

Post a Comment

Popular posts from this blog

Wednesday, September 20th

Image
 Reduce X to Zero Given an integer array and value x, use elements at the right and left of the array to reduce the x value to zero A collection of windows, by Daderot .  Shared under the Creative Commons Attribution-Share Alike 3.0 Unported License .  No changes made A key observation is that if elements at the ends of the array are used to sum up to a target value x , then elements in a contiguous subarray will equal the total_sum - x .  So we will look for the largest window equal to  total_sum - x Since all elements in the array are positive, then we can solve the problem using 2 pointers that form a sliding window. The general idea is to begin 2 pointers right and left at index 0.  Continue incrementing the right index by 1, adding up the elements it passes into the current_window  sum.  If the sum equals the target value, update the length.  Otherwise, if the sum is greater than the target sum, increment the left index until the window...
Read more

Monday, September 11th

Image
 Groups There are a given number of people, each of whom is assigned to a group.  The number identifier of the group is also its size.  The size of a group may be a multiple of its size, e.g. a group of 3 may have 6 people.  Return the  collection of all groups . Team USA Softball (a group).  Shared by USASoftball , via Wikipedia , distributed under the Creative Commons Attribution-Share Alike 3.0 Unported license.  No changes made. This problem is pretty straightforward.  The idea is to create a map (or a vector) keyed by the group, storing an array of individuals belonging to the group. First we create the vector-of-vectors to store our solution, then we initialize a vector of vectors that will store individuals according to their group numbers.  The size of the solution vector is n+1, because contrary to what the beginning of the problem statement said, the indices/group sizes go from 1 to n, according to the stated constraints. vect...
Read more

Tuesday, September 19th

Image
 Find the duplicate number Given an array of integers of length n+1, which contains numbers within the range [1,n], and contains on element that is duplicated at least once, find the duplicate element , considering use of only constant space and no changes to the array "How They Met Themselves" by Dante Rossetti, depicting doppelgängers The problem of finding duplicates is made difficult by the constraints of no modifications to the original array, and use of only constant extra space.  Still, despite these constraints there are still several ways to solve the problem.   Since yesterday's solution involved binary search, we will hone our BS skills by applying it to today's problem The general idea is based on the observation that without duplicates, the number of elements less than or equal an element is equal to the element itself.  E.g., in the collection {1,2,3,4}, the number of elements less than or equal to 2 is 2, less than or equal to 3 is 3, etc.   Howe...
Read more