Problem:
 Max Score: 350 Points   Problem Statement There are N buildings along the line. The i -th building from the left is colored in color i , and its height is currently a_i meters. Chokudai is a mayor of the city, and he loves colorful thigs. And now he wants to see at least K buildings from the left.  You can increase height of buildings, but it costs 1 yens to increase 1 meters. It means you cannot make building that height is not integer. You cannot decrease height of buildings. Calculate the minimum cost of satisfying Chokudai's objective. Note: "Building i can see from the left" means there are no j exists that (height of building j ) ≥ (height of building i ) and j < i .       Input Format   N  K  a_1  a_2  a_3 ... a_N       Output Format Print the minimum cost in one line. In the end put a line break.    Constraints   1 ≤ K ≤ N ≤ 15  1 ≤ a_i ≤ 10^9     Scoring Subtask 1 [ 120 points]   N = K  Subtask 2 [ 90 points]   N ≤ 5  a_i ≤ 7  Subtask 3 [ 140 points]   There are no additional constraints.        Sample Input 1  5 5
3949 3774 3598 3469 3424    Sample Output 1  1541 The optimal solution is (height of buildings from the left) = [3949, 3950, 3951, 3952, 3953] .      Sample Input 2  5 3
7 4 2 6 4    Sample Output 2  7 The optimal solution is (height of buildings from the left) = [7, 8, 2, 9, 4] .

Solution (Python):
import sys
input = sys.stdin.readline
from itertools import product
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))

    cur_max = A[0]
    count = 1
    for i in range(1,N):
        if cur_max < A[i]:
            cur_max = A[i]
            count += 1
    
    if count >= K:
        print(0)
        return
    answer = 10**11

    for bit in product([0,1],repeat=N):
        cur_max = A[0]
        count = 1
        cost = 0
        for i in range(1,N):
            if cur_max < A[i]:
                cur_max = A[i]
                count += 1
            else:
                if bit[i] == 1:
                    cost += cur_max+1-A[i]
                    cur_max += 1
                    count += 1

        if count >= K:
            answer = min(answer,cost)
    print(answer)


    return


if __name__ == '__main__':
    main()

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))

ans = 10**18

for i in range(2**N):
    count = 0
    maxh = 0
    money = 0
    for j in range(N):
        if i >> j & 1:
            count += 1
            if maxh < A[j]:
                maxh = A[j]
            else:
                money += maxh+1-A[j]
                maxh += 1
        else:
            maxh = max(maxh,A[j])
    if count >= K:
        ans = min(ans,money)

print(ans)

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))

ans = float('inf')
for b in range(1<<(N-1)):
    mxa = A[0]
    k = 1
    cost = 0
    for i,a in enumerate(A[1:]):
        if b&(1<<i):
            c = max(0, mxa+1 - a)
            cost += c
            mxa = max(a, mxa+1)
            k += 1
        else:
            if mxa < a:
                mxa = a
                k += 1
    if k >= K:
        ans = min(ans, cost)
print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 10000000000000
for i in range(2 ** n):
    res = 0
    cnt = 0
    m = 0
    for j in range(n):
        if (i >> j) & 1:
            cnt += 1
            res += max(m - a[j] + 1, 0)
            m = max(m + 1, a[j])
        else:
            m = max(m, a[j])
    if cnt == k:
        ans = min(ans, res)
print(ans)

Solution (Python):



def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = float('inf')

    
    
    if n == 1:
        print(0)
        exit()

    for bit in range(1 << (n - 1)):
        color_count = 1
        cost = 0
        height_min = a[0]

        for j in range(n - 1):
            if height_min < a[j + 1]:
                color_count += 1
                height_min = a[j + 1]
                continue

            if bit & (1 << j):
                cost += height_min - a[j + 1] + 1
                color_count += 1
                height_min += 1

        if color_count >= k:
            ans = min(ans, cost)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import product as p
n,k=map(int,input().split())
a=list(map(int,input().split()))
an=float("INF")
for i in p([0,1],repeat=n):
    s=0
    c=a[::]
    p=0
    q=0
    for j in range(n):
        if i[j]:
            if s<c[j]:
                p+=1
                s=c[j]
            else:
                q+=s+1-c[j]
                c[j]=s+1
                p+=1
                s+=1
        else:
            if s<c[j]:
                p+=1
                s=c[j]
    if p>=k:
        an=min(q,an)
print(an)

Solution (Python):
n, k = map(int, input().split())
A = list(map(int, input().split()))




