COLGLF4 - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter:
Tester: Felipe Mota
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Basic Maths, Inequalities.

PROBLEM

A Canteen has E eggs and H chocolate bars. Canteen serves omelette at price A which needs 2 eggs, chocolate milkshake at price B which needs three chocolate bars and chocolate cake at price C which needs one egg and one chocolate bar each.

Chef and N-1 friends each order any one of the above such that the canteen can prepare all orders, while the cost is minimized. Find this minimum cost, or determine that canteen cannot handle all N orders.

QUICK EXPLANATION

  • Write these constraints in form of inequalities, where variables are the number of omelettes, chocolate milkshake and chocolate cakes ordered.
  • Iterate over the number of chocolate cakes and find the maximum possible omelettes and chocolate milkshakes possible.
  • Decide between omelettes and milkshake based on cost.
  • Take minimum of cost over all possible number of chocolate cakes.

EXPLANATION

Since all we need to handle are constraints, we can write it in form of linear inequalities, along with an optimizing function.

Let x denote number of omelettes, y denote number of chocolate milkshakes and z denote the number of chocolate cakes ordered.

Then, we have

  • x+y+z = N since exactly N orders are made.
  • 2*x + z \leq E due to number of eggs.
  • 3*y + z \leq H due to number of chocolate bars.
  • x, y, z \in Z^+ since number of orders are non-negative integers.

We need to minimize A*x+B*y+C*z

This general setting is known as Integer Programming, which is an NP-complete problem. Thankfully, for this problem, we can approach it in a different way.

Since \sum N \leq 10^6 in constraints, we can actually iterate over value of any one of x, y or z from 0 to N.

We can see that by iterating on z, we can find maximum bounds on both x and y from both the inequalities, so iterating on z is most useful in this problem.

Let’s say we try all values of z one by one. So we get x \leq (E-z)/2, y \leq (H-z)/3. Now canteen can prepare x omelettes and y chocolate milkshakes independent of each other. So chef can decide how to order remaining N-z items depending upon whether omelette is cheaper or chocolate milkshake. We also need to check if it’s even possible or not.

Hence, for a fixed value of z, we can compute in O(1) time the minimum cost to order N items. So, by iteratig over all values of z, we have considered all possible combinations which may be candidates for lowest cost. We can simply take minimum of these costs.

If there’s no z for which it is possible to order N items, print -1.

TIME COMPLEXITY

The time complexity is O(N) per test case.
The memory complexity is O(1) per test case.

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>

using namespace std;
  
const int maxtn = 1e6, maxt = 2e5, maxch = 1e6, maxeg = 1e6, maxA = 1e6, maxB = 1e6, maxC = 1e6;
int n, eg, ch, A, B, C;
long long solveFull(){
    long long ans = 1e18;
    for(int i = 0; i <= n; i++){
        long long req = n;
        if(i > eg || i > ch)break;
        long long egl = eg - i, chl = ch - i;
        long long canA = egl / 2, canB = chl / 3, canC = i;
        if(canA + canB + canC < n)continue;
        long long useC = min(canC, req);
        long long val = useC * C;
        req -= useC;
        if(A < B){
            long long useA = min(canA, req);
            val += useA * A;
            req -= useA;
            val += req * B;
            // cout << useA << " " << req << " " << useC << " " << val << endl;
        }else{
            long long useB = min(canB, req);
            val += useB * B;
            req -= useB;
            val += req * A;
        }
        ans = min(ans, val);
    } 
    return ans;
}
long long solvePartial(){
    long long ans = 1e18;
    for(long long useA = 0; useA <= n; useA++){
        for(long long useB = 0; useB + useA <= n; useB++){
            long long useC = n - useA - useB;
            long long egUsed = 2 * useA + useC, chUsed = 3 * useB + useC;
            if(chUsed > ch)break;
            if(egUsed > eg)continue;
            ans = min(ans, useA * A + useB * B + useC * C);
        }
    } 
    return ans;   
}
int main()
{ 
    int t; cin >> t; 
    int tn = 0;
    while(t--){
        cin >> n >> eg >> ch >> A >> B >> C;
        tn += n;
        long long ans = n <= 100 ? solvePartial() : solveFull(); 
        // long long ans = solvePartial(); 
        ans = (ans > 1e12 ? -1 : ans);
        cout << ans << endl;
    }
    assert(tn <= maxtn);
} 
Tester's Solution
t = int(raw_input())
while t > 0:
  t -= 1
  n, eggs, bars, price_ome, price_milk, price_cake = map(int, raw_input().split(' '))
  w_eggs, w_bars = 2, 3
  if price_ome > price_milk:
    price_ome, price_milk = price_milk, price_ome
    w_eggs, w_bars = w_bars, w_eggs
    eggs, bars = bars, eggs

  ans = 10**18
  for cake in range(0, n + 1):
    if eggs >= cake and bars >= cake:
      used_ome = min(n - cake, (eggs - cake) / w_eggs)
      used_milk = min(n - cake - used_ome, (bars - cake) / w_bars)
      if cake + used_ome + used_milk == n:
        ans = min(ans, cake * price_cake + used_ome * price_ome + used_milk * price_milk)

  if ans == 10**18:
    ans = -1

  print(ans)
