Approach #1: Dynamic Programming [Accepted]
First, we can simplify all the numbers by dividing by 25. More specifically, each unit is 25ml, and partial quantities of 25ml are rounded up to a full quantity.
N is small, this is a relatively straightforward dynamic programming problem: we have quantities of soup represented by the state
(x, y), and we can either go to
(x-2, y-2), or
(x-1, y-3) each with equal probability.
N is very large, this approach fails, so we need a different idea.
Instead of serving in batches of
(4, 0), (3, 1), (2, 2), (1, 3), pretend we serve
(1, 0) on the side first, and then serve from the fair distribution
(3, 0), (2, 1), (1, 2), (0, 3). If the pots of soup initially start at
(N, N), then after roughly less than
N/2 servings, one pot will still have soup. Because of the
(1, 0) servings on the side, this means that roughly speaking, pot
A is used first if we serve
N/2 fairly from the first pot before
N from the second pot.
N is very large, this almost always happens (better than 99.9999%, so we can output 1), and we can check this either experimentally or mathematically.
We convert all units by dividing by 25 and rounding up. If
N >= 500 (in new units), then by the above argument the answer is
Otherwise, we will perform a dynamic programming algorithm to find the answer. Our Java implementation showcases a "bottom-up" approach, that fills
memo diagonally from top left to bottom right, where
s = i + j is the sum of the indices. Our Python implemtation showcases a "top-down" approach that uses memoization.
Time Complexity: . (There exists a constant
Csuch that the algorithm never performs more than
Space Complexity: . (There exists a constant
Csuch that the algorithm never uses more than
Analysis written by: @awice.