Approach #1: Dynamic Programming [Accepted]

Intuition

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.

When 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-4, y-0), (x-3, y-1), (x-2, y-2), or (x-1, y-3) each with equal probability.

When 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.

When 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.

Algorithm

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 1.

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.

Complexity Analysis

  • Time Complexity: . (There exists a constant C such that the algorithm never performs more than C steps.)

  • Space Complexity: . (There exists a constant C such that the algorithm never uses more than C space.)


Analysis written by: @awice.