How to solve HHMGN of Loc june 2017? I am unable to find its Editorial.
The solution is simple. First sort all the numbers and then calculate the prefix sum array for this sorted array. Next for each value (lets call is N) check whether sum of all values less than N + sum of all values greater than N converted to N is equal to S and the first value with which the sum equals to S is the answer.
Why does this solution give the correct answer?
That’s because we are basically trying each and every number (lets call it M) and checking whether the sum of all the numbers greater than M converted to M + sum of all numbers less than M equals S.
[1]
[1]: https://www.codechef.com/viewsolution/14375184I also do this question as you said but got only 30 points.
Here is my solution.
https://www.codechef.com/viewsolution/14375033