-
Notifications
You must be signed in to change notification settings - Fork 5
/
valet_parking_chapter_2-5.py
83 lines (75 loc) · 3 KB
/
valet_parking_chapter_2-5.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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
# Copyright (c) 2021 kamyu. All rights reserved.
#
# Facebook Hacker Cup 2021 Round 2 - Problem C. Valet Parking - Chapter 2
# https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-2/problems/C2
#
# Time: O(S * min(R, C) + (R * C + S) * logR)
# Space: O(R * C)
#
# Template:
# https://github.com/kamyu104/GoogleKickStart-2021/blob/main/Round%20F/festival.py
class BIT(object): # 0-indexed.
def __init__(self, n):
self.__bit = [0]*(n+1) # Extra one for dummy node.
def add(self, i, val):
i += 1 # Extra one for dummy node.
while i < len(self.__bit):
self.__bit[i] += val
i += (i & -i)
def query(self, i):
i += 1 # Extra one for dummy node.
ret = 0
while i > 0:
ret += self.__bit[i]
i -= (i & -i)
return ret
def kth_element(self, k):
floor_log2_n = (len(self.__bit)-1).bit_length()-1
pow_i = 2**floor_log2_n
total = pos = 0 # 1-indexed
for _ in reversed(xrange(floor_log2_n+1)): # O(logN)
if pos+pow_i < len(self.__bit) and total+self.__bit[pos+pow_i] < k: # find max pos s.t. total < k
total += self.__bit[pos+pow_i]
pos += pow_i
pow_i >>= 1
return (pos+1)-1 # 0-indexed, return min pos s.t. total >= k if pos exists else n
def update(R, K, r, bit, cnts, left, right, diff):
total = bit.query(R-1)
A = bit.kth_element(total-(R-K+1)+1)+1 if R-K+1 <= total else -1
B = bit.kth_element(K)+1 if K <= total else R+2
bit.add(r-1, diff)
total += diff
if r >= A:
new_A = bit.kth_element(total-(R-K+1)+1)+1 if R-K+1 <= total else -1
nl, nr = (max(left, A+1), min(right, new_A-1)) if diff == 1 else (max(left, new_A+1), min(right, A-1))
for i in xrange(nl, nr+1):
cnts[i-left] += diff
A = new_A
if r <= B:
new_B = bit.kth_element(K)+1 if K <= total else R+2
nl, nr = (max(left, new_B+1), min(right, B-1)) if diff == 1 else (max(left, B+1), min(right, new_B-1))
for i in xrange(nl, nr+1):
cnts[i-left] += diff
B = new_B
if not (r < A or r > B):
if left <= r <= right:
cnts[r-left] += diff
def valet_parking_chapter_2():
R, C, K, S = map(int, raw_input().strip().split())
G = [list(raw_input().strip()) for _ in xrange(R)]
bits = [BIT(R) for _ in xrange(C)]
left, right = max(K-(C-1), 0), min(K+(C-1), R+1)
cnts = [abs(i-K) for i in xrange(left, right+1)]
for j in xrange(C):
for i in xrange(R):
if G[i][j] == 'X':
update(R, K, i+1, bits[j], cnts, left, right, 1)
result = 0
for _ in xrange(S):
i, j = map(lambda x: int(x)-1, raw_input().strip().split())
G[i][j] = 'X' if G[i][j] == '.' else '.'
update(R, K, i+1, bits[j], cnts, left, right, 1 if G[i][j] == 'X' else -1)
result += min(cnts)
return result
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, valet_parking_chapter_2())