12CUnreviewed1100GPT-5.5 (high)

Fruits

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

greedy implementation sortings

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

The order of Valera's list is a distraction. What matters is how many times each fruit name appears.

If a fruit appears $c$ times and gets price $p$ , its contribution is $c \cdot p$ . So the total is a sum over distinct fruits, not over list lines directly.

There may be more price tags than fruit types Valera needs. Since all counts are positive, for the minimum you only care about the cheapest $d$ tags, and for the maximum the most expensive $d$ tags, where $d$ is the number of distinct listed fruits.

Now it is just pairing frequencies with prices. To minimize, large frequencies should get small prices. To maximize, large frequencies should get large prices. This is the rearrangement inequality doing all the work while pretending to be greedy.

Count frequencies, sort them decreasing. Sort prices increasing. Then

\text{min} = \sum_{i=0}^{d-1} freq_i \cdot price_i

and

\text{max} = \sum_{i=0}^{d-1} freq_i \cdot price_{n-1-i}.

Key observation

The actual fruit names are mostly noise. We only need to know how many times each distinct fruit appears in Valera's list.

If some fruit appears $c$ times and Ashot assigns it price $p$ , then that fruit contributes

c \cdot p

to the total cost.

So after counting the list, the problem becomes:

Given frequencies $freq_1, freq_2, \dots, freq_d$ and $n$ price tags, assign one price to each of these $d$ fruits to minimize or maximize
$\sum_{i=1}^{d} freq_i \cdot price_i.$

Here $d$ is the number of distinct fruits in the list, and the statement guarantees $d \le n$ .

Which price tags matter?

For the minimum, every frequency is positive, so assigning a larger price instead of a smaller unused one can only make the sum worse. Therefore, the minimum uses the cheapest $d$ price tags.

For the maximum, similarly, it uses the most expensive $d$ price tags. The unused tags can be slapped onto fruits Valera does not buy. Ashot can do that; nobody cares.

How to pair them?

For minimization, big frequencies should get small prices.

Suppose $a \ge b$ are two frequencies and $x \le y$ are two prices. Compare the two pairings:

a \cdot x + b \cdot y

versus

a \cdot y + b \cdot x.

Their difference is

(a \cdot x + b \cdot y) - (a \cdot y + b \cdot x) = (a-b)(x-y) \le 0.

So pairing the larger frequency with the smaller price is never worse. That proves the greedy pairing.

For maximization, flip the logic: pair large frequencies with large prices.

Algorithm

Read prices.
Count occurrences of each fruit name using a map.
Store all frequencies in a vector.
Sort frequencies in decreasing order.
Sort prices in increasing order.
Let $d$ $d$ be the number of distinct fruits.
- Minimum: pair $freq_i$ with price[i].
- Maximum: pair $freq_i$ with price[n - 1 - i].

Formally:

mn = \sum_{i=0}^{d-1} freq_i \cdot price_i

mx = \sum_{i=0}^{d-1} freq_i \cdot price_{n-1-i}

Complexity

Sorting dominates:

O(n \log n + d \log d)

with $d \le m \le 100$ , so this is hilariously fast. Memory usage is

O(n + d).

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int n, m;
    cin >> n >> m;

    vector<int> price(n);
    for (int &x : price) cin >> x;

    map<string, int> cnt;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        cnt[s]++;
    }

    vector<int> freq;
    for (auto &it : cnt) freq.push_back(it.second);

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

    int d = (int)freq.size();
    int mn = 0, mx = 0;

    for (int i = 0; i < d; i++) {
        mn += freq[i] * price[i];
        mx += freq[i] * price[n - 1 - i];
    }

    cout << mn << ' ' << mx << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();

    int n, m;
    cin >> n >> m;

    vector<int> price(n);
    for (int &x : price) cin >> x;

    map<string, int> cnt;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;
        cnt[s]++;
    }

    vector<int> freq;
    for (auto &it : cnt) freq.push_back(it.second);

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

    int d = (int)freq.size();
    int mn = 0, mx = 0;

    for (int i = 0; i < d; i++) {
        mn += freq[i] * price[i];
        mx += freq[i] * price[n - 1 - i];
    }

    cout << mn << ' ' << mx << '\n';
    return 0;
}

View on Codeforces Back to the list