Official

D - パソコンの販売 / Selling Computers Editorial by admin Editorial for printing

gpt-6-astra-medium

Overview

Process customers in descending order of their required performance, selling each customer the most expensive unsold computer that meets their requirement. This greedy approach can be implemented efficiently using sorting and a priority queue (heap).

Analysis

Processing customers with higher required performance first

Customers with lower performance requirements can purchase a wider variety of computers, whereas customers with higher performance requirements have fewer options.

For example, suppose there are the following \(2\) computers:

Performance Price
\(10\) \(100\)
\(5\) \(50\)

If there are two customers with requirements \(5\) and \(10\), and we sell the most expensive computer to the customer with requirement \(5\) first, we will no longer be able to sell a computer to the customer with requirement \(10\).

Therefore, we consider processing customers in descending order of their required performance.

We can pick the most expensive valid computer

Let \(c\) be the performance requirement of the current customer. Since the remaining customers are sorted in descending order of requirement, all remaining customers have requirements less than or equal to \(c\).

Therefore, any computer that can be sold to the current customer can also be sold to any of the remaining customers.

From this property, it is always optimal to choose the most expensive unsold computer that can be sold to the current customer. This can be justified by an exchange argument.

Consider an optimal assignment consistent with our choices so far. Let \(x\) be the computer assigned to the current customer in this optimal assignment, and let \(y\) be the most expensive valid computer chosen by our greedy strategy.

  • If \(y\) is already assigned to the current customer, we do nothing.
  • If \(y\) is not assigned to anyone, we can replace \(x\) with \(y\). Since \(B_y \ge B_x\), the total revenue does not decrease.
  • If \(y\) is assigned to a later customer, we can swap their computers: sell \(y\) to the current customer and \(x\) to that later customer. Since \(x\) satisfies the current customer’s requirement, it also satisfies the requirement of the later customer (whose required performance is at most that of the current customer). The total revenue remains unchanged.

Thus, the greedy strategy of picking the most expensive valid computer at each step achieves the maximum revenue.

Speeding up the management of candidate computers

If we check all computers for each customer, the time complexity would be \(O(NM)\), which requires around \(10^{10}\) operations in the worst case.

To avoid this, we also sort the computers in descending order of performance.

Since the customers’ required performance decreases as we process them, the set of available computers that meet the requirement monotonically grows. By adding only newly qualified computers to a heap, we do not need to check all computers every time.

We store the prices of candidate computers in a heap so that we can extract the highest price efficiently.

Algorithm

  1. If \(N < M\), output \(-1\) because there are not enough computers.
  2. Sort the computers in descending order of performance \(A_i\).
  3. Sort the customers in descending order of required performance \(C_j\).
  4. Initialize an empty heap, a total revenue total = 0, and an index i pointing to the first computer that has not yet been added to the heap.
  5. For each customer with required performance requirement, do the following:
    • While the performance of computers[i] is greater than or equal to requirement, push its price into the heap and increment i.
    • If the heap is empty, there is no unsold computer that can be sold to this customer, so output \(-1\) and terminate.
    • Pop the maximum price from the heap and add it to total.
  6. If computers have been sold to all customers, output total.

When processing each customer, after the insertion step, the heap contains all “unsold computers that can be sold to this customer”. Since a sold computer is removed from the heap, no computer will be sold to multiple customers.

Furthermore, from the exchange argument, our greedy choices do not prevent us from achieving a valid assignment for all customers if one existed. Therefore, if the heap becomes empty at any point, we can conclude that it is impossible to sell computers to all customers.

Complexity

  • Time complexity: \(O(N \log N + M \log M + (N+M)\log N)\)
  • Space complexity: \(O(N+M)\)

Sorting the computers and customers takes \(O(N \log N)\) and \(O(M \log M)\) time, respectively. Each computer is pushed into the heap at most once, and an element is popped from the heap once per customer.

Note that since the process terminates early when \(N < M\), we have \(M \le N\) whenever the loop continues, so the time complexity can also be expressed as \(O(N \log N)\).

Implementation Notes

  • Python’s heapq is a min-heap.
    By pushing \(-B_i\) instead of \(B_i\), we can extract elements in descending order of price. In the code, total -= pop(heap) adds the original price to the revenue.

  • A computer can be sold even if its performance is equal to the requirement.
    The condition for adding to the heap is computers[i][0] >= requirement.

  • Do not clear the heap for each customer.
    A computer that was valid for a previous customer is also valid for all subsequent customers. Candidates that were not chosen should remain in the heap for future use.

  • The total revenue can be up to \(10^{14}\).
    While Python handles arbitrarily large integers automatically, other languages require using a \(64\)-bit integer (e.g., long long in C++).

    Source Code

import sys
import heapq


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, m = data[0], data[1]

    if n < m:
        print(-1)
        return

    end = 2 + 2 * n
    computers = [(data[i], data[i + 1]) for i in range(2, end, 2)]
    customers = data[end:end + m]
    del data

    computers.sort(reverse=True)
    customers.sort(reverse=True)

    heap = []
    push = heapq.heappush
    pop = heapq.heappop
    total = 0
    i = 0

    for requirement in customers:
        while i < n and computers[i][0] >= requirement:
            push(heap, -computers[i][1])
            i += 1

        if not heap:
            print(-1)
            return

        total -= pop(heap)

    print(total)


if __name__ == "__main__":
    main()

This editorial was generated by gpt-6-astra-medium.

posted:
last update: