Video Solution

By David Zhou

Official Analysis (Java)

Solution 1 (DFS)

Explanation

We can perform a DFS starting from the base state of $(0, 0)$, where both pails have $0$ units of milk.

Note that we need to use a 3D grid to correctly track visited states, though. This is because the DFS may visit the same $(i, j)$ state earlier in its processing but through a greater number of operations. To properly track visited cells, we need to make sure the visited grid has a record for how many operations it took to reach each state every time.

Simulating all six operations every time is enough to pass the constraints.

Implementation

Time Complexity: $\mathcal O(XYK)$

Copy
MAX_OPS = 100

x, y, k, m = map(int, open("pails.in", "r").read().split())

sol = float("inf")
vis = [
	[[False for a in range(MAX_OPS + 1)] for b in range(MAX_OPS + 1)]
	for c in range(MAX_OPS + 1)
]

Solution 2 (BFS)

Explanation

We can directly simulate all operations using BFS.

In this problem, we care about states $(i, j)$ where pail $X$ has $i$ and pail $Y$ has $j$ units of milk. We can perform a BFS starting from base state $(0, 0)$ to compute $\texttt{dist}[i][j]$, the minimum number of steps to reach each state. Afterwards, compute the answer by iterating over all states where $\texttt{dist}[i][j] \le K$ and finding the minimum $|i+j-M|$.

For every transition in the BFS, we simulate all possible actions.

1. Fill either pail completely to the top: set $i$ to $X$ or $j$ to $Y$.
2. Empty either pail: set $i$ or $j$ to $0$.
3. Pour the contents of one pail into another without overflowing or running out of milk.

To perform operation 3, we can find the amount poured to be $\min(i, Y-j)$ or $\min(j, X-i)$ depending on which pail you pour from. Then add/subtract this quantity to each pail appropriately.

Now iterate over all states $(i, j)$ where $\texttt{dist}[i][j] \le K$ and compute the minimum $|i+j-M|$.

Implementation

Time Complexity: $\mathcal O(XY)$

Copy
from collections import deque
import sys

sys.stdin, sys.stdout = open("pails.in", "r"), open("pails.out", "w")
input = sys.stdin.readline


def generate_permutations(p1: int, p2: int):
	# generates results of all possible pours
	da = min(p2, x - p1)  # amount poured when pouring p2 into p1

Solution 3 (DP)

Explanation

The states in this problem are a combination of the milk amounts in each pail and the number of operations to reach such amounts.

Let $\text{f}[i][j][l]$ represent if it is possible to reach $i$ and $j$ pail amounts in $l$ operations. Our base case is $\text{f}[0][0][0]$ as true, since there is no milk initially. Now, iterate through all $l$ such that $0\leq l<K$, and all possible $i$ and $j$. For any true state $\text{f}[i][j][l]$, mark $\text{f}[i'][j'][l+1]$ as true for all $(i', j')$'s that can result from a single operation based on $(i, j)$. The possible operations are explained in the previous solutions.

The answer is the minimum of $|i+j-m|$ for all true $\texttt{f}[i][j][l]$.

Implementation

Time Complexity: $\mathcal O(XYK)$

Copy
#include <climits>
#include <fstream>
#include <vector>
using namespace std;

int main() {
	ifstream fin("pails.in");

	int x, y, k, m;
	fin >> x >> y >> k >> m;