MOONSOON - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: yash_daga
Tester: satyam_343
Editorialist: iceknight1093

DIFFICULTY:

1479

PREREQUISITES:

Sorting

PROBLEM:

You have N cars and M power outlets.
The i-th car has energy capacity A_i Watt-hour.
The i-th output provides B_i Watt power.

If you have H hours, what’s the maximum total power that can be charged?
Each car can use at most one charger, each charger can charge at most one car.

EXPLANATION:

Let K = \min(N, M).
Certainly, we can only use at most K outlets, and charge at most K cars.

Since only K outlets can be used, it makes sense to take the best K of them, i.e, the K highest B_i values.
Similarly, it makes sense to take the cars with most capacity - the K largest A_i values.

These can be found by sorting the array in descending order.
Now, let

A_1 \geq A_2 \geq\ldots\geq A_K \\ B_1 \geq B_2 \geq\ldots\geq B_K \\

We’d like to match each outlet to a car.
It’s not hard to see that it’s best to match the best outlet to the highest-capacity car, the second best outlet to the second highest-capacity car, and so on.
That is, it’s optimal to match A_i with B_i for each 1 \leq i \leq K. A proof can be found below.

Matching A_i with B_i gives us a total of \min(A_i, H\cdot B_i) energy.
So, after sorting as above, the answer is simply

\sum_{i=1}^K \min(A_i, H\cdot B_i)

Proof of the greedy choice

Suppose A_1 is not matched with B_1.
Let A_1 be matched with B_j, and B_1 be matched with A_i.
Here, i, j \gt 1.

Consider what happens if we match A_1 with B_1 and A_i with B_j instead.

  • Initially, A_1 was matched with B_j and B_1 with A_i.
    This provided a total of \min(A_1, H\cdot B_j) + \min(A_j, H\cdot B_1) power.
  • After swapping, they’ll instead provide \min(A_1, H\cdot B_1) + \min(A_i, H\cdot B_j) power.
  • A bit of case analysis should tell you that the second expression is certainly not worse than the first; and is sometimes even larger.

This means it’s optimal to match A_1 with B_1.
Once this is done, continue the argument with i = 2, 3, 4, \ldots, K to fix everything.

TIME COMPLEXITY

\mathcal{O}(N\log N) per testcase.

CODE:

Author's code (C++)
#include <bits/stdc++.h>
using namespace std;

int32_t main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n, m, h;
		cin>>n>>m>>h;
		vector <int> a(n), b(m);
		for(int i=0;i<n;i++)
			cin>>a[i];
		for(int i=0;i<m;i++)
			cin>>b[i];
		sort(a.begin(), a.end(), greater <int> ());
		sort(b.begin(), b.end(), greater <int> ());
		long long sum=0;
		for(int i=0;i<min(n, m);i++)
			sum+=min(1ll*a[i], 1ll*b[i]*h);
		cout<<sum<<"\n";
	}
}
Editorialist's code (Python)
for _ in range(int(input())):
    n, m, h = map(int, input().split())
    a = sorted(list(map(int, input().split())))[::-1]
    b = sorted(list(map(int, input().split())))[::-1]
    ans = 0
    for i in range(min(n, m)):
        ans += min(a[i], h*b[i])
    print(ans)
2 Likes

Can anyone explain why this code is wrong

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        StringBuilder str = new StringBuilder();
        int t = scanner.nextInt();
        while (t-- > 0) {
            int n = scanner.nextInt(), m = scanner.nextInt(), h = scanner.nextInt();
            int[] c = new int[n];
            for (int i = 0; i < n; i++) {
                c[i] = scanner.nextInt();
            }
            int[] p = new int[m];
            for (int i = 0; i < m; i++) {
                p[i] = scanner.nextInt();
            }
            Arrays.sort(c);
            Arrays.sort(p);
            long sum = 0;
            int j = n, k = m;
            while (j != 0 && k != 0) {
                j--;
                k--;
                sum += Math.min(c[j], p[k] * h);
            }
            str.append(sum).append("\n");
        }
        System.out.println(str);
    }
}

1 Like

sum += Math.min(c[j], p[k] * h);
Here, p[k] * h can overflow.
Use long there and it should be fine.

1 Like

Ok, thanks for helping!

It does not work for 1TC.I Cannot understand where it goes wrong.Can anyone help please.
/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t–>0)
{
int n_e=sc.nextInt();
int n_otl=sc.nextInt();
int hr=sc.nextInt();

	    int[] e=new int[n_e];
	    for(int i=0;i<n_e;i++)
	        e[i]=sc.nextInt();
	    int[] otl=new int[n_otl];
	   for(int i=0;i<n_otl;i++)
	        otl[i]=sc.nextInt();
	    
	    Arrays.sort(e);
	    Arrays.sort(otl);
	    
	    int j=n_e-1;
	    long s=0;
	    for(int i=otl.length-1;i>=0;i--)
	    {
	        long store=0;
	        long cur=otl[i]*hr;
	        
	        if(cur>=e[j])
	            store=e[j];
	        else
	            {store=cur ; }
	       j--;
	       s=s+store;
	       if(j<0)
	        break;
	    }
	    System.out.println(s);
	}
}

Can you explain how did you come to the conclusion that long needs to be used instead of int?

can anyone tell me why my code is giving wrong answer?
include <bits/stdc++.h>
using namespace std;

int main() {

int t;
cin>>t;
while(t--)
{
	int n, m, h;
	cin>>n>>m>>h;
	vector <int> a(n), b(m);
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int i=0;i<m;i++)
		cin>>b[i];
		for(int i=0;i<m;i++){
		    b[i] = 1ll*b[i]*h;
		}
		sort(a.begin(), a.end(), greater <int> ());
	    sort(b.begin(), b.end(), greater <int> ());
	    long long sum=0;
	    for(int i=0;i<n && i<m;i++)
	    {
	        if(a[i]<=b[i])sum+=1ll*a[i];
	        else sum+=1ll*b[i];
	    }
	    cout<<sum<<endl;
}
return 0;

}