11413 - Fill the Containers
Moderator: Board moderators
11413 - Fill the Containers
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?
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?
Re: 11413 - Fill the Containers
I used binary search in capacity.
Re: 11413 - Fill the Containers
Whats The Problem With This Problem ... ???????????????????????????????????????????
(((((((((((
![:(](./images/smilies/icon_frown.gif)
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;)
Beliefs are not facts, believe what you need to believe;)
Re: 11413 - Fill the Containers
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
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
Re: 11413 - Fill the Containers
I would like to tell respective authority of this problem to add some more data set in input file.It missed some input like:
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:
Output:
Code: Select all
5
1 2 3 5 4
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
Code: Select all
12
12
5
82
-
- New poster
- Posts: 1
- Joined: Sat Jul 21, 2012 6:46 am
Re: 11413 - Fill the Containers
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;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11413 - Fill the Containers
On line 20 you might be testing order[-1].
Check input and AC output for thousands of problems on uDebug!
Re: 11413 - Fill the Containers
Hi could anybody clarify some issues with this problem
Problem says
why does containers limit greater than vessels limit?
Also, I don't understand this constraint
Problem says
So, this is "one container many vessels" relationship.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.
why does containers limit greater than vessels limit?
Ho does it possible?(1 <= m <= 1000000)
Also, I don't understand this constraint
Does it mean that for first container we always must have to vessels?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
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11413 - Fill the Containers
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.
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!
Re: 11413 - Fill the Containers
I meant two ![:)](./images/smilies/icon_smile.gif)
Somebody posted input example
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?
![:)](./images/smilies/icon_smile.gif)
Somebody posted input example
Code: Select all
3 100
4 78 9
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?
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11413 - Fill the Containers
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!
Re: 11413 - Fill the Containers
Input:
Output:
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
Code: Select all
9
45
55
When I believe it is possible, I always find a way
Re: 11413 - Fill the Containers
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
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