You are not logged in. Please login at www.codechef.com to post your questions!

×

Need help with this hackerearth question

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

dragonemperor's gravatar image

3★dragonemperor
89321134
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★

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 :P

link

answered 22 Sep '16, 13:59

additya1998's gravatar image

3★additya1998
942
accept rate: 15%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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