from itertools import combinations

ptn = combinations(range(1, n), k - 1)

ans = 10 ** 19
for p in ptn:
  totalcost = 0
  repA = A[:]
  for itr, val in enumerate(p):
    cost = max(0, max(repA[:val]) + 1 - repA[val])
    repA[val] += cost
    totalcost += cost
  ans = min(ans, totalcost)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np



N,K = map(int,input().split())
A = [int(x) for x in input().split()]

L = 1<<N
right = np.zeros(L,dtype=np.int64)
total = np.zeros(L,dtype=np.int64)

for i,a in enumerate(A):
    bit = 1<<i
    right[bit:2*bit] = np.maximum(right[:bit]+1,a)
    np.maximum(right[:bit],a,out=right[:bit])
    total[bit:2*bit] = (right[bit:2*bit] - a) + total[:bit]

popcount = np.zeros(L,dtype=np.int32)
rng = np.arange(L)
for _ in range(15):
    popcount += rng&1
    rng >>= 1

answer = total[popcount >= K].min()
print(answer)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime,random
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
aa = inpl()
NotLooking = list(itertools.combinations(range(1,N),N-K))

ans = INF
for NL in NotLooking:
    h = aa[0]
    tmp = 0
    for i in range(1,N):
        if i in NL:
            h = max(h,aa[i])
            continue
        else:
            if h < aa[i]:
                h = aa[i]
            else:
                tmp += h+1 - aa[i]
                h = h+1
    ans = min(tmp,ans)

print(ans)

Solution (Python):


import sys
from itertools import combinations, accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
A=LIST()


acc=list(accumulate(A, max))

ans=INF
for comb in combinations(range(N), K):
    sm=0
    for i, n in enumerate(comb):
        if i==0:
            
            cost=max(acc[n]-A[n], 0)
            
            if n!=0 and acc[n-1]==acc[n]:
                cost+=1
        else:
            
            cost=max(max(prev, acc[n-1])-A[n]+1, 0)
        sm+=cost
        prev=A[n]+cost
    ans=min(ans, sm)
print(ans)

Solution (Python):


import sys
from itertools import combinations, accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
A=LIST()

acc=list(accumulate(A, max))

ans=INF
for comb in combinations(range(N), K):
    sm=0
    for i, n in enumerate(comb):
        if i==0:
            cost=max(acc[n]-A[n], 0)
            if n!=0 and acc[n-1]==acc[n]:
                cost+=1
        else:
            cost=max(prev-A[n]+1, acc[n-1]-A[n]+1, 0)
        sm+=cost
        prev=A[n]+cost
    ans=min(ans, sm)
print(ans)

Solution (Python):
from itertools import product
n,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
a2,ans = [0],float("inf")
for i in range(n): a2.append(max(a[i],a[-1]))
def g(q):
	c,f = 0,1
	if sum(q)<k-1: f = 0
	else:
		m = a[0]
		for i in range(n-1):
			if q[i]: m,c = max(a[i+1],m+1),c+max(m+1-a[i+1],0)
			elif m<a[i+1]:
				f = 0
				break
	if f: return c
	else: return float("inf")
for i in product((0,1),repeat=n-1): ans = min(ans,g(i))
print(ans)

Solution (Python):
def b_buildings_are_colorful(N, K, A):
    import itertools
    
    attention_building = itertools.combinations(range(1, N), K - 1)
    ans = float('inf')
    for comb in attention_building:
        raised_a = A[:]  
        max_height = A[0]  
        for k in range(1, N):
            if k in comb:
                
                
                if raised_a[k] <= max_height:
                    raised_a[k] = max_height + 1
            max_height = max(max_height, raised_a[k])

        cost = 0
        for k in range(N):
            cost += raised_a[k] - A[k]
        ans = min(ans, cost)
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(b_buildings_are_colorful(N, K, A))

Solution (Python):
def b_buildings_are_colorful(N, K, A):
    import itertools
    combination = itertools.combinations(range(1, N), K - 1)
    ans = float('inf')
    for comb in combination:
        tmp = A[:]
        max_height = A[0]
        for k in range(1, N):
            if k in comb:
                if tmp[k] <= max_height:
                    tmp[k] = max_height + 1
            max_height = max(max_height, tmp[k])

        delta = 0
        for k in range(N):
            delta += tmp[k] - A[k]
        ans = min(ans, delta)
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(b_buildings_are_colorful(N, K, A))

