MINBUY - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: mathmodel
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

cakewalk

PREREQUISITES:

Sorting

PROBLEM:

There are N types of coins. The i-th type has value A_i, and you have B_i of them.
You would like to buy an item with cost X. What’s the minimum number of distinct types of coins you need?

EXPLANATION:

Our objective is to minimize the number of distinct coin types we need, and we’re allowed to pay more than X. So, if decide to use even one coin of some type, there’s no harm in using all coins of that type - the number of distinct types doesn’t change, after all.

So, the i-th type of coin essentially gives us a value of A_i\cdot B_i to work with.

Since the aim is to minimize the number of types used, it’s better to choose high-value coin types first.
This gives us a fairly simple solution:

  1. Sort the coins in descending order of their A_i\cdot B_i values.
  2. Greedily choose coins in this order. If the sum of values ever becomes \geq X, stop immediately and print the number of types of coins used. If X is never reached, the answer is -1.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    indices = list(range(n))
    indices.sort(key = lambda x: - a[x] * b[x])
    sm = 0
    for i in range(n):
        sm += a[indices[i]] * b[indices[i]]
        if sm >= x:
            print(i+1)
            break
    if sm < x: print(-1)