×

Need help with this hackerearth question

 0 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 asked 21 Sep '16, 21:54 893●2●11●34 accept rate: 10% You could use an implicit treap to solve the problem in $O(n \log n)$, although that's probably overkill :P (22 Sep '16, 05:59) nibnalin6★

 0 You can just use segment tree (or sets) to solve this question. Keep 2 sets : Pair of (A[i], i) for all i to extract the position of the minimum element in each step. 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 :P answered 22 Sep '16, 13:59 94●2 accept rate: 15%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×836
×393
×173
×47

question asked: 21 Sep '16, 21:54

question was seen: 807 times

last updated: 22 Sep '16, 13:59