DECDISC - 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 vases, of which you want to buy exactly two. The i-th vase costs A_i.
If you buy vase i, vase i+1 will have a discount of 50\%.
Find the minimum cost of buying two vases.

EXPLANATION:

Suppose you buy two vases, say i and j where i \lt j.
Then,

  • If j = i+1, the cost of the second vase will be halved due to the discount.
    So, the cost here is A_i + \frac{A_j}{2}.
  • If j \gt i+1, the cost of the second vase is unchanged.
    The cost here is A_i + A_j.

Try all possibilities of i and j, which takes \mathcal{O}(N^2) time, and output the minimum cost among them.

It’s also possible to solve the problem in \mathcal{O}(N) time, with a little observation.
There are N-1 possibilities of buying vases i and i+1, try all of them and take the best cost.
For buying vases that are not adjacent, the best option is to just choose the two vases with smallest cost since there’s no discount anyway; so only the minimum and second minimum need to be computed.

TIME COMPLEXITY:

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

CODE:

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

    ans = 200
    
    # Option 1: buy two consecutive vases
    for i in range(n-1):
        ans = min(ans, a[i] + a[i+1] // 2)
    
    # Option 2: buy two non-consecutive vases
    for i in range(n):
        for j in range(i+2, n):
            ans = min(ans, a[i] + a[j])
    print(ans)