10603 - Fill

[tep]

Hi,
I got WA for this. I use memoization to solve. But WA
anyone got test cases? and what the answer for this?

Input

5
12 23 42 14
12 53 75 23
56 23 34 2
23 55 72 25
124 86 173 84

Output

166 14
728 23
0 0
23 23
1012 77

[filigabriel]

Hi:

my output is

166 14
728 23
0 0
23 23
850 77

[tep]

I got ACC using BFS, but I'm still confused why I got WA using DFS + memoization
can u help?
thx

regards,
stephanus

[cpp]

/*
@ Problem : Fill
@ UVa id : 10603
@ Lang. : C++
@ Author : Stephanus
@ Date : 26 May 2004
*/
#include <iostream>
#include <map>
using namespace std;

#define f(a,b,c) (1000000*(a)+1000*(b)+(c))
#define INF 2000000

/* Memoization */
class Memo {
public:
int mindiff;
int poured;
};

map<int,Memo> memo;
map<int,Memo>::iterator p;

class Jug {
public:
int vol;
int maxvol;
};

Jug jug[3];
int wantvol;

// doit return min difference
int doit(int &poured)
{
// base case
if (jug[0].vol == wantvol || jug[1].vol == wantvol || jug[2].vol == wantvol)
{
poured = 0;
return 0;
}

// memo case
int y = f(jug[0].vol,jug[1].vol,jug[2].vol);
p = memo.find(y);
if (p != memo.end())
{
if (p->second.mindiff == -1) {
//cout << "memo1" << endl;
poured = INF;
return INF;
} else {
//cout << "memo2" << endl;
poured = p->second.poured;
return p->second.mindiff;
}
}

// init
Memo t;
t.mindiff = -1;
t.poured = -1;
memo.insert(pair<int,Memo>(y,t));

// operation
int i,j,k;
int mindiff,minpour;
int diff,pour;
int delta;

mindiff = INF;
minpour = 0;
for (k=0; k<3; k++)
if (jug[k].vol < wantvol)
{
diff = wantvol-jug[k].vol;
if (diff < mindiff) mindiff = diff;
}

for (i=0; i<3; i++) for (j=0; j<3; j++)
if (i != j && jug.vol != 0 && jug[j].vol != jug[j].maxvol)
{
// pour i to j untill j full
if (jug[j].maxvol - jug[j].vol <= jug.vol)
delta = jug[j].maxvol - jug[j].vol;
else delta = jug.vol;

jug.vol -= delta;
jug[j].vol += delta;

diff = doit(pour);
if (diff == mindiff && delta + pour < minpour)
minpour = delta + pour;
if (diff < mindiff)
{
mindiff = diff;
minpour = delta + pour;
}

jug.vol += delta;
jug[j].vol -= delta;
}

t.mindiff = mindiff;
t.poured = minpour;

memo.insert(pair<int,Memo>(y,t));

poured = minpour;
return mindiff;
}

int main()
{
int ncase,n;
int mindiff;
int poured;

cin >> ncase;
for (n=0; n<ncase; n++)
{
// input
cin >> jug[0].maxvol >> jug[1].maxvol >> jug[2].maxvol >> wantvol;

// init
memo.clear();
jug[0].vol = 0;
jug[1].vol = 0;
jug[2].vol = jug[2].maxvol;

// process
mindiff = doit(poured);

// output
cout << poured << " " << wantvol-mindiff << endl;
}

return 0;
}[/cpp]

[shuniu]

I used DFS to solve the problem, had to use approx 20000 of memory. I see on the ranklist alot of people got it with 64 mem and almost 0 time. This question seems to be quite large to send in precalc results, so is there a much better approach then searching through all configurations?

[minskcity]

I solved this problem in 0.014s, 64kb - I used dijkstra. Implementation is based on STL multimap and not optimized at all. Switching to self-made heap, adding some breaking conditions and some other minor optimization would probably bring me to 0.002, but I don't have time for it...

[brianfry713]

My approach to solve this using BFS was to keep an int array of size 201 that is the least total amount of poured water needed to produce that amount of liters in at least one of the jugs. Initialize this to all INT_MAX.
I also keep a bool array of size 201*201*201 that tracks if a state has been visited, initialized to all false.

My queue contains the amount currently in each jug and the amount of water poured so far.
Then for every reachable state I try the 6 possible pourings.

Then find the maximum d' less than or equal to d that is reachable.

This algorithm got AC for me in 0.036 seconds.

[m.shawkey]

