GAME_XI - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: yash_daga
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given the skill levels of N batsmen and M bowlers (A_i and B_i, respectively).
Find the maximum possible sum of skill levels of a team of 11 players that includes at least 4 batsmen and at least 4 bowlers.

EXPLANATION:

First off, if N \lt 4 or M \lt 4 or N+M \lt 11, it’s impossible to pick a team at all.

Otherwise, it’s always possible to form a valid team, so we only need to maximize the sum of skill levels.

We need to choose at least 4 each of batsmen and bowlers, so do that first: pick the largest 4 values each from A and B.
This leaves us with 3 more people to be chosen, but now it doesn’t matter whether they’re batsmen or bowlers (i.e chosen from A or B).

So, take all the remaining (N-4) + (M-4) elements into a single list, and then choose the largest three elements of this list.

Finding the largest 3 or 4 elements of a list can be done quickly by sorting it.

TIME COMPLEXITY:

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

CODE:

Tester's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n, m; cin >> n >> m;
    
    vector <int> a(n);
    for (auto &x : a) cin >> x;
    vector <int> b(m);
    for (auto &x : b) cin >> x;
    
    if (n < 4 || m < 4 || (n + m) < 11){
        cout << -1 << "\n";
        return;
    }
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    
    int ans = 0;
    int t = 4;
    while (t--){
        ans += a.back();
        a.pop_back();
    }
    t = 4;
    while (t--){
        ans += b.back();
        b.pop_back();
    }
    
    vector <int> c;
    for (auto x : a) c.push_back(x);
    for (auto x : b) c.push_back(x);
    sort(c.begin(), c.end());
    t = 3;
    while (t--){
        ans += c.back(); c.pop_back();
    }
    
    cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    if min(n, m) < 4 or n+m < 11:
        print(-1)
        continue
    a, b = sorted(a), sorted(b)
    ans = sum(a[-4:]) + sum(b[-4:])
    c = sorted(a[:-4] + b[:-4])
    ans += sum(c[-3:])
    print(ans)
1 Like
2 
#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int solver(vector<int> bat, vector<int> bol, int n, int m){
    sort(bat.begin(), bat.end());
    sort(bol.begin(), bol.end());
    reverse(bat.begin(), bat.end());
    reverse(bol.begin(), bol.end());
    
    int total_skill=0;
    
    for(int i=0;i<4;i++) total_skill+=(bat[i]+bol[i]);
    // cout<<total_skill<<endl;
    int total_player_left=3;
    int i=4, j=4;  
    while(i<n && j<m && total_player_left){
        if(bat[i]>bol[j]){
            total_skill+=bat[i];
            i++;
            total_player_left--;
        }else{
            total_skill+=bol[j];
            j++;
            total_player_left--;
        }
    }
    while(total_player_left && i<n && j==m){
        total_skill+=bat[i];
        total_player_left--;
        i++;
    }
    while(total_player_left && j<m && i==n){
        total_skill+=bol[j];
        total_player_left--;
        j++;
    }



    return total_skill;
}
int main(){
    int t;
    cin>>t;
    int n, m;
    while(t--){
        
        cin>>n>>m;
        // cout<<n<<" "<<m<<" "<<n+m<<endl;
        if(n<4 || m<4 || (n+m)<11){
            vector<int> bat (n, 0);
            vector<int> bol(m, 0);
            for(int i=0;i<n;i++){
                cin>>bat[i];
            }
            for(int j=0;j<m;j++){
                cin>>bol[j];
            }
            
            cout<<"-1"<<endl;
            continue;

            
        }else{
            vector<int> bat (n, 0);
            vector<int> bol(m, 0);
            for(int i=0;i<n;i++){
                cin>>bat[i];
            }
            for(int j=0;j<m;j++){
                cin>>bol[j];
            }
            cout<<solver(bat, bol, n, m)<<endl;;
        }

    }
    
    return 0;
}

can someone please figure out what is the problem with this code, and why this isn’t working for this problem. Its giving a wrong answer.

1 Like
3

