I have $N$ numbers $a_i$. I want to find the smallest sum of EXACTLY $K$ non-consecutive elements. I know how to solve this in $O(N*K)$ (straightforward dynamic programing) but it is too slow. Anyone knows how to do this faster? This task was taken from an old programming contest.
Constraints:
$1 \le N \le 10^6$
$1 \le K \le N/2$
$0 \le a_i \le 10^6$
I think this is a correct algorithm. You sort the numbers, you start from the smallest and iterate toward the largest. Let's call a sequence of neighboring numbers a cluster. For every cluster you encounter you select the first one, and every other number. Keep going until you have collected K numbers. That should run in $O(n\log{n})$ time
The key property is that if you encounter a cluster of c neighboring numbers, if you select any other way, you cannot select more numbers, and for every number you select, there is a corresponding number that is no bigger in the optimal scheme.
For example, suppose you see the sequence 4 5 6 7 8 9, you should choose 4 6 8, if you choose any other way, for example, 4 7 9, then there is a correspondence between this choice and the optimal choice, where each individual number is not better than the optimal choice. For example, 4-4, 6-7, 8-9. Alternatively, if you select 4 8, then this is even worse, because the missing number will have to come later.
