PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Vishesh Saraswat
Tester: Shubham Anand Jain
Editorialist: Nishank Suresh
DIFFICULTY:
Easy
PREREQUISITES:
Sorting
PROBLEM:
You have an array A of length N. In one move, you can remove the leftmost element A_l with cost equal to its value, remove the rightmost element A_r with cost equal to its value, or remove both A_l and A_r with cost X. However, the third operation can only be performed at most K times. What is the minimum cost to remove all elements of the array?
QUICK EXPLANATION:
- Notice that any even number of elements can be removed using the third operation, irrespective of their positions, as long at the number of positions is \leq 2K
- Greedily choose as many pairs as possible under this constraint while maximizing the sum of the chosen pairs
- Any unpaired element is taken on its own
EXPLANATION:
A simple upper bound on the answer is sum(A) - where each element is removed one at a time. Lowering it any further requires us to use the operation of removing two elements at once.
Ideally, we would like to be able to use the operation on several of the largest elements of the array, mitigating the cost of picking them individually. It turns out that it is always possible to do so!
Claim: Given any set of 2m indices of the array, where 0\leq m\leq K, there is an order in which operations can be performed such that the elements at these 2m indices are exactly the ones removed by the operation with cost X.
Proof
We prove this by induction on m.
If m = 0 there is nothing to prove - every element is removed individually no matter what.
Now, suppose the claim is true for some 0\leq m < K. We would like to prove it for m+1.
Consider any sequence of 2m + 2 indices 1 \leq i_1 < i_2 < \dots < i_{2m+2} \leq N.
Perform operations as follows:
- individually remove the elements at indices 1, 2, 3, ..., i_1 - 1, i_{2m+2}+1, i_{2m+2}+2, \dots, i_N by applying the first two operations.
- The remaining array now has i_1 and i_{2m+2} as its endpoints - so they can be removed with the third type operation for cost X.
We are then left with a sequence of 2m indices which we would like to remove in pairs, which is possible by the inductive hypothesis. This concludes the proof.
The above claim tells us that we can pick any even-sized subset of indices of the array with size 0 \leq 2m \leq 2K, and remove all those elements for a cost of mX. The remaining elements can be removed one by one. Of course, to minimize the cost, we would like these 2m pairs to have as large a sum as possible.
This immediately leads us to a solution:
- Sort the input array
- Keep pairing off the largest 2 elements of the array until you either have K pairs, or until the sum of the pair falls below X
- Take any unpaired element on its own
This can be done by just iterating once over the sorted array, or even by pushing every element into a max heap and popping two at a time, giving us a solution in \mathcal{O}(N\log N)
It is also possible to get a well-optimized \mathcal{O}(NK) solution to pass.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
SOLUTIONS:
Setter's Solution
#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()
using ll = long long;
const int mod = 1e9+7;
void solve(int tc) {
int n, k;
ll x;
cin >> n >> k >> x;
priority_queue<ll> pq;
for (int i = 0; i < n; ++i) {
ll a;
cin >> a;
pq.push(a);
}
ll ans = 0;
while (k-- and sz(pq) > 1) {
ll a = pq.top();
pq.pop();
ll b = pq.top();
pq.pop();
if (a + b < x) {
pq.push(a);
pq.push(b);
break;
}
ans += x;
}
while (!pq.empty()) {
ans += pq.top();
pq.pop();
}
cout << ans << '\n';
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int tc = 1;
cin >> tc;
for (int i = 1; i <= tc; ++i) solve(i);
return 0;
}
Tester's Solution
//By TheOneYouWant
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
int main(){
fastio;
int tests;
cin >> tests;
while(tests--){
int n; long long int k, x;
cin >> n >> k >> x;
long long int a[n];
for(int i = 0; i < n; i++){
cin >> a[i];
}
sort(a, a+n, greater<long long int>());
long long int ans = 0;
int left = k;
for(int i = 0; i < n; i++){
if(left){
ans += min(a[i] + a[i+1], x);
left--;
i++;
continue;
}
ans += a[i];
}
cout << ans << endl;
}
return 0;
}
Editorialist's Solution
for _ in range(int(input())):
n, k, x = map(int, input().split())
a = list(map(int, input().split()))
ans = sum(a)
a = sorted(a)[::-1]
for i in range(0, 2*k, 2):
if a[i] + a[i+1] >= x:
ans += x - a[i] - a[i+1]
print(ans)