Блог пользователя kstheking

Автор kstheking, история, 6 лет назад, По-английски

Problem: Given N elements, in one operation you can merge adjacent elements (i.e. sum them up into one element), you have to do exactly K operations, what is the minimum possible obtainable value of the maximum of the resultant array.

Example
Elements: 1 2 3
K : 1
Output: 3 (by merging 1 and 2 we get 3, if we merged 2 and 3 we would get 5 which is > 3)

I can do this problem in O(N^2) complexity by Dynamic Programming, but can better time complexity be achieved?

  • Проголосовать: нравится
  • -13
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Problem Source? constraints?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

How are you solving in N^2?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Create a min heap of all the elements in an array. Remove the top 2 elements, add them and insert in the heap. Do this k times.

Time Complexity: O(klogn)

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

I think you can solve this problem using binary search . Let's fix $$$mx$$$ , means the max element after performing $$$k$$$ operations would not be greater than $$$mx$$$ .
Now create a stack and start pushing elements in the stack . Now if the stack has at least 2 elements then take top 2 elements from the stack and check if there sum is less or equal to $$$mx$$$ . Now if the sum is less or equal to $$$mx$$$ , it means you can perform an operation here otherwise you can't .
Now in the end if you were able to perform $$$k$$$ operations then return $$$true$$$ otherwise return $$$false$$$ and set $$$low$$$ and $$$high$$$ of binary search accordingly .