AMAZAUC - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Sorting

PROBLEM:

N people want buy K tickets (K \lt N).
Person i bids A_i, and can be persuaded to increase their bid by 1 at a cost of C_i coins.

The people with the top K bids win the right to buy tickets, and each of them will pay a number of coins equal to the (K+1)-th largest bid.

Find the maximum possible profit that can be made.

EXPLANATION:

Suppose we persuade the i-th person to increase their bid x_i times.

The total cost of this is then \sum_{i} x_i\cdot C_i.
The income we earn from it is obtained as follows:

  • Define B_i = A_i + x_i. This is the final bid of person i.
  • Sort the elements of B in non-increasing order, so that B_1 \ge\ldots\ge B_N.
  • Then we earn B_{K+1} \cdot K coins.

Let’s fix the value of B_{K+1} (after sorting in non-increasing order), say to Y.
This fixes our income to be Y\cdot K.
The profit is hence Y\cdot K - \sum_{i} x_i\cdot C_i, and to maximize this, we want to minimize \sum_i x_i\cdot C_i.

However, we also need to ensure that the (K+1)-th largest element is indeed Y.
Thus, we need at least K+1 elements of the form (A_i + x_i) to be \ge Y.

So, let’s compute the minimum cost needed for each element to become \ge Y.
This is fairly easy:

  • If A_i \ge Y, then the cost is 0.
  • Otherwise, it’s optimal to make the element reach exactly Y.
    So, we need (Y - A_i) increments, and the total cost for this element is (Y - A_i) \cdot C_i.

For K+1 elements to become \ge Y, clearly it’s now optimal to just choose the K+1 smallest costs among these.

(Note that technically if we have \ge K+1 elements already larger than Y, then the (K+1)-th largest element of B won’t be equal to Y.
However, it cannot be smaller than Y so our answer can’t get worse; thus we don’t need to care about this.)

So, assuming the value of Y (the final price paid) is fixed, we can compute the optimal profit in \mathcal{O}(N\log N) time: compute the costs needed to make each element \ge Y in linear time, then sort them and find the sum of the K+1 smallest costs.

The question now is, what should the value of Y be?

The key observation here is that the optimal Y will always be one of the A_i values!
This is because the function f(Y) whose output is the maximum possible profit given Y, is piecewise linear.
That is, if Y_1 \lt Y_2 are two array elements such that no other array element lies in the range (Y_1, Y_2), then the function f(Y) will look like a line segment from f(Y_1) to f(Y_2).

Since it’s a line segment, the maximum value on this segment must occur at one of the endpoints.

Applying this to each pair of consecutive values tells us that the global maximum must also occur at some array value, since those are exactly the line segment endpoints.

This gives us a rather simple solution: try each A_i as a candidate for Y, compute the maximum possible profit in \mathcal{O}(N\log N), and take the best over all A_i.
This leads to a solution in \mathcal{O}(N^2 \log N) which is fast enough for the given constraints.

It’s also possible to avoid sorting and solve the problem in \mathcal{O}(N^2) time.
To do this, simply replace the sort by a selection algorithm, which can find the (K+1)-th smallest element of the cost array in linear time after which computing the total cost is easy in linear time.
Some languages have this inbuilt: C++ has std::nth_element for example.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    c = list(map(int, input().split()))

    ans = 0
    for x in a:
        costs = [0]*n
        for i in range(n):
            costs[i] = c[i]*max(0, x - a[i])
        costs.sort()
        curcost = sum(costs[:k+1])
        ans = max(ans, x*k - curcost)
    print(ans)
2 Likes