USACO 2016 February Contest, Silver - Milk Pails

 Problem Link

Tags: USACO, BFS, graph
Time Complexity: O(XY)

I learnt the way to solve this problem using BFS from here.

In this problem, there is M (the order quantity), two pails X and Y, and K(the number of moves available). By using at most K moves, we need to find the minimum difference in M and the achievable milk quantity using pails X and Y, in the ways described in the problem.

Even though this may not seem like a graph problem, guess what? It is.

When pail X has x amount of milk and pail Y has y amount of milk, we call this situation a state. A state can be written as s[x][y]. For example, if pail X has 2 units of milk and pail Y has 5 units of milk, the state is s[2][5].

The first state is s[0][0], since we start out with both pails having 0 units of milk. From here, we can reach s[X][0] or s[0][Y] by filling either pail to the top. Treat the different states as nodes in a graph. Since the two states can be obtained from s[0][0], we can draw an edge between the two nodes (s[X][0] and s[0][Y]) and the original node (s[0][0]).

Likewise, we can build additional states by following the different operations in the problem. There are a total of 6 states can can be obtained from a node, although sometimes achieving all 6 states from a node may not be possible (for example: only 2 states can be obtained from s[0][0]) -

1. Fill pail X
2. Fill pail Y
3. Empty pail X
4. Empty pail Y
5. Pour X into Y
6. Pour Y into X

Keep track the number of moves taken to reach state[x][y]. This can be done by recording the smallest number of edges that were traversed to reach s[x][y]. Only if this distance is ≤ K, then this state can be considered valid. The answer is the smallest value of  |M - (x+y)| calculated from all valid stat, since we want the total milk in both pails to be as close to M as possible.

Code

#include <bits/stdc++.h>

using namespace std;

const int MAX_X = 101, MAX_Y = 101;

int startx, starty, k, m;

bool visited[MAX_X][MAX_Y];

int main()

{

    freopen("pails.in", "r", stdin);

    freopen("pails.out", "w", stdout);

    cin >> startx >> starty >> k >> m;

    queue <tuple <int, int, int>> q;

    q.push({0, 0, 0});

    int ans = INT_MAX;

    while (!q.empty()){

        int moves = get<0>(q.front()), x = get<1>(q.front()), y = get<2>(q.front());

        q.pop();

        if (moves >= k)

            continue;

        int dx[] = {startx - x, 0, -x, 0, -min(starty - y, x), min(startx - x, y)};

        int dy[] = {0, starty - y, 0, -y, min(starty - y, x), -min(startx - x, y)};

        for (int i = 0; i < 6; i++){

            int curr_x = x + dx[i], curr_y = y + dy[i];

            if (visited[curr_x][curr_y])

                continue;

            visited[curr_x][curr_y] = true;

            q.push({moves+1, curr_x, curr_y});

            ans = min(ans, abs(m - (curr_x + curr_y)));

        }

    }

    cout << ans << '\n';

}