Leetcode 1648 - Sell Diminishing-Valued Colored Balls

Subscribe Send me a message home page tags


Problem Description

Leetcode 1648

You have an inventory of different colored balls, and there is a customer that wants orders balls of any color.

The customer weirdly values the colored balls. Each colored ball's value is the number of balls of that color you currently have in your inventory. For example, if you own 6 yellow balls, the customer would pay 6 for the first yellow ball. After the transaction, there are only 5 yellow balls left, so the next yellow ball is then valued at 5 (i.e., the value of the balls decreases as you sell more to the customer).

You are given an integer array, inventory, where inventory[i] represents the number of balls of the ith color that you initially own. You are also given an integer orders, which represents the total number of balls that the customer wants. You can sell the balls in any order.

Return the maximum total value that you can attain after selling orders colored balls. As the answer may be too large, return it modulo 10^9 + 7.

Solution

It's obvious we need to start with the largest inventory because the first item in that inventory offers the maximum value.

We assume the inventory list is sorted by decreasing order for the sake of simplicity (e.g. inventory[0] \( \geqslant \) inventory[1]). It's obvious we need to start with inventory[0] because the first item in that inventory offers the maximum value. We observe that we can keep selecting inventory[0] until inventory[0] == inventory[1].

Now we have (at least) two inventories that has the same number of items. We further assume inventory[0] == inventory[1] > inventory[2]. We observe that we will not select inventory[2] until we have inventory[0] == inventory[1] == inventory[2]. In other words, when inventoreis have the same number of items, they are grouped togher.

Suppowe the inventory = [6, 6, 6] and the order = 7. Here is how we calcaute the value of the order.

[0] [1] [2]
-----------
+    +   +          <--- item in this row has value 6
+    +   +          <--- item in this row has value 5
+    0   0          <--- item in this row has value 4
0    0   0
0    0   0
0    0   0

The columns in the table above represent an inventory. The + indicates the selected items. The calculation of the order value can be divided into two pieces

  1. The value of rows with + only. These rows forms a rectangle.
  2. The value of rows with mixed + and 0

In the following implemenation, we use a priority queue to track the largest inventory and use a hash map to track the number of inventories that have the same number of items. If we sort the inventory list first, we may get rid of both of the priority queue and the hashmap.

Implemenation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

class Solution {

using Count = unordered_map<long, long>;
public:

    static long calculate(long current, long order, Count& count, long module) {
        long c = count.at(current);
        long k = order / c;
        long remaining = order % c;
        return ((current * 2 + 1 - k) * k / 2 * c + remaining * (current - k)) % module;
    }

    static void addOne(Count& count, long k) {
            if (count.find(k) == count.end()) {
                count.emplace(k, 1);
            } else {
                ++count.at(k);
            }
    }

    static bool isVisited(Count& count, long k) {
        return count.find(k) != count.end();
    }


    int maxProfit(vector<int>& inventory, int orders) {
        priority_queue<long> q{};
        Count count{};

        for (auto& k : inventory) {
            if (!isVisited(count, k)) {
                q.push(k);
            }
            addOne(count, k);
        }

        int module = 1000000007;
        long value = 0;

        while (orders > 0) {
            value = value % module;

            long maxValue = q.top();
            q.pop();

            if (q.empty()) {
                value += calculate(maxValue,  orders, count, module);
                return value % module;
            }

            long nextValue  = q.top();
            long availableInventory = (maxValue - nextValue) * count.at(maxValue);

            if (availableInventory >= orders) {
                value += calculate(maxValue, orders, count, module);
                return value % module;
            } else {
                value += calculate(maxValue, availableInventory, count, module);
                count.at(nextValue) += count.at(maxValue);
                count.erase(maxValue);
                orders -= availableInventory;
            }
        }
        return value % module;
    }
};

----- END -----

Welcome to join reddit self-learning community.
Send me a message Subscribe to blog updates

Want some fun stuff?

/static/shopping_demo.png