-
Notifications
You must be signed in to change notification settings - Fork 5
/
string_concatenation.py
60 lines (55 loc) · 2 KB
/
string_concatenation.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
# Copyright (c) 2021 kamyu. All rights reserved.
#
# Facebook Hacker Cup 2021 Round 2 - Problem D. String Concatenation
# https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-2/problems/D
#
# Time: O(N + X*2^X*(N-X)/C) ~= O(1e8) on average, O(6e12) at worst, pass in PyPy2 but Python2
# Space: O(N)
#
def find_equal_sum_masks(L, idxs): # Time: O(X*2^X)
lookup = {}
for mask in xrange(1, 1<<len(idxs)):
total, bit = 0, 1
for i in idxs:
if mask&bit:
total += L[i]
bit <<= 1
if total in lookup:
return mask, lookup[total]
lookup[total] = mask
return None
def add_remains(N, K, L, A, B, R): # Time: O(X*2^X) * O((N-X)/C) = O(23*2^23 * (2e5-23)/6) ~= O(1e8) on average, O(6e12) at worst, C = 6 on average
curr = []
for i in xrange(len(R)):
curr.append(R[i])
if N-(len(A)+len(B)) <= K:
break
if len(curr) == X or i == len(R)-1:
pair_masks = find_equal_sum_masks(L, curr)
if not pair_masks:
return "Impossible"
mask_A, mask_B = pair_masks
nxt = []
bit = 1
for i in curr:
if (mask_A&bit) and not (mask_B&bit):
A.add(i)
elif (mask_B&bit) and not (mask_A&bit):
B.add(i)
else:
nxt.append(i)
bit <<= 1
curr = nxt
return "Possible\n%s\n%s" % (" ".join(map(lambda x: str(x+1), A)), " ".join(map(lambda x: str(x+1), B)))
def string_concatenation():
N, K = map(int, raw_input().strip().split())
L = map(int, raw_input().strip().split())
A, B, R = set(), set(), range(N)
return add_remains(N, K, L, A, B, R)
MAX_L = 200000
X = 1
while 2**X < X*MAX_L+1: # pigeonhole principle
X += 1
assert(X == 23) # we can always find equal sum subsets by 23 or more strings
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, string_concatenation())