SUBSETMINMAX - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Sorting

PROBLEM:

For an array A and a binary string S, define f(S) as follows:

  • Collect all A_i such that S_i = 1 into an array B.
  • If B is empty, f(S) = 0
  • Otherwise, f(S) = \min(B) \cdot \max(B)

You can pay X coins to toggle an element of S.
If the final string is S', you will receive f(S') coins.
Find the maximum possible number of coins you can have in the end.

EXPLANATION:

Let’s look at f(S') = \min(B) \cdot \max(B).
To make this larger, we have to make either \max(B) larger or \min(B) larger.

\max(B) is quite easy to deal with: if the maximum element of A is not already present in B, we can spend one operation to toggle its position and include it in B.
No more than one operation is needed here, since clearly \max(B) can’t be larger than \max(A); and wasting operations on including other elements is quite pointless.

That leaves us with several operations to deal with making \min(B) large.
Here, observe that the optimal strategy is to just keep removing the smallest element from B.

In particular, we’ll never need to insert a new element into B to maximize \min(B) - because if the a newly inserted element is the minimum then simply not inserting it would’ve saved one coin but given a larger minimum; and if a newly inserted element is not the minimum then we just wasted a coin inserting it and gaining nothing.

So, our strategy looks like this:

  • (Maybe) toggle \max(A) to include it in B.
  • Then, repeatedly toggle off the smallest existing element in B.
    • Note that this will stop when B has only one remaining element.

We thus have two separate strategies to try:

  1. Don’t include \max(A) into B, and just repeatedly spend X coins to remove the smallest element of B several times.
    By going over elements of B from small to large, we can try all possibilities of the final array and take whichever one gives us the best profit.
  2. Include \max(A) into B.
    This incurs a one-time cost of X coins, after which we can again just simulate all possible deletion choices and take the best profit among them.

Simulation can be done in linear time after sorting, so the complexity is \mathcal{O}(N\log N).

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3) 
def calc(b, x):
    if len(b) == 0: return 0
    best, cost = 0, 0
    for y in b:
        best = max(best, y * b[-1] - cost)
        cost += x
    return best

for _ in range(int(input())):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    s = input()
    
    mx = max(a)
    b = []
    for i in range(n):
        if s[i] == '1':
            b.append(a[i])
    b.sort()

    ans = calc(b, x)
    if mx not in b: ans = max(ans, calc(b + [mx], x) - x)
    print(ans)
1 Like