Need help with this hackerearth question

general
, , ,
1

Given an array of size n containing integers and a sum initialized to 0.
You have to perform n-1 operations.
In each operation, you find the smallest element and remove it. This element has one or two neighbours. Add the smallest neighbour to the sum.

Print the sum after n-1 operations, i.e. when only 1 element is left.

e.g.
arr[] = {4,1,2,3}
smallest element is 1 and smallest neighbour of 1 is 2
So after operation 1
arr[] = {4,2,3}
sum = 2
after second operation,
arr[] = {4,3}
sum = 2 + 3
after third operation
arr[] = {4}
sum = 2 + 3 + 4

How do I approach this problem in efficient manner? I am not able to understand the approach in editorial

Problem link

2

You could use an implicit treap to solve the problem in O(n \log n), although that’s probably overkill :stuck_out_tongue:

3

You can just use segment tree (or sets) to solve this question.

Keep 2 sets :

  1. Pair of (A[i], i) for all i to extract the position of the minimum element in each step.
  2. Indices 1…N

Now every time when you extract the minimum from the first set, delete that from the first set and on the second set, use lower_bound to find it’s current neighbors. After that, just delete the extracted position of the minimum element from the second set.

No need for a treap, or rather an implicit treap :stuck_out_tongue: