@bennyjoseph can you explain your approach?
@taran_1407 , Hi, I was trying with simple recursion to get minimum cost. But it did’nt passed any subtask except #5. Could you let me know, where I did wrong, or could it be done this way or if I missed some case?
my submission
Yeah , actually even I did the same thing and the sample test cases were passed but still after submitting I got a wrong answer
Can anyone please help me figure out why my solution is giving a wrong answer on almost all test cases. If someone could produce a test case on which my code fails, that would be great too. Thanks!
My code (C++):
using namespace std;
long long answer(int n, int e, int h, int a, int b, int c)
{
long long answer1 = -1;
long long answer2;
int x,y,z;
int limit = min(h, e);
limit = min(limit, n);
for (int i=0;i<=limit; i++)
{
z = i;
if (a<=b)
{
x = (e-z)/2;
y = n-z-x;
if (y<=(h-z)/3)
{
answer2 = (long long)a*(long long)x+(long long)b*(long long)y+(long long)c*(long long)z;
if (answer1 == -1)
answer1 = answer2;
else
answer1 = min(answer1, answer2);
}
}
else
{
y = (h-z)/3;
x = n-y-z;
if (x<=(e-z)/2)
{
answer2 = (long long)a*(long long)x+(long long)b*(long long)y+(long long)c*(long long)z;
if (answer1 == -1)
answer1 = answer2;
else
answer1 = min(answer1, answer2);
}
}
}
return answer1;
}
int main()
{
int t,n,e,h,a,b,c;
long long ans;
cin>>t;
for (int i=0;i<t;i++)
{
cin>>n>>e>>h>>a>>b>>c;
ans = answer(n,e,h,a,b,c);
cout<<ans<<endl;
}
return 0;
}```In two-dimensional Linear Programming, the max/min of the objective function will be at one of the vertices of the polygon formed by the inequalities, but that is not true for Integer Linear Programming in general, but in this case, because the objective function is a plane we can try integer points near the intersection and find min of all those.
3 Likes
I have recursively found all possible costs and take minimum of them. I got right answer for example inputs but WA on submitting. Can anyone help me with the issue please ?
Easiest problem of this long challenge
How can we show that the optimal integer point is always within distance two of an intersection? During the contest I checked the 4 closest integer points of each intersection (so the floors, ceilings), and gave up when that didn’t work.
I’m not sure if I can show the proof rigorously. When I meant a distance of 2 I meant manhattan distance “at most 2”. I think it works because of the plane-like shape of the objective function in three dimensions.
As for why distance “2” works, I think it it’s because the intersections are integers and I guessed that if you graphed these lines, you’d have some point within that range that falls inside the “constraint polygon”.
you solved it like a pro!!
1 Like
Nice problem. In the setter’s solution in the line :
long long useC = min(canC, req) ;
Is min() required ?. I think it can be directly assigned to canC.
1 Like
/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press “Run” button to compile and execute it.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long int n,e,h,a,b,c,MaxItem,sum;
vector<long long int> v1;
long long int t;
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>n>>e>>h>>a>>b>>c;
if(e%2 !=0 && h%3 !=0)
sum = e/2 + h/3 + 1;
else
{
sum = e/2 + h/3;
}
int minItem = min(e,h);
if(e == minItem)
{
MaxItem = max(min(e,h)+(h-e)/3,sum);
}
else if( h==minItem)
{
MaxItem = max(min(e,h)+(e-h)/2,sum);
}
if(n > MaxItem)
{
cout<<-1<<endl;
}
else
{
//only omellete
long long int cost1 =1000000;
if(e/2 >= n)
{
cost1 = n*a;
}
//only shake
long long int cost2 =1000000;
if(h/3 >= n)
{
cost2 = n*b;
}
// only cake
long long int cakes = min(e,h);
long long int cost7 =100000;
if(cakes >=n)
{
cost7 = n * c;
}
// milk shake and omlette
long long int omlette = e/2;
long long int shake = h/3;
long long int cost3 =1000000;
long long int cost4 =1000000;
if(omlette + shake >=n)
{
if(a > b && (n-(h/3))>=0)
{
cost3 = (n-(h/3)) * a + (h/3) * b;
}
else if(a <= b && (n-(e/2))>=0)
{
cost3 = (n-(e/2)) * b + (e/2) * a;
}
}
// omellete and cake
long long int cost5 =1000000;
for(int j=1 ;j<=min(e,h);j++)
{
if((e-j)/2 >= (n-j) && (n-j)>=0)
{
cost5 = min(j*c+(n-j)*a,cost5);
//cout<<cost5<<endl;
}
}
long long int cost8 = 1000000;
for(int j=1;j<=min(e,h);j++)
{
if((e-j)/2 + (h-j)/3 >= (n-j) && (n-j)>=0)
{
if(a > b && (n-j-((h-j)/3)) && h-j>=0)
{
cost8 = min(cost8,j*c+(n-j-((h-j)/3))*a+((h-j)/3)*b);
//cout<<cost8<<" "<<j<<" "<<(n-j-((h-j)/3))<<" "<<((h-j)/3)<<endl;
}
if(b >=a && (n-j-((e-j)/2)) && (e-j)>=0)
{
cost8 = min(cost8,j*c+(n-j-((e-j)/2))*b+((e-j)/2) *a);
//cout<<cost8<<" "<<j<<" "<<(n-j-((e-j)/2))<<" "<<((e-j)/2)<<endl;
}
}
else
{
if((e-j)%2 !=0 && (h-j)%3 != 0)
{
if((e-j)/2 + (h-j)/3 + 1 >= (n-j) && (n-j)>=0)
{
if(a > b && (h-j)>=0 && (n-j-((h-j)/3))>=0)
{
cost8 = min(cost8,(j+1)*c+(n-j-((h-j)/3))*a+((h-j)/3) *b);
}
if(b >= a && (n-j-((e-j)/2)) && (e-j)>=0)
{
cost8 = min(cost8,(j+1)*c+(n-j-((e-j)/2))*b+((e-j)/2) *a);
}
}
}
}
}
v1.push_back(cost1);
v1.push_back(cost2);
v1.push_back(cost3);
v1.push_back(cost4);
v1.push_back(cost5);
//v1.push_back(cost6);
v1.push_back(cost7);
v1.push_back(cost8);
sort(v1.begin(),v1.end());
//cout<<cost1<<" "<<cost2<<" "<<cost3<<" "<<" "<<cost4<<" "<<cost5<<" "<<cost6<<" "<<" "<<cost7<<" "<<cost8<<endl;
//cout<<mp[c]<<" "<<mp[o]<<" "<<mp[m]<<endl;
//cout<<a<<" "<<" "<<b<<" "<<c<<endl;
for(int k=0;k<v1.size();k++)
{
if(v1[k] != 1000000)
{
cout<<v1[k]<<endl;
break;
}
}
cost1=1000000;
cost2=1000000;
cost3=1000000;
cost4=1000000;
cost5=1000000;
//cost6=1000000;
cost7=1000000;
cost8=1000000;
v1.clear();
}
}
}
can anyone please help where I am geting wrong.I have tried every possible arrangement…
You are really smart brother 
1 Like
yeah, same question
Yes, if I understand correctly, it is required. If possible we want to take canC, but if N is such that we don’t need to serve that many meals, we just serve as many as required.
This one is all about some basic permutation.
Which element to perform it on is the important part.
As both Om (Omelette) and Mk (Milkshake) are dependent on Ck (Cake), it makes sense to perform the permutation with respect to Ck.
At every step in the permutation, I ran a weird variation of binary search to find the optimal solution.
A great Problem Statement for Div. 3.
My Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
int t;
cin>>t;
while(t--){
ll n,e,h,a,b,c;
cin>>n>>e>>h>>a>>b>>c;
ll cake=min(e,h);
ll omlette=(e-cake)/2;
ll milkshake=(h-cake)/3;
ll cost=INT_MAX;
if(cake+omlette+milkshake<n){
cout<<-1<<endl;
continue;
}
for(ll i=0;i<cake;i++){
if(a>b){
milkshake=min(n-i,(h-i)/3);
if((n-i-milkshake)>(e-i)/2){
continue;
}
omlette=n-i-milkshake;
cost=min(omlette*a+milkshake*b+i*c,cost);
}
else{
omlette=min(n-i,(e-i)/2);
if((n-i-omlette)>(h-i)/3){
continue;
}
milkshake=n-i-omlette;
cost=min(omlette*a+milkshake*b+i*c,cost);
}
}
cout<<cost<<endl;
}
return 0;
}
This is my code and its pass test cases but its showing WA during submission
Your code is failing in this test-case :
1
3 5 2 3 2 1
Expected O/P :
5
Your O/P :
7
What if the cost of cake is more than omelette and chocolate milkshake? For example if the input is :
1
4 5 4 2 3 4
The Expected output is : (22+13+14)=11
But, when we fix the cake, the answer will be 44=16