getting runtime error while using 2 pointer approach

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    long long t;
    cin >> t;
    while (t--) {
        long long m, n;
        cin >> m >> n;
        if (m < 4 || n < 4 || m + n < 11) {
            cout << -1 << endl;
            continue;
        }

        vector<long long> bat(m), bow(n);
        
        for (long long i = 0; i < m; i++) {
            cin >> bat[i];
        }
        for (long long i = 0; i < n; i++) {
            cin >> bow[i];
        }
        sort(bat.rbegin(), bat.rend());
        sort(bow.rbegin(), bow.rend());

        long long ans = 0;
        long long x = 0, y = 0;

        for (long long i = 0; i < 4; i++) {
            ans += bat[x++];
            ans += bow[y++];
        }
        long long rem = 3;
        while (rem > 0) {
            if (x < m && y < n) {
                if (bat[x] > bow[y]) {
                    ans += bat[x++];
                } else {
                    ans += bow[y++];
                }
            } else if (x < m) {
                ans += bat[x++];
            } else {
                ans += bow[y++];
            }
            rem-=1;
        }
        
        cout << ans << endl;
    }
    return 0;
}
1 Like
4

i’m getting runtime error after passing some test case and i can’t figure it out .
my approach is i took a vector in which i took all the elements and then sort it and took the sum of 11 elements from the last

//Pranav 
//lets go------------->
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

void solve(){
    ll n,m;
    cin>>n>>m;
    if(n+m<11 || n<4 ||m<4){
        cout<<-1<<endl;
    }else{
        vector<ll> arr(n+m);
        for(int i =0;i<n;i++){
            cin>>arr[i];
        }
        for(int i =0;i<m;i++){
            cin>>arr[n+i];
        }
        sort(arr.begin(),arr.end());
        int i = (n+m)-11;
        ll sum =0;
        for(int j =i;j<arr.size();j++){
            sum += arr[j];
        }
        cout<<sum<<endl;
    }
}

int main() {
    int t;
    cin>>t;
    while(t--){
        solve();
    }

}
1 Like
5

You are using int variables

Constraints says there can be numbers up to 10^9
The sum of 11 players with skill 10^9 is 1.1^11
That overflows your int

Just a comment on your sorting techninque. You don’t need to use reverse. You can sort it decreasingly.

sort(bat.begin(), bat.end(), greater<int>());

Or

sort(bat.begin(), bat.end(), [](int a, int b){return a > b;});
1 Like
6

@pranav_71 @deep_afk

You both have the same issue, this conditional:

        if (m < 4 || n < 4 || m + n < 11) {
            cout << -1 << endl;
            continue;
        }

You are continuing before time. The numbers of bat and bow are still queued to be inputed by your program, but you ignore them. You need to process them either you use them or not.

1 Like
8

Thanks, working fine now.

9

oky got ya, btw thanks bro!

10 
#include <stdio.h>

int comparator(const void * p1,
    const void * p2)
{
    return ( * (int * ) p1 - * (int * ) p2);
}

int main()
{
    long int t;
    scanf("%ld", & t);
    while (t--)
    {
        long int n, m, sum = 0;
        scanf("%ld %ld", & n, & m);
        long int bt[n], bw[m];
        if (n < 4 || m < 4 || n + m < 11)
        {
            sum = -1;
        }
        else
        {
            for (long int i = 0; i < n; i++)
            {
                scanf("%ld", & bt[i]);
            }
            qsort(bt, n, sizeof(long int), comparator);
            for (long int i = 0; i < m; i++)
            {
                scanf("%ld", & bw[i]);
            }
            qsort(bw, m, sizeof(long int), comparator);
            if (n == 4)
            {
                sum = bt[0] + bt[1] + bt[2] + bt[3] + bw[m - 1] + bw[m - 2] + bw[m - 3] + bw[m - 4] + bw[m - 5] + bw[m - 6] + bw[m - 7];
                // printf("%d\t", sum);
            }
            else if (m == 4)
            {
                sum = bw[0] + bw[1] + bw[2] + bw[3] + bt[n - 1] + bt[n - 2] + bt[n - 3] + bt[n - 4] + bt[n - 5] + bt[n - 6] + bt[n - 7];
                // printf("%d\t", sum);
            }
            else
            {
                sum = bt[n - 1] + bt[n - 2] + bt[n - 3] + bt[n - 4] + bw[m - 1] + bw[m - 2] + bw[m - 3] + bw[m - 4];
                int i = 5, j = 5;
                for (int k = 0; k < 3 && (m - j >= 0 || n - i >= 0); k++)
                {
                    if (m - j >= 0 && (n - i <= 0 || bt[n - i] < bw[m - j]))
                    {
                        sum += bw[m - j];
                        j++;
                    }
                    else if (n - i >= 0 && (m - j <= 0 || bt[n - i] >= bw[m - j]))
                    {
                        sum += bt[n - i];
                        i++;
                    }
                }
            }
        }
        printf("%ld\n", sum);
    }
    return 0;
}

