10603 - Fill

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

tep
New poster
Posts: 23
Joined: Fri Jun 13, 2003 6:08 am
Contact:

10603 - Fill

Post by tep » Tue May 25, 2004 8:51 am

Hi,
I got WA for this. I use memoization to solve. But WA :cry:
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

User avatar
filigabriel
New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M
Contact:

Post by filigabriel » Tue May 25, 2004 9:14 pm

Hi:

my output is

166 14
728 23
0 0
23 23
850 77

tep
New poster
Posts: 23
Joined: Fri Jun 13, 2003 6:08 am
Contact:

Post by tep » Wed May 26, 2004 2:05 pm

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
New poster
Posts: 34
Joined: Thu Oct 16, 2003 6:15 pm

Post by shuniu » Wed Jun 16, 2004 6:55 am

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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Sat Aug 07, 2004 3:20 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10603 - Fill

Post by brianfry713 » Wed Feb 06, 2013 11:37 pm

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.
Check input and AC output for thousands of problems on uDebug!

m.shawkey
New poster
Posts: 9
Joined: Tue Jun 11, 2013 2:58 pm

Re: 10603 - Fill

Post by m.shawkey » Sun Aug 04, 2013 8:04 pm

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10603 - Fill

Post by lighted » Wed Jun 18, 2014 12:40 pm

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;
}
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10603 - Fill

Post by brianfry713 » Thu Jun 19, 2014 12:13 am

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.
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10603 - Fill

Post by lighted » Thu Jun 19, 2014 1:50 pm

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?
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10603 - Fill

Post by brianfry713 » Thu Jun 19, 2014 10:11 pm

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.
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10603 - Fill

Post by lighted » Fri Jun 20, 2014 1:03 pm

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
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10603 - Fill

Post by brianfry713 » Tue Jun 24, 2014 9:33 pm

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;
Check input and AC output for thousands of problems on uDebug!

shi562217697
New poster
Posts: 3
Joined: Fri Jun 20, 2014 9:51 am

10603-Fill

Post by shi562217697 » Sat Jul 05, 2014 3:20 am

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10603-Fill

Post by lighted » Sun Jul 06, 2014 3:02 pm

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
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 106 (10600-10699)”