RESELL - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N items.
The i-th item can be resold for a value of A_i.

You can buy however many items you like, and in any order.
The first K items will be sold at a price of 5 coins, everything else will be sold at 10 coins.

Find the maximum possible profit you can obtain by reselling.

EXPLANATION:

Suppose we have decided to buy X items in total.
Then, it’s clearly optimal to buy the X items with highest resell values, i.e. choose the X largest elements of A.

As for costs,

  • If X \le K, all X items can be bought for 5 coins.
  • If X \gt K, we must buy K items for 5 coins and the remaining (X - K) items for 10 coins.
    The order of buying doesn’t matter here (given that we’ve decided to buy exactly X items), and the total cost is simply 5\cdot K + 10\cdot (X - K).

So, the overall profit when buying X items equals the sum of the X largest elements of A, minus the cost of buying the items (which is either 5\cdot X or 5\cdot K + 10\cdot (X - K) depending on whether X \le K or not.)

Finding the largest X items can be done by, for example, sorting the array A in descending order.

Since we’re free to choose how many items we want to buy (i.e. the value X), we can simply try every value of X from 0 to N and compute the resulting profit; then in the end report the maximum among them.

This can be done in \mathcal{O}(N^2) or even \mathcal{O}(N) after sorting.
The constraints are low so either approach will pass.

TIME COMPLEXITY:

\mathcal{O}(N^2) or \mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        vector a(n, 0);
        for (int &x : a) cin >> x;

        ranges::sort(a);
        ranges::reverse(a);
        
        int ans = 0, cost = 0, value = 0;
        for (int i = 0; i < n; ++i) {
            value += a[i];
            if (i < k) cost += 5;
            else cost += 10;
            ans = max(ans, value - cost);
        }

        cout << ans << '\n';
    }
}