11413 - Fill the Containers

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

Moderator: Board moderators

Post Reply
Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

11413 - Fill the Containers

Post by Leonid » Tue Sep 30, 2008 11:42 pm

What is the best time complexity approach for the problem?
I've somehow managed to get AC with a very slow DP O(n^3) solution.
How is it possible to improve the algorithm?
Is there any greedy approach?

pab2
New poster
Posts: 2
Joined: Wed Oct 01, 2008 7:25 pm

Re: 11413 - Fill the Containers

Post by pab2 » Wed Oct 01, 2008 7:28 pm

I used binary search in capacity.

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11413 - Fill the Containers

Post by Leonid » Wed Oct 01, 2008 10:48 pm

Thanks, that was obvious :oops:

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11413 - Fill the Containers

Post by Angeh » Mon Oct 18, 2010 8:15 pm

Whats The Problem With This Problem ... ???????????????????????????????????????????
:((((((((((((

Code: Select all

#include<iostream>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;++i)
int  in[1024],n,m;
bool f(int  S){
    int  C=0;
    int  s=0;
    FOR(i,n){
        if(s+in[i]>S )s=in[i],C++;
        else s+=in[i];
    }
    C++;
    if(C<=m)return true;
    else return false;
}
int main(){
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)>0 ){
        FOR(i,n)scanf("%d",&in[i] );
        int Sum=0;
        FOR(i,n)Sum+=in[i];
        int  l=2147483647,r=Sum+1;
        FOR(i,n)l=min(l,in[i] );
        while(l<r){
            int  mid=(r+l)/2;
            if( f(mid)==true )r=mid;
            else l=mid+1;
        }
        printf("%d\n",l);
    }
    return 0;
}
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

lucastan
New poster
Posts: 10
Joined: Sat Jul 02, 2011 6:46 am

Re: 11413 - Fill the Containers

Post by lucastan » Wed Jul 27, 2011 5:04 pm

Try this:

5 3
1 2 3 4 8
3 2
4 78 9

Your solution gives an incorrect answer of 6 whereas it should be 8
I think you're close. Just have to fix this bug

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 11413 - Fill the Containers

Post by Imti » Sun Nov 13, 2011 12:03 am

I would like to tell respective authority of this problem to add some more data set in input file.It missed some input like:

Code: Select all

5
1 2 3 5 4
output should be 5 but previous accepted code gave 4.after fixing that I got accepted which means absence of data set like that.For those who getting WA
Try This Input:

Code: Select all

2 3
12 3
2 3
3 12
5 4
1 2 3 5 4
3 100
4 78 9
Output:

Code: Select all

12
12
5
82

kurniawan1101
New poster
Posts: 1
Joined: Sat Jul 21, 2012 6:46 am

Re: 11413 - Fill the Containers

Post by kurniawan1101 » Sat Jul 21, 2012 6:49 am

can anyone help me with my program?

Code: Select all

#include <cstdio>
#include <cstring>

#define MAX 5000005
#define min(a,b) a < b ? a : b

int order[MAX];

int cek (int m, int v, int c)
{
	int sum = 0;
	for (int i = 0; i < v; i ++)
	{
		if ((sum + order[i]) <= m)
		{
			sum += order[i];
		}else
		{
			c--, sum = 0, i --;
			if (c == 0 || order[i] > m) return 0;
		}
	}
	return 1;
}

void in_o ()
{
	int ves, con;
	while (scanf ("%d %d", &ves, &con) == 2)
	{
		int sum = 0, ans = 1 << 25;
		for (int i = 0; i < ves; i++)
		{
			scanf ("%d", &order[i]);
			sum += order[i];
		}
		
		int l = 1, r = sum;
		while (l <= r)
		{
			int m = (l + r) / 2, x = cek (m, ves, con);
			if (x)
			{
				ans = min (ans, m);
				r = m - 1;
			}else
			{
				l = m + 1;
			}
		}
		
		printf ("%d\n", ans);
	}
}

int main ()
{
	in_o ();
	return 0;
}

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

Re: 11413 - Fill the Containers

Post by brianfry713 » Tue Jul 24, 2012 3:30 am

On line 20 you might be testing order[-1].
Check input and AC output for thousands of problems on uDebug!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 11413 - Fill the Containers

Post by sith » Sun Dec 23, 2012 8:59 am

Hi could anybody clarify some issues with this problem

Problem says
Whenever milk from a vessel is poured into a container, the milk in the vessel must be completely poured into that container only. That is milk from same vessel can not be poured into different containers.
So, this is "one container many vessels" relationship.

why does containers limit greater than vessels limit?
(1 <= m <= 1000000)
Ho does it possible?

Also, I don't understand this constraint
The ith container must be filled with milk only from those vessels that appear earlier to those that fill jth container, for all i < j
Does it mean that for first container we always must have to vessels?

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

Re: 11413 - Fill the Containers

Post by brianfry713 » Sun Dec 23, 2012 10:34 pm

You don't have to put milk in each container. If there are more containers then vessels you will end up with empty containers.

I don't really understand your second question. Did you mean "two" instead of "to"? The first container must be filled from the first vessel. The second vessel can either be poured into the first or the second container. Each of the remaining vessels can either be poured into the current container or the next.
Check input and AC output for thousands of problems on uDebug!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

Re: 11413 - Fill the Containers

Post by sith » Mon Dec 24, 2012 2:44 am

I meant two :)

Somebody posted input example

Code: Select all

    3 100
    4 78 9
and answer is 82.
Why? I think if we have a lot of containers we can set one container per each vessel, so the answer has to be 78?
Why 82?

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

Re: 11413 - Fill the Containers

Post by brianfry713 » Tue Dec 25, 2012 9:22 pm

Yes the correct output for that input is 78. You can generate I/O at http://www.uvatoolkit.com/problemssolve.php
Check input and AC output for thousands of problems on uDebug!

Alim14
New poster
Posts: 8
Joined: Sun Jan 05, 2014 3:40 pm
Location: BUBT,Dhaka, Bangladesh

Re: 11413 - Fill the Containers

Post by Alim14 » Sun Jan 05, 2014 4:02 pm

Input:

Code: Select all

5 9
1 9 2 3 5
10 9
1 2 3 4 9 12 34 45 34 2

5 2
12 12 45 5 5
Output:

Code: Select all

9
45
55
When I believe it is possible, I always find a way

Kingreey
New poster
Posts: 1
Joined: Thu Dec 11, 2014 6:39 pm

Re: 11413 - Fill the Containers

Post by Kingreey » Thu Dec 11, 2014 6:40 pm

10 11
1 1 1 1 1 1 1 1 1 1

10 10
1 1 1 1 1 1 1 1 1 1


5 3
1 2 3 4 5

3 2
4 78 9

1 2
1

1 1
1

5 1
1 2 3 4 5

5 2
1 2 3 4 5

10 3
9 5 1 4 2 8 7 3 6 5

21 6
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Post Reply

Return to “Volume 114 (11400-11499)”