USACO Silver 2016 February - Milk Pails

Video Solution

By David Zhou

Official Analysis (Java)

Explanation (DFS)

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
#include <bits/stdc++.h>

using namespace std;

bool vis[101][101][101];
int x, y, k, m, sol;

void ff(int curX, int curY, int curK) {
	if (vis[curX][curY][curK] || curK > k) return;
	vis[curX][curY][curK] = true;

Copy
import java.io.*;
import java.util.*;

public class Pails {
	static class State {
		int op, a, b;

		State(int op, int a, int b) {
			this.op = op;
			this.a = a;

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)
]

Alternate Solution: BFS

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
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORE(i, a, b) for (int i = (a); i <= (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define trav(a, x) for (auto &a : x)

int X, Y, K, M;

Copy
import java.io.*;
import java.util.*;

public class pails {
	final static int MX = 101, INF = (int)1e9 + 7;
	static int X, Y, K, M;
	static int[][] dist;

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new FileReader("pails.in"));

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