Editorialist's Solution
import java.util.*;
import java.io.*;
class COLGLF4{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), E = ni(), H = ni();
        long A = ni(), B = ni(), C = ni();
        
        long best = Long.MAX_VALUE;
        //Iterating over number of chocolate cake
        for(int chocolateCakes = 0; chocolateCakes <= N; chocolateCakes++){
            int e = E-chocolateCakes, h = H-chocolateCakes;
            if(e < 0 || h < 0)continue;
            
            //Maximum omelette and chocolate milkshake possible, if x chocolate cakes are ordered
            int omelettes = e/2, chocolateMilkshakes = h/3;
            
            if(chocolateCakes+omelettes+chocolateMilkshakes < N)continue;//N orders not possible
            
            int orders = N-chocolateCakes;//number of orders to be made
            if(A <= B){
                //Prefering omelette over chocolate milkshake
                long cost = chocolateCakes*C;
                int min = Math.min(orders, omelettes);
                cost += min*A;
                orders -= min;
                min = Math.min(orders, chocolateMilkshakes);
                cost += min*B;
                
                best = Math.min(best, cost);
            }else{
                long cost = chocolateCakes*C;
                int min = Math.min(orders, chocolateMilkshakes);
                cost += min*B;
                orders -= min;
                min = Math.min(orders, omelettes);
                cost += min*A;
                
                best = Math.min(best, cost);
            }
        }
        if(best == Long.MAX_VALUE)pn(-1);
        else pn(best);
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new COLGLF4().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

9 Likes

Cool Problem! enjoyed wasting time by not reading the last constraint. O(1) per testcase solution. graph

9 Likes

Saw your solution man it’s good.

2 Likes

bro :boom: :boom: :boom:

1 Like

when ratings will be alloted ??

Hey!
I also tried this problem by a similar method as yours i.e. linear programming.
I calculated the cost for all boundary solutions to get the minimum cost. I also checked if the optimum solution point (X, Y) has integer coordinates or not,
if ( X and Y both are integers) answer = ObjectiveFunction(X,Y);
else {
X = floor(X); Y = floor(Y);
check if (X+1,Y), (X,Y+1) and (X,Y) satisfy the constraints;
answer = min(ObjectiveFunction(X+1,Y), ObjectiveFunction(X,Y+1), ObjectiveFunction(X,Y));
}

Can anyone please help, what I’m doing wrong?
https://www.codechef.com/viewsolution/43732034

Firstly, I think you missed some intersection points (check my code for all points).
Secondly, not just the floor, sometimes we have to search all neighbours at dist 2. try tweaking the values of E, H, in the graph to get the case which is failing.

2 Likes

Okay, thanks!
Integer linear optimization is NP-hard so I didn’t go that way and thought that the optimum solution in that case (if X and Y are not integers) would be either ([X]+1, [Y]) or ([X], [Y] + 1) or ([X], [Y]) depending upon if it satisfies the constraints and results in min cost.
Thanks again!

Why greedy approach fails?

In this problem, the solution must have integer values, which makes it an Integer Programming problem, NP complete. This is why Linear Programming approach is not correct here.

I have updated editorial now.

1 Like

I chose the greedy approach by finding the minimum individual price…like minimum of A,B,C…then chose the minimum ones…if they get over then second minimum and so on…I also considered the case when output will be -1…if(e<2n && h<3n && (e<n || h<n)) but it failed…can anyone please explain why it failed

Though it was passing the sample test case and some personalized cases

Exactly! Even I wondered about NP completeness, but we can effectively remove z by substitution z = N - x - y and convert it into two-dimensional ILP with additional constraints like x + y \le N, x\ge0, y\ge0.
Usually, ILP won’t work when we’re approximating near intersection points; but here it will work because of the nature of the objective function:
A*x +B*y+C*z which is a plane and will be smoothly inclined.

2 Likes

@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 ?

https://www.codechef.com/viewsolution/43834404

Easiest problem of this long challenge