COLDPANI Editorial

editorial
, , ,
1

Cold Water:

SNU CodeChef Chapter Inaugration contest

Author: Jackson Jose
Testers: Nishank Suresh, Kabir Kanha, Vaibhav Gautam, Illisha Singh
Editorialist: Jackson Jose

DIFFICULTY:

EASY

PREREQUISITES:

Greedy, Sorting

PROBLEM:

A lot of guests have suddenly shown up at your house and you only have x litres of cold water (at y °) at the moment. Due to fear of Covid, each guest brings their own bottle, each of which already has M_i litres of water at C_i °. Each of these bottles has infinite capacity.

If you add cool water to the i^{th} bottle, the temperature changes according to the formula T_{final} = \frac{(M_i*C_i + K*y)}{(M_i + K)} where K is the amount of cool water you added.

You wish to maximise the number of containers that have a temperature \leq Q.

Note: It is guaranteed that Q>y.

QUICK EXPLANATION:

Finding the required amount of water for each container to reach the threshold, and then greedily selecting the containers which require the least amount of water is the intended solution.

EXPLANATION:

The problem requires us to maximize the number of container’s with temperature lesser than or equal to the threshold Q. We know that the temperature varies according to the formula T_{final} = \frac{(M_i*C_i + K*y)}{(M_i + K)}, we can do a bit of algebraic manipulation and find the value K (the amount of water of temperature y that has to be added to the container to make its temperature equal to Q the threshold).

Solving the equation for K gives us:
K = \frac{(M_i*(C_i - Q))}{(Q - y)}

Now we can iterate over all containers and find the value K for each container, and store it in an array. Do note that K might come out to be negative in cases where the container’s temperature is already less than the threshold Q, in such a situation we would not add water to the container at all.

        if (containers[i][1] < y) {
            amountRequired[i] = 0;
        } else {
            double aR = (containers[i][0] * (containers[i][1] - Q)) / (Q - y);
            amountRequired[i] = max(0 * 1.0, aR);
        }

So we place a check that does the following if container temperature is less than Q, K = 0, else use the formula.

Now that we know the amount of water required for each container, it would be optimal to select the container which requires the least amount of water. So we do just that, this is also called “Greedy”, i.e. looking for the optimal way at the current step.

To do this we sort the array first, and then iterate over its value’s from the starting index, incrementing the ANS counter if the water left with us is more than or equal to the required amount in the current container and reducing the amount x by the same.

SOLUTIONS:

Setter's Solution in c++ 
#include <bits/stdc++.h>
using namespace std;

void ColdWater() {
    double x, y, Q, n;
    cin >> x >> y >> Q >> n;
    //This just a 2d array
    vector<vector<double>> containers(n, vector<double>(2));
    for (int i = 0; i < n; i++) {
        cin >> containers[i][0] >> containers[i][1];
    }
    // First compute the amount of water required to cool every container up till the threshold
    vector<double> amountRequired(n);
    for (int i = 0; i < n; i++) {
        if (containers[i][1] < y) {
            amountRequired[i] = 0;
        } else {
            double aR = (containers[i][0] * (containers[i][1] - Q)) / (Q - y);
            amountRequired[i] = max(0 * 1.0, aR);
        }
    }
    //Greedily select the containers which require the least amount of water to reach the threshold
    sort(amountRequired.begin(), amountRequired.end());
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (amountRequired[i] <= x) {
            ans++;
            x -= amountRequired[i];
        }
    }
    cout << ans << "\n";
}
int main() {
    int test;
    cin >> test;
    while (test-- > 0) {
        ColdWater();
    }
    return 0;
}
Tester's Solution (Kabir Kanha) in java 
import java.util.*;
public class Main {
public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int t = scanner.nextInt();
    while (t-- > 0) {
        double x = scanner.nextDouble();    // IMPORTANT: Do not declare this as int
        int y = scanner.nextInt();
        int Q = scanner.nextInt();
        int n = scanner.nextInt();

        // List to store the required amounts for each bottle.
        ArrayList<Double> requirements = new ArrayList<>();     // Again, double, not int.
        for (int i = 0; i < n; ++i) {
            int Mi = scanner.nextInt();
            int Ci = scanner.nextInt();
            // Calculate the amount of cold water required by bottle i.
            // Brackets must be put precisely.
            double k = Ci <= Q ? 0.0 : (1.0 * Mi * (Ci - Q)) / (Q - y);    
            requirements.add(k);
        }

        // Pick as many bottles greedily as possible.
        int ans = 0;
        Collections.sort(requirements);
        for (double requirement : requirements) {
            if (x >= requirement) {
                ans++;
                x -= requirement;
            }
        }
        System.out.println(ans);
    }
}
}
Tester's Solution (Vaibhav Gautam) in python 
T = int(input())
while T > 0:
x,y,q,n=[int(i) for i in input().split()]
    MC = []
    arr_k = []
    for i in range(0, n):
        m, c = map(int, input().split())
        MC.append((m, c))
        k = (m * c - q * m) / (q - y)
        arr_k.append(max(0, k))
    arr_k.sort()
    water_added = 0
    ans = 0
    for i in range(0, n):
        if water_added + arr_k[i] <= x:
            water_added += arr_k[i]
            ans += 1
    print(ans)
    T -= 1
1 Like