I do not understand this part "It is allowed to pour water from one jug into another until either the first one is empty or the second one is full."
can you explain a test case?

EDIT:
Explained by Moustafa Mahmoud

you can pour some water from one jug (call it 'a') to another (call it 'b'), you MUST keeping pouring until either jug 'a' becomes empty or jug 'b' becomes full.

So, the initial state you're in is that the first two jugs are empty and the 3rd one is full. From that state you can move to other states according to the above condition.
So, think of the states as nodes, and from one state you have 6 possible moves:
- pour from jug 1 to jug 2
- from jug 1 to 3
- from jug 2 to 1
- from jug 2 to 3
- from jug 3 to 1
- from jug 3 to 2
each move will get you to a new state. So each state (node) will have at max 6 neighbours.
the above information is sufficient to define an implicit graph.

[lighted]

I am using BFS to search all possible states, but TLE. Something wrong with my implementation or there is a way to improve my BFS.

Code: Select all

#include <stdio.h>
#include <string.h>

const int MAX = 10000000000000000;

int f[210][210][210], qA[9000000], qB[9000000], qC[9000000];

char used[210][210][210];

int i, j, k, t, a, b, c, d, MAXD, MINS, nxt, lst;


void check(int D, long long SUM) {

  if (D <= d)
    if (D > MAXD  ||  (D == MAXD  &&  SUM < MINS) ) {

    MAXD = D;
    MINS = SUM;
  }
}

void add(int I, int J, int K, int poured) {

  if (!used[I][J][K]) {

    used[I][J][K] = 1;

    f[I][J][K] = f[i][j][k] + poured;

    qA[lst] = I;
    qB[lst] = J;
    qC[lst++] = K;

    check(I, f[I][J][K]);
    check(J, f[I][J][K]);
    check(K, f[I][J][K]);
  }
}


int main() {

  #ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
  #endif

  scanf("%d", &t);

  while(t--) {

    scanf("%d %d %d %d", &a, &b, &c, &d);

    memset(used, 0, sizeof(used));    

    qA[0] = 0;
    qB[0] = 0;
    qC[0] = c;

    f[0][0][c] = 0;

    used[0][0][c] = 1;
 
    MAXD = MINS = 0; 

    for (nxt = 0, lst = 1; nxt < lst; nxt++) {

      i = qA[nxt];
      j = qB[nxt];
      k = qC[nxt];

      if (i) {

        if (i + j > b) add(i + j - b, b, k, b - j);
                  else add(0, i + j, k, i);

        if (i + k > c) add(i + k - c, j, c, c - k);
                  else add(0, j, i + k, i);
      }

      if (j) {

        if (j + k > c) add(i, j + k - c, c, c - k);
                  else add(i, 0, j + k, j);

        if (j + i > a) add(a, j + i - a, k, a - i);
                  else add(j + i, 0, k, j);
      }

      if (k) {

        if (k + i > a) add(a, j, k + i - a, a - i);
                  else add(k + i, j, 0, k);

        if (k + j > b) add(i, b, k + j - b, b - j);
                  else add(i, k + j, 0, k);
      }
    }

    printf("%lld %d\n", MINS, MAXD);
  }

  return 0;
}

[brianfry713]

Change line 101 to:
printf("%d %d\n", MINS, MAXD);

Try changing line 8 to:
char used[201][201][201];

You're not using line 4 but you shouldn't try to declare an int with a value greater than 2147483647.

I kept track of the min amount of water poured to get to every possible d', and then found d' after the BFS.

You could try making your functions inline.

[lighted]

After this sentence i have a question:

I kept track of the min amount of water poured to get to every possible d', and then found d' after the BFS.

If we come to a visited state and we have less poured water, in my opinion we should change old value to the new better value. But in this case this problem cannot be solved by BFS. It becomes a DP problem which must be solved using Deikstra algo. Am i right?

[brianfry713]

I solved it using a full BFS, not Dijkstra's algorithm. I kept track of the min amount of water poured to get to every possible d', but continued with the BFS even if the amount of water poured to get to that d' was greater than before. Each reachable state in your used array should only be visited once. This isn't for reducing runtime, but the way your code only kept track of the min water poured for the current d' is probably wrong.

[lighted]

I changed my BFS to Dijkstra's algo but again got TLE.
Then i made changes which you recommended and got acc with runtime 2.725.

Change line 101 to:
printf("%d %d\n", MINS, MAXD);

Try changing line 8 to:
char used[201][201][201];

You're not using line 4 but you shouldn't try to declare an int with a value greater than 2147483647.

