2016-17 Woburn Challenge Finals Round - Senior Division

Problem 3: Privacy

It's almost time to head into battle, but Bo Vine's cow soldiers insist on taking a nice long drink of water first. All N (1 ≤ N ≤ 400) of his army's cows have lined up at a trough to drink water. However, the cows like their privacy when drinking, and the i-th cow insists that they must drink from a trough from which at most C_i (0 ≤ C_i < N) other cows are also drinking.

The cows refuse to budge until they get hydrated, so to help make that possible, Bo Vine is prepared to install at most K (0 ≤ K < N) dividers at various points along the trough, effectively dividing it into multiple troughs as far as the cows are concerned. For example, if he installs a single divider between cows i and i + 1, then cows 1..i will be considered to drink from one trough, while cows (i + 1)..N will be considered to drink from a different trough.

It may turn out that the cows' demands can't all be met even after the installation of K dividers. As such, Bo Vine may also need to "encourage" some of them to relax their requirements. Each cow is willing to increase their C value by 1 in exchange for 1 treat. Bo Vine may bribe any cow as many times as he'd like.

What's the minimum total number of treats which Bo Vine must give to the cows such that, once at most K dividers are installed, each cow will be willing to drink from its trough?

In test cases worth 4/17 of the points, N ≤ 50 and K ≤ 1.
In test cases worth another 8/17 of the points, N ≤ 50.

Input Format

The first line of input consists of two space-separated integers N and K.
N lines follow, the i-th of which consists of a single integer C_i (for i = 1..N).

Output Format

Output one line consisting of a single integer – the minimum total number of treats required such that the cows can all be satisfied after the installation of K dividers.

Sample Input

7 2
2 0 5 0 1 3 1

Sample Output

3

Sample Explanation

One optimal strategy is to give the second cow 2 treats to increase its C value from 0 to 2, and the fourth cow 1 treat to increase its C value from 0 to 1. Then, Bo Vine can install one divider between cows 3 and 4, and one more between cows 5 and 6, in order to yield the following valid set of troughs:

  [ 2 2 5 | 1 1 | 3 1 ]

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: May 07, 2017
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)