getting a runtime error on the third test case, please help me find the problem in my logic

1 Like
11

You are ignoring the values of “bt” and “bm”.
Either you use them or not, every input must be received

1 Like
12 
import java.util.*;

class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
int i,n,t,m,j,k,p=7,c=0;
long s=0;
Scanner in=new Scanner(System.in);
t=in.nextInt();
for(i=1;i<=t;i++)
{p=7;c=0;
    n=in.nextInt();//batsman
    m=in.nextInt();//bowler
    long bat[]=new long[n];
    long ball[]=new long[m];
    for(j=0;j<n;j++)
    bat[j]=in.nextInt();
    for(j=0;j<m;j++)
    ball[j]=in.nextInt();
    if(n<4||m<4||m+n<11){
    System.out.println("-1");
    continue;}
Arrays.sort(bat);
Arrays.sort(ball);
s=0;
for(j=1;j<=4;j++)
s=s+bat[n-j]+ball[m-j];
for(j=5;j<=p;j++)
{
    if(m-j<0){
    s=s+bat[n-j];
    continue;}
   else if(n-j<0){
    s=s+ball[m-j];
    continue;}
 if(bat[n-j]>ball[m-j])
 s=s+bat[n-j];
else if(ball[m-j]>bat[n-j])
 s=s+ball[m-j];
 else if(bat[n-j]==ball[m-j])
 {c=c+1;
 if(c>1)
 {
     s=s+ball[m-j];
     break;
 }
 s=s+bat[n-j]+ball[m-j];
p=p-1;
}}
System.out.println(s);
	}
}
}

this code is not running for hidden test case can someone help

1 Like
13

Your code were doing things I couldn’t understand when filling the last three places for the team, but I barely got that you weren’t indexing the arrays correctly.

The messy indentation didn’t help.

This a corrected version of your code:


class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
        int i,n,t,m,j,k,p=7,c=0;
        long s=0;
        Scanner in=new Scanner(System.in);
        
        t=in.nextInt();
        for(i=1;i<=t;i++){
            p=7;c=0;
            
            n=in.nextInt();//batsman
            m=in.nextInt();//bowler
            long bat[]=new long[n];
            long ball[]=new long[m];
            for(j=0;j<n;j++)
                bat[j]=in.nextInt();
                
            for(j=0;j<m;j++)
                ball[j]=in.nextInt();
                
            if(n<4||m<4||m+n<11){
                System.out.println("-1");
                continue;
            }
            
            Arrays.sort(bat);
            Arrays.sort(ball);
            
            s=0;
            for(j=1;j<=4;j++)
                s = s+bat[n-j]+ball[m-j];
            
            int bat_ind  = n-5;
            int ball_ind = m-5;
            
            for(j=0;j<3;j++){
                
                if(ball_ind < 0){
                    s=s+bat[bat_ind];
                    bat_ind -= 1;
                }
                
                else if(bat_ind < 0){
                    s=s+ball[ball_ind];
                    ball_ind -= 1;
                }
                
                else if(bat[bat_ind] > ball[ball_ind]){
                    s=s+bat[bat_ind];
                    bat_ind -= 1;
                }
                
                else{
                    s=s+ball[ball_ind];
                    ball_ind -= 1;
                }
            }
            
            System.out.println(s);
        }
	}
}
1 Like