PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Daanish Mahajan
Tester: Riley Borgard
Editorialist: Aman Dwivedi
DIFFICULTY
Cakewalk
PREREQUISITES
None
PROBLEM
Given an array of size, N determine the maximum total cost sum that you can achieve by alternately choosing K costliest gifts where 2 \times K+1\leq N.The one starting second gets to keep one more gift.
QUICK EXPLANATION
Choosing maximum value gifts results in maximum total cost sum. Let the maximum total cost sum by you and your twin is sum1 and sum2 respectively. Now, maximum of sum1 and sum2 is answer.
EXPLANATION
- Now in order to calculate sum1 and sum2, we need to choose gifts in such a way that it maximizes the total cost of gifts.
- In each turn choosing the costliest gift from the array and adding it, results in the maximum total cost of gifts.
- So we sort the array in decreasing order of their cost and alternately choose elements starting from the beginning of the array and add it to their respective sums.
Let’s take an example to understand it better.
-
a= [4,2,1,3,5,6], K=2 and sum1=0,sum2=0
-
Sort the array, a = [6,5,4,3,2,1]
-
Let’s suppose you start first.
-
It’s your turn and you choose the costliest gift i.e a[0] =6 and sum1=6
-
It’s your twin’s turn and he chooses the costliest gift i.e a[1]=5 and sum2=5
-
It’s your turn and you choose the costliest gift i.e a[2]=4 and sum1=6+4=10
-
It’s your twin’s turn and he choose the costliest gift i.e a[3]=3 and sum2=5+3=8
-
Since your twin started second, therefore he gets choose one more gift and choose the costliest gift i.e a[4]=2 and sum2=8+2=10.
-
Now if sum2 is greater than sum1, then you would want to start second and vice-versa. Therefore, the maximum of sum1 and sum2 is the answer.
TIME COMPLEXITY
The time complexity is O(N*logN) per test case.
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
ll TC;
cin >> TC;
while (TC--)
{
ll n, k; cin >> n >> k;
vector<ll> arr(n);
for (auto &x : arr) cin >> x;
ll s1 = 0, s2 = 0;
sort(arr.begin(), arr.end());
while (k--) {
s1 += arr.back(); arr.pop_back();
s2 += arr.back(); arr.pop_back();
}
s2 += arr.back();
cout << max(s1, s2) << '\n';
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
void solve() {
int n, k;
cin >> n >> k;
vector<ll> a(n);
for(auto &x : a) cin >> x;
sort(all(a), greater<>());
ll A = 0, B = 0;
rep(i, 0, 2 * k) {
(i % 2 == 0 ? A : B) += a[i];
}
B += a[2 * k];
cout << max(A, B) << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int te;
cin >> te;
while(te--) solve();
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long int
void solve()
{
int n, k;
cin >> n >> k;
int a[n];
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
int sum1 = 0, sum2 = 0;
int i = n - 1;
while (k--)
{
sum1 += a[i];
sum2 += a[i - 1];
i -= 2;
}
sum2 += a[i];
cout << max(sum1, sum2) << endl;
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}
