-
Notifications
You must be signed in to change notification settings - Fork 15
/
combination_lock2.py
33 lines (30 loc) · 1.11 KB
/
combination_lock2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Copyright (c) 2020 kamyu. All rights reserved.
#
# Google Kick Start 2020 Round G - Problem C. Combination Lock
# https://codingcompetitions.withgoogle.com/kickstart/round/00000000001a0069/0000000000414a24
#
# Time: O(WlogW)
# Space: O(1)
#
# this solution is optimized from combination_lock.py
#
def combination_lock():
W, N = map(int, raw_input().strip().split())
X = map(lambda x:int(x)-1, raw_input().strip().split())
X.sort()
result = float("inf")
prefix_j_add_1 = sum(X[i] for i in xrange(W))
prefix_m2 = sum(X[i] for i in xrange(((W-1)+1)//2))
prefix_m1_add_1 = sum(X[i] for i in xrange(((W-1)//2)+1))
prefix_i = 0
for i in xrange(len(X)):
result = min(result, (prefix_j_add_1-prefix_m2) - (prefix_m1_add_1-prefix_i))
ni, nj = i+1, (i+1)+(W-1)
m1, m2 = (ni+nj)//2, (ni+nj+1)//2
prefix_j_add_1 += X[nj-W]+N
prefix_m2 += X[(m2-1)-W]+N if m2-1 >= W else X[m2-1]
prefix_m1_add_1 += X[m1-W]+N if m1 >= W else X[m1]
prefix_i += X[ni-1]
return result
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, combination_lock())