MOONSOON - Editorial

editorial
, ,
1

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
2

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
3

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

1 Like
4

Ok, thanks for helping!

6

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);
	}
}
7

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

8

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;

}