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 (x4, y0)
, (x3, y1)
, (x2, y2)
, or (x1, y3)
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 "bottomup" 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 "topdown" approach that uses memoization.
Complexity Analysis

Time Complexity: . (There exists a constant
C
such that the algorithm never performs more thanC
steps.) 
Space Complexity: . (There exists a constant
C
such that the algorithm never uses more thanC
space.)
Analysis written by: @awice.