CLEARARR - Editorial

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)
7 Likes

I understood that the problem asks us to remove at every turn either the first element or the last element of the array or both. Is this incorrect?

If Any one has implemented any dp solution or o(nk) solution please share it!!!

6 Likes

or both

Yes, I forgot to mention that we can also remove both elements. My main concern is that, is it necessary to always work over the first and last element of the array?

1 Like

DP solution but gives TLE!!!

int DP[5005][5005];
int min_cost(int a[], int k, int x, int left, int right) {
if (right < left)return 0;
if (DP[left][right] != -1)return DP[left][right];
if (left == right) {
return DP[left][right] = a[left];
}
int include = INT_MAX;
int left_sum = a[left] + min_cost(a, k, x, left + 1, right);
int right_sum = a[right] + min_cost(a, k, x, left, right - 1);
if (k) {
include = x + min_cost(a, k - 1, x, left + 1, right - 1);
}
return DP[left][right] = min(left_sum, min(right_sum, include));
}
void solve() {
int n, k, x;
cin >> n >> k >> x;
int a[n];
memset(DP, -1, sizeof DP);

f(i, 0, n) {
	cin >> a[i];
}
cout << min_cost(a, k, x, 0, n - 1) << nl;

}

can anyone tell me what test case i missed ?
https://www.codechef.com/viewsolution/50124850

1
2 1 5
4 4

You print 8, the answer is 5 (just take both elements at once)

1 Like

The problem in itself is not that clear, it tells us to only remove elements from left, right, or from both at a time, but acc. to the editorial it seems like the position of the elements doesn’t matter, let’s say I have this array 9 10 11 12 13 if I want to do the third operation on max 2 elements here 12 and 13 the I won’t be able to the third operation anymore, because to perform the third operation on 12 and 13 I have to first remove 9 10 and 11 one by one.

3 Likes

The problem is quite clear - you can indeed only remove elements from the ends of the array; whether that is one at a time or both at the same time.

The editorial proves that this restriction doesn’t matter because no matter which 2K elements you want to remove, there is a way to do so by only removing from the ends.

In your example, as you have correctly noted, if you want to remove 12 and 13 at the same time you have to first remove 9, 10 and 11 one by one.

If the array was instead 1 100 2 101 3, then to remove the 100 and the 101 using the operation you can:
Remove 1 → Remove 3 → Remove 100 and 101 together → Remove 2

Of course, these are just specific examples. As I mentioned before, the editorial includes a formal proof as to why this is always possible.

2 Likes

Ok so what you are saying is that let’s say if for this example
1
5 2 7
9 10 11 12 13
I first convert 12 + 13 to x then 11 + 10 to x, then it doesn’t matter which way I do it because its value would be the same if we do 10 + 13 to x and 11 + 12 to x, which means I can produce any combination to get the optimal solution given that a + b > x, where a and b are elements of the array right?

1 Like

Yes, exactly.
In the end, it doesn’t really matter which element was chosen in which pair - only which elements were chosen overall.

2 Likes

I tried implementing a similar DP Solution, but it’s giving TLE.

1 Like

DP Solution but giving tle

#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define nline “\n”
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif
void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template void _print(vector v);
template void _print(set v);
template <class T, class V> void _print(map <T, V> v);
template void _print(multiset v);
template <class T, class V> void _print(pair <T, V> p) {cerr << “{”; _print(p.ff); cerr << “,”; _print(p.ss); cerr << “}”;}
template void _print(vector v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template void _print(set v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template void _print(multiset v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << “]”;}
const int N = 1e4;
ll dp[N ][N] ;
ll fun(vector v, ll l, ll r, ll x, ll k) {
if (l > r) {
return 0;
}
// ll ans = 0;
if (dp[l][r] != -1) {
return dp[l][r];
}
if (k > 0 && v[l] + v[r] > x) {
if (r - l != 0) {
if (v[l] < v[r]) {
dp[l][r] = min(x + fun(v, l + 1, r - 1, x, --k), v[l] + fun(v, l + 1, r, x, k));
}
else {
dp[l][r] = min(x + fun(v, l + 1, r - 1, x, --k), v[r] + fun(v, l, r - 1, x, k));
}
}
else {
if (v[l] < v[r]) {
dp[l][r] = v[l] + fun(v, l + 1, r, x, k);
}
else {
dp[l][r] = v[r] + fun(v, l, r - 1, x, k);
}
}
}
else {
if (v[l] < v[r]) {
dp[l][r] = v[l] + fun(v, l + 1, r, x, k);
}
else {
dp[l][r] = v[r] + fun(v, l, r - 1, x, k);
}

}
return dp[l ][r];

}
void solve() {
ll n, k, x;
cin >> n >> k >> x;
vector v(n);
for (auto &x : v) {
cin >> x;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
dp[i][j] = -1;
}
}
cout << fun(v, 0, n - 1, x, k) << nline;
// cout << “h”;
// cout << dp[0][n - 1];
}

int main() {
fastio();
#ifndef ONLINE_JUDGE
freopen(“Error1.txt”, “w”, stderr);
#endif
int t; cin >> t;
while (t–)
solve();
cerr << “\n” << (float)clock() / CLOCKS_PER_SEC * 1000 << “ms” << endl;
}

The O(N^2K) DP solution wasn’t intended to pass all test cases in the time limit.

The question asked us to remove elements either from left, right, or both sides from the input array. How is sorting allowed here, it changes the complete question it basically means that we are picking random indexes from the input array just to apply the greedy approach.

This question must have been solved without sorting otherwise many of us who tried to frame a logic for not making changes to the input array are at disadvantage.
Kindly inform me regarding this, I may be wrong, just want to clarify :slight_smile:

This can not be possibly correct, we were not allowed to choose a pair by our choice, rather only the extreme values can be made a pair

Basically here, order doesn’t matter as we can bring those max numbers as extreme left or right by using first 2 operations and use 3rd step on them when they acquire those positions ( of course if there sum is less than the fixed value). Hope you got it.

[solution in O(n(log(n))]

https://www.codechef.com/status/CLEARARR,aman_singh_20

  • Firstly input the array and sort it.
  • iterate from the last so as to remove the larger values first ( if((arr[i]+arr[i-1])>=x)&&i>0 ) then remove both the value and increase your answer.
  • if k==0 then iterate it till i=0 and add all arr[i] to answer
    this is one of the simple approach.
    :slight_smile:

This post was flagged by the community and is temporarily hidden.