-
Notifications
You must be signed in to change notification settings - Fork 7
/
double_or_noting2.py
66 lines (57 loc) · 2.14 KB
/
double_or_noting2.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
# Copyright (c) 2021 kamyu. All rights reserved.
#
# Google Code Jam 2021 Round 1C - Problem C. Double or NOTing
# https://codingcompetitions.withgoogle.com/codejam/round/00000000004362d7/00000000007c1139
#
# Time: O(|E| + K * |S|), K is the number of bit groups of S
# Space: O(|E| + |S|)
#
# from re import match
from collections import deque
def logical_flip(s, flag):
while s and s[0]^flag == 1:
s.popleft()
if not s:
s.append(0^(1^flag))
def compare(s, e, flag):
if len(s) > len(e):
return False
for i in xrange(len(s)):
if s[i]^flag != e[i]:
return False
return True
def init_flip_count(E):
s = list(E)+[0] # if s ends with '1', it requires one more "not" operation (flip), which could be easily counted by appending a '0'
suffix_flip_cnt = [0]*len(s)
for i in reversed(xrange(len(s)-1)):
suffix_flip_cnt[i] = suffix_flip_cnt[i+1] + int(s[i] != s[i+1])
return suffix_flip_cnt
def get_flip_count(suffix_flip_cnt, i):
return suffix_flip_cnt[i] if i < len(suffix_flip_cnt) else 0
def find_prefix_and_count(S, E, suffix_flip_cnt):
result = float("inf")
X = 0
while S[0] != 0^(X%2):
if compare(S, E, X%2) and X >= get_flip_count(suffix_flip_cnt, len(S)):
return X+(len(E)-len(S)), None
logical_flip(S, X%2)
X += 1
return result, X
def double_or_noting():
S, E = map(lambda x: deque(int(c) for c in list(x)), raw_input().strip().split())
suffix_flip_cnt = init_flip_count(E)
result, X = find_prefix_and_count(S, E, suffix_flip_cnt)
if result != float("inf"):
return result
if X >= get_flip_count(suffix_flip_cnt, 0):
return X+len(E)-int(E[0] == 0)
cnt = get_flip_count(suffix_flip_cnt, 1)
if cnt == 0:
# assert(match("^10*$", E))
return X+1+(len(E)-1) # S =X=> "0" =1=> "1" =(len(E)-1)=> "10*"
if cnt == 1:
# assert(match("^11+0*$", E))
return X+1+len(E)+1 # S =X=> "0" =1=> "1" =k=> "100+" =1=> "11+" =(len(E)-k)=> "11+0*", where 2 <= k <= len(E)
return "IMPOSSIBLE"
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, double_or_noting())