Solution (Python):
from itertools import product
N, K = map(int, input().split())
*A, = map(int, input().split())

ans = 10**18
for P in product(range(2), repeat=N-1):
    if sum(P) < K-1:
        continue
    res = 0
    base = A[0]
    for i in range(N-1):
        if P[i]:
            if A[i+1] <= base:
                res += (base+1 - A[i+1])
                base += 1
            else:
                base = A[i+1]
        else:
            if base < A[i+1]:
                res += (A[i+1] - base)
                base = A[i+1]
    ans = min(ans, res)
print(ans)

Solution (Python):
N,K = map(int,input().split())
src = list(map(int,input().split()))

if N == 1:
    print(0)
    exit()

ans = float('inf')
for bs in range(1<<(N-1)):
    colors = 1
    cost = 0
    tmp = src[0]
    for k in range(N-1):
        if tmp < src[k+1]:
            colors += 1
            tmp = src[k+1]
            continue
        if bs&(1<<k):
            cost += tmp - src[k+1] + 1
            colors += 1
            tmp += 1
    if colors >= K:
        ans = min(ans, cost)

print(ans)

Solution (Python):
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
ans=float("inf")
for i in xrange(1<<n):
    cnt=0
    li=[]
    for j in xrange(1,n):
        if i>>j&1:
            cnt+=1
            li.append(j)
    if cnt<k-1:continue
    tmp=0
    h=a[0]
    for j in li:
        for l in xrange(j):
            h=max(h,a[l])
        tmp+=max(h+1-a[j],0)
        h=max(h+1,a[j])
    ans=min(ans,tmp)
print ans

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))

ans = 10**12
for b in range(1<<n):
    c = 0
    for i in range(n):
        if ((b>>i)&1) == 1:
            c += 1
    if c != k: continue
    t = 0
    h = 0
    for i in range(n):
        if ((b>>i)&1) == 0:
            h = max(h, a[i])
            continue
        if h < a[i]:
            h = a[i]
            continue
        if h >= a[i]:
            t += h - a[i] + 1
            h += 1
            continue
    ans = min(ans, t)
print(ans)

Solution (Python):
N,K = map(int,input().split())
bills = list(map(int,input().split()))
ans = 0
k = 0
while k < K:
	k = 0
	cost =[]
	cosd = {}
	tatekae = {}
	maxh = 0
	for bi,b in enumerate(bills):
		if b > maxh:
			cost.append(0)
			maxh = b
			k = k + 1
		else:
			c = maxh - b + 1
			cost.append(c)
			maxh2 = maxh + 1
			tatekae[bi] = []
			for b2i,b2 in enumerate(bills[bi:]):
				if maxh2 < b2:
					break
				elif maxh2 == b2:
					c = c + 1
					maxh2 = maxh2 + 1
					tatekae[bi].append(b2i + bi)
			cosd[bi] = c
	if k >= K:
		break
	a = min(cosd.items(),key =lambda x: x[1])[0]
	ans = ans + cosd[a]
	bills[a] = bills[a] + cost[a]
	for t in tatekae[a]:
		bills[t] = bills[t] + 1
	k = k + 1
print(ans)

Solution (Python):
from sys import stdin
n,k = map(int,stdin.readline().split())
a = map(int,stdin.readline().split())
def solve(b):
    req = 0
    ans = 0
    pr = b[0]-1
    for ii in b:
        i = ii
        if i <= pr:
            ans += pr+1-i
            i = pr+1
        pr = i
    return ans


ma = 1<<n
res = 10**38
for mask in xrange(ma):
    b = [a[0]]
    ma = a[0]
    pr = a[0]
    for i in xrange(1,n):
        if mask & (1<<i):
            b.append(a[i])
        elif a[i] > pr:
            b.append(a[i])
            
        pr = max(pr,a[i])
    if len(b)>=k:
        res = min(res, solve(b[:k]))
print res

Solution (Python):
from itertools import combinations
n, k = map(int, raw_input().split())
a = map(int, raw_input().split())
ans = 10 ** 12
for p in combinations(range(n), k):
    p = list(p)[::-1]
    ma = 0
    res = 0
    for j in xrange(n):
        if p and j == p[-1]:
            if ma < a[j]:
                ma = a[j]
            else:
                res += ma + 1 - a[j]
                ma += 1
            p.pop()
        else:
            if ma < a[j]:
                ma = a[j]
    if ans > res:
        ans = res
print ans