DBDISC - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N food items, the i-th has cost A_i and tastiness B_i.
When buying two items, the more expensive one receives a discount of either 50\% or 100, whichever is smaller.

Find the maximum possible total tastiness when buying exactly two items with a total cost not exceeding K after the discount.

EXPLANATION:

The constraints are small, allowing for a solution that runs in \mathcal{O}(N^2) time.

This means we can simply try all possible combinations of choosing two items.

So, fix i and j to be the two items we’re trying to buy.
Then,

  • The initial cost is A_i + A_j.
  • The discount is applied to the more expensive item, i.e. to \max(A_i, A_j).
    Let this value be M.
  • The value of the discount is either 100 or half of the item’s cost, whichever is smaller.
    That is, \min(100, \frac{M}{2}).
  • So, the overall cost comes out to be A_i + A_j - \min(100, \frac{M}{2}).

If the final cost is \le K, we can buy these two items; so update the answer with B_i + B_j.

In the end, print the maximum tastiness obtained.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (Python3) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    ans = 0
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    for i in range(n):
        for j in range(i+1, n):
            cost = a[i] + a[j]
            disc = min(100, max(a[i], a[j]) // 2)
            if cost - disc <= k:
                ans = max(ans, b[i] + b[j])
    print(ans)