BUYTICK - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

Sorting (optional)

PROBLEM:

There are N seats for a sports game. The i-th seat has a cost of A_i.
Some seats have been bought already - you’re given a binary string S of length N where S_i = 0 if and only if the i-th seat is available.

Find the minimum cost needed to buy K seats among the available ones.

EXPLANATION:

First, if there are less than K free seats, it’s impossible to even buy K seats.
So, in this case the answer is simply -1.

Otherwise, since we don’t really care about which seats exactly we buy, it’s clearly optimal to just buy the K cheapest free seats.

That can be done as follows:

  • Create an array \text{free} that contains the prices of all seats available to us.
    This can be done as follows:
    • Initialize \text{free} = [\ ] to be an empty array.
    • Then, for each i = 1, 2, \ldots, N, if S_i = 0, append A_i to \text{free}.
  • Once \text{free} has been built, sort it in ascending order.
  • After sorting, output the sum of the first K elements of \text{free}.

Sorting can be done in either \mathcal{O}(N^2) or \mathcal{O}(N\log N) depending on the algorithm you choose; here, N is small enough that either one will work just fine.

An alternate solution is to simply run a greedy algorithm K times.
That is, to find the first seat we buy, just iterate through all N seats and find the minimum cost one among those that are available.

After finding the first seat, simply add its cost to the answer, then mark it as bought so that we can’t buy it again.
Then, again iterate through all seats to find the best available one - this will be the second seat we buy.

Repeat this K times to find all K seats that will be bought, giving an algorithm that runs in \mathcal{O}(N\cdot K) time.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    s = input()
    
    if s.count('0') < k:
        print(-1)
        continue
    
    free = []
    for i in range(n):
        if s[i] == '0':
            free.append(a[i])
    
    free.sort()
    print(sum(free[:k]))