Here is a possible approach: Use a heap in which each element contains a range and the sum for that range. Initially the heap contains n ranges of size one, one per balloon, where the sum is the score for that one balloon. Then k times you extend the smallest range by one by adding the smaller of the 2 adjacent balloons and downheap. Then the range at the top of the heap is the kth smallest contiguous sum. This is O(k * log n). Since k can be n*(n+1)/2, in the worst case this is O(n^2 log n).
Don On Feb 21, 11:32 am, shady <sinv...@gmail.com> wrote: > Problem link <http://www.spoj.pl/ABACUS12/status/ABA12E/> -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
