MARKALL - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author:
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You have the N numbers 1, 2, \ldots, N, along with an array A of length N.
You can do the following:

  • Choose an index i, and for cost A_i, either mark every value in [1, i] or every value in [i, N].
  • Each index i can be used this way at most once.

Find the minimum cost to mark all elements.

EXPLANATION:

Let’s call marking [1, i] a “prefix move”, and marking [i, N] a “suffix move”.

Observe that we don’t really require too many operations at all - in particular, it’s never useful to perform more than one prefix move, or more than one suffix move.
It’s easy to see why: for example, if you perform both the prefix moves [1, i] and [1, j], where i \lt j, you could just not perform the move [1, i] instead: the cost reduces, and everything till i stays marked anyway because of the [1, j] move.

So, we have three possibilities: perform only one prefix move, only one suffix move, or both one prefix move and one suffix move.

The first two cases are easy to calculate: if we perform only one prefix move, the only way to mark all elements is to choose i = N, for a cost of A_N.
Similarly, if we perform only one suffix move, the only choice is i = 1, for a cost of A_1.

This leaves the case of performing one prefix move and one suffix move.
Here, it’s not hard to see that the minimum cost is just the sum of the two smallest elements of A - if the smallest element of A is at index x_1 and the second smallest is at index x_2, we can perform a prefix move with the larger index and a suffix move with the smaller one, and everything will be marked.
This is also optimal because we’re forced to pick two different indices, so clearly the answer in this case cannot be smaller than the sum of the two smallest elements of A.

To summarize, the answer is the minimum of:

  • A_1
  • A_N
  • The sum of the two smallest elements of A.

The two smallest elements of A can be quickly found by sorting the array, or even in linear time by finding the minimum, deleting it, and finding the minimum again.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    ans = min(a[0], a[-1])
    a.sort()
    ans = min(ans, a[0] + a[1])
    print(ans)