I kept track of the min amount of water poured to get to every possible d', and then found d' after the BFS.

You could try making your functions inline.

At last i removed the line

Code: Select all

memset(used, 0, sizeof(used));

And changed it to

Code: Select all

    for (i = 0; i <= a; i++)
      for (j = 0; j <= b; j++)
        for (k = 0; k <= c; k++) used[i][j][k] = 0;

A got acc with runtime 0.736. The main reason of getting TLE was using memset of full array.
Thanks for your help!

By the way with the modifications that you said my BFS avoided TLE. But got WA.
If you solved this problem with BFS than its a bit modified BFS. Because i think that BFS must be used in unweighted graph, and once you have reached a node by BFS it must be the path minimal cost or value. Maybe i am wrong

[brianfry713]

Yes you can also solve this with Dijkstra's algorithm.
You could also try changing used to an int array:

Code: Select all

for (i = 0; i <= a && i <= C; i++)
  for (j = 0; j <= b && i + j <= C; j++)
    used[i][j][C - i - j] = INT_MAX;

[shi562217697]

Hi,
I got WA for this.Why?

Code: Select all

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#include <set>

using namespace std;

struct state
{
   int water[3];
   int amt;
   bool operator < (const state& s) const
   {
      for (int i = 0 ; i < 2 ; ++i)
      {
         if (water[i] != s.water[i])
         {
            return water[i] < s.water[i];
         }
      }
      return water[2] < s.water[2];
   }
};
int cap[3];
int d;
set<state> ss;
int r_d;
int r_cnt;

bool is_visited(state& s)
{
   set<state>::iterator it = ss.find(s);
   if (it != ss.end())
   {
      if (it->amt > s.amt)
      {
         ss.erase(it);
         return false;
      }
      return true;
   }
   return false;
}
void set_visit(state& s)
{
   ss.insert(s);
}

void bfs()
{
   queue<state> q;
   state tmp;
   tmp.water[0] = tmp.water[1] = tmp.amt = 0;
   tmp.water[2] = cap[2];
   q.push(tmp);
   while (!q.empty())
   {
      state tmp = q.front();
      q.pop();
      set_visit(tmp);

      int max_liter;
      for (int k = 0 ; k < 3 ; ++k)
      {
         if (k == 0)
         {
            max_liter = tmp.water[k];
         }
         else if (tmp.water[k] <= d && tmp.water[k] > max_liter)
         {
            max_liter = tmp.water[k];
         }
      }
      if (max_liter <= d)
      {
         if (max_liter > r_d)
         {
            r_d = max_liter;
            r_cnt = tmp.amt;
         }
         if (max_liter == r_d && r_cnt > tmp.amt)
         {
            r_cnt = tmp.amt;
         }
      }

      for (int i = 0 ; i < 3 ; ++i)
      {
         if (tmp.water[i] == 0)
         {
            continue;
         }
         for (int j = 0 ; j < 3 ; ++j)
         {
            if (i == j)
            {
               continue;
            }
            if (tmp.water[j] < cap[j])
            {
               state next;
               memcpy(&next,&tmp,sizeof(next));
               int cnt = next.water[i] < (cap[j] - next.water[j]) ? next.water[i] : (cap[j] - next.water[j]);
               next.water[i] -= cnt;
               next.water[j] += cnt;
               next.amt += cnt;
               if (!is_visited(next))
               {
                  q.push(next);
               }            
            }
         }
      }
   }
}

void read_input()
{
   scanf("%d%d%d%d",&cap[0],&cap[1],&cap[2],&d);
   r_d = r_cnt = 0;
}


int main()
{

#ifdef shichun
   freopen("test.in","r",stdin);
   //freopen("test.out","w",stdout);
#endif

   int n;
   scanf("%d",&n);
   while (n--)
   {
      read_input();
      bfs();
      printf("%d %d\n",r_cnt,r_d);
   }

   
    return 0;
}

[lighted]

Don't open new thread. Search for existing thread about this problem first.
On every boards Volume header said

If there is a thread about your problem, please use it.

Try to use existing threads and continue it.

For input

Code: Select all

2
93 157 199 67
96 97 199 62

your program gives

Code: Select all

343 64
3468 12

my acc problem gives

Code: Select all

250 64
9859 62

I didn't checked your code.
Maybe one of problems is not memseting (cleaning) old results because when i changed the order of tests your program gave correct result for the first test

input

Code: Select all

2
96 97 199 62
93 157 199 67

your program gives

Code: Select all

9859 62
343 64