## PROBLEM LINK

**Author:** Sunny Aggarwal

**Tester:** Alex Gu and Pushkar Mishra

**Editorialist:** Prateek Gupta

**Russian Translator:** Vitalij Kozhukhivskij

**Vietnamese Translator:** Khanh Xuan Nguyen

**Mandarian Translator:** Gedi Zheng

**Contest Admin:** Praveen Dhinwa and Pushkar Mishra

## DIFFICULTY:

Simple

## PREREQUISITES:

None

## PROBLEM:

Given an array of size N, you have to reduce the array into a single element by repeatedly applying a single operation.

The operation involves picking up two adjacent elements in the array and remove larger of them by paying a cost equal to smaller of them. Minimize the total cost.

## EXPLANATION

**Solution for Subtask 1:**

This subtask can indeed be solved by Bit Masking DP. Check this link to know more about Bit Masking.

In this case, we maintain a state F(mask) where in, set bits of mask represent which all indexes have been removed uptill now. We want to arrive at a state where only the last element i.e only 1 unset bit remains in the final array. The last index remaining will always be the position of minimum element in the array regardless of the order of applied operations. Lets look at the pseudo code to understand how this recurrence works.

```
F(mask) {
if ( __builtin_popcount(mask) == n-1 ) return 0
long long ans = 0
for ( int i = 0; i < n; i++ ) {
if ( !(mask & (1<<i)) ) {
int j = i+1
while ( j < n && (mask&(1<<j)) ) j++
if ( j != n ) {
int remove_idx = (A[i] > A[j]) ? i : j
ans = min(ans, min(A[i],A[j]) + f(mask | (1<<remove_idx)) )
}
}
}
return ans
}
```

Basically, at any particular state, we are checking what all indices are there which have not been removed yet. So for this, we try to apply all kinds of X-1 operations for any X unset bits. We take a bit which is not set, lets call it i, we find the just next unset bit j, which would mean these two are consecutive elements at that particular state and hence, the greater of them can be removed. We do this for all such (i,j) pairs to take the minimum of all answers. Minimum value returned by calling function F(0) will hence be the minimum cost spent to convert the array into a single element. Overall Complexity for this naive approach is \mathcal{O}(2^N*N^2)

**Solution for subtask 2 & 3:**

In order to minimize the total cost, you should surely choose the pair of consecutive integers consisting of the smallest element in the given array. The minimum element will anyway be the last remaining element after all operations have been applied. So, why not choose a pair of consecutive numbers involving this minimum element till the whole array reduces to this minimum element. Since, we need to perform this operation N - 1 times, total cost incurred will hence be equal to (N - 1)*(MINVAL). As answer can be little large, use a data type which can handle larger numbers.

## COMPLEXITY

As minimum value in the array can just be found in a single traversal, overall complexity of the solution is \mathcal{O}(N).