Milk Pails WA 1 testcase

Problems and Contests
#1

Problem link.
I use floodfill to store the “states”, which represent the sizes of the two buckets. The c variable in my dfs function refers tot he number of moves FJ made so far, which must always be \le K.

#include <bits/stdc++.h>
using namespace std;

int x, y, k, m;
bool vis[101][101] = {{0}};

int ans;
void dfs(int a, int b, int c){ // c = # of moves made so far
    if(c>k || vis[a][b]) return;
    vis[a][b] = true;
    ans = min(ans, abs(m-a-b));
    dfs(x, b, c+1), dfs(a, y, c+1); // fill pail completely
    dfs(0, b, c+1), dfs(a, 0, c+1); // empty pail
    int p1 = min(a, y-b), p2 = min(b, x-a);
    dfs(a-p1, b+p1, c+1); // pour from a to b
    dfs(a+p2, b-p2, c+1); // pour from b to a
}

int main()
{
    freopen("pails.in", "r", stdin);
    freopen("pails.out", "w", stdout);
    cin >> x >> y >> k >> m;
    ans = m;
    dfs(0, 0, 0);
    cout << ans << endl;
}

I receive a WA on test case 8, while all other test cases pass within a few milliseconds. I tried changing a few things, such as

  • setting ans = 1e9,
  • vis[0][0] = 1 prior to dfs and if(c>k || (c && vis[a][b])) return; within dfs,
  • extending the size of the vis matrix (number of states),

but these are insignificant changes. Can you please help me fix my mistake?

1 Like
#2

I could be completely wrong since I didn’t read the problem yet :cowboy_hat_face: but shouldn’t your visited array have three dimensions, a b and c? Because arriving at state (a, b) with 10 moves spent isn’t the same as arriving at state (a, b) with only 5 moves spent right?

#3

Hi, i had the same problem as you, and i think i figured it out.

Lets say that there are two possible ways to get to a and b, one in two moves and one in six moves, lets say you get to a and b in 6 moves first that means you will mark a and b as visited and never visit it again in 2 moves in the future, c=2 or c=6 is different because if you are at a and b and c = 6,and lets say the limit is 8(k is 8),then you will have two moves left,so a limited amount of new possibilities to be generated, but if you would have gotten to a and b with c equal to 2(that means 6 moves left!) you maybe would have generated more solutions.

I hope my explanation helps! :slight_smile: