Problem:


Score : 700 points

Problem Statement

For strings s and t, we will say that s and t are prefix-free when neither is a prefix of the other.

Let L be a positive integer. A set of strings S is a good string set when the following conditions hold true:

Each string in S has a length between 1 and L (inclusive) and consists of the characters 0 and 1.

Any two distinct strings in S are prefix-free.

We have a good string set S = \{ s_1, s_2, ..., s_N \}. Alice and Bob will play a game against each other. They will alternately perform the following operation, starting from Alice:

Add a new string to S. After addition, S must still be a good string set.

The first player who becomes unable to perform the operation loses the game. Determine the winner of the game when both players play optimally.

Constraints

1 \leq N \leq 10^5

1 \leq L \leq 10^{18}

s_1, s_2, ..., s_N are all distinct.

{ s_1, s_2, ..., s_N } is a good string set.

|s_1| + |s_2| + ... + |s_N| \leq 10^5

Input

Input is given from Standard Input in the following format:

N L
s_1
s_2
:
s_N

Output

If Alice will win, print Alice; if Bob will win, print Bob.

Sample Input 1

2 2
00
01

Sample Output 1

Alice

If Alice adds 1, Bob will be unable to add a new string.

Sample Input 2

2 2
00
11

Sample Output 2

Bob

There are two strings that Alice can add on the first turn: 01 and 10.
In case she adds 01, if Bob add 10, she will be unable to add a new string.
Also, in case she adds 10, if Bob add 01, she will be unable to add a new string.

Sample Input 3

3 3
0
10
110

Sample Output 3

Alice

If Alice adds 111, Bob will be unable to add a new string.

Sample Input 4

2 1
0
1

Sample Output 4

Bob

Alice is unable to add a new string on the first turn.

Sample Input 5

1 2
11

Sample Output 5

Alice

Sample Input 6

2 3
101
11

Sample Output 6

Bob



Sample input:
2 2
00
01


Sample output:
Alice

Submission status: Wrong Answer

Solution code:
class Node():
    def __init__(self):
        self.lt = None
        self.rt = None
        self.dep = None

class Trie():
    def __init__(self):
        self.root = Node()
        self.root.dep = 0

    def add(self, string):
        node = self.root
        for s in string:
            if s == '0':
                if node.lt is None:
                    node.lt = Node()
                    node.lt.dep = node.dep + 1
                node = node.lt
            else:
                if node.rt is None:
                    node.rt = Node()
                    node.rt.dep = node.dep + 1
                node = node.rt

N, L = map(int, input().split())

trie = Trie()

for _ in range(N):
    s = input()
    trie.add(s)

subgame = []
stack = [trie.root]

while stack:
    node = stack.pop()
    if node.lt is None and node.rt is None:
        continue
    elif node.rt is None:
        stack.append(node.lt)
        subgame.append(L - node.dep)
    elif node.lt is None:
        stack.append(node.rt)
        subgame.append(L - node.dep)
    else:
        stack.append(node.lt)
        stack.append(node.rt)

def grundy(n):
    if n == 0: return 0
    if n % 2 == 1: return 1
    if n == 2**(n.bit_length() - 1):
        return n
    return grundy(n - 2**(n.bit_length() - 2))

res = 0

for l in subgame:
    res ^= grundy(l)

print('Alice' if res != 0 else 'Bob')

Submission status: Wrong Answer

Solution code:
n,l = map(int,input().split())
s = [input() for _ in range(n)]
s2 = [(len(si),si) for si in s]
s2.sort()

max_d = s2[-1][0]
cnt = [0] * (max_d+1)
stack = set()
down = 0
for i in range(max_d,-1,-1):
    now = 0
    next = set()
    while(stack):
        sj = stack.pop()
        next.add(sj//2)
        now += 1

    cnt[max_d-i] = now*2 - down

    if(s2):
        while(s2[-1][0] == i):
            _,sj = s2.pop()
            if(len(sj)>0):
                next.add(int(sj,2)//2)
                now += 1
            if(len(s2)==0):
                break
    down = now
    stack = stack.union(next)

num = 0
for i,ci in enumerate(cnt[1:]):
    num += 2**i * (ci%2)

def calc(x):
    if(x==0):
        return 0
    elif(x==1):
        return 1
    y = x.bit_length()//2
    block = 4**y //2
    if( x//block in [1,3]):
        return 1
    else:
        return 1-calc(x - block*2)

if(calc(num)==0):
    print('Bob')
else:
    print('Alice')

Submission status: Wrong Answer

Solution code:
n,l = map(int,input().split())
s = [input() for _ in range(n)]
s2 = [(len(si),si) for si in s]
s2.sort()

max_d = s2[-1][0]
cnt = [0] * (max_d+1)
done = set()
stack = []
for i in range(max_d,-1,-1):
    next = set()
    while(stack):
        sj = stack.pop()
        if(not (sj + '0') in done):
            cnt[max_d-len(sj)] += 1
        if(not (sj + '1') in done):
            cnt[max_d-len(sj)] += 1
        if(len(sj)>0):
            next.add(sj[:-1])
            done.add(sj)

    if(s2):
        while(s2[-1][0] == i):
            _,sj = s2.pop()
            if(len(sj)>0):
                next.add(sj[:-1])
                done.add(sj)
            if(len(s2)==0):
                break

    stack = list(next)

cnt_odd = 0
bef = cnt[0]
for ci in cnt[1:]:
    ci %= 2
    if(bef==0)&(ci==1):
        cnt_odd += 1
    bef = ci

if(cnt_odd%2==0):
    print('Bob')
else:
    print('Alice')

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key


def f(s, t):
    m = min(len(s), len(t))
    if s[:m] > t[:m]:
        return 1
    elif s[:m] < t[:m]:
        return -1
    else:
        if len(s) > len(t):
            return -1
        else:
            return 1


def ms(s, t):
    i = 0
    for c1, c2 in zip(s, t):
        if c1 != c2:
            return i
        i += 1
    return i


def xxor(x):
    if x & 3 == 0:
        return x
    if x & 3 == 1:
        return 1
    if x & 3 == 2:
        return x + 1
    if x & 3 == 3:
        return 0


def gray(x):
    return x ^ (x // 2)


n, l = map(int, input().split())
s = [input() for _ in range(n)]
s.sort(key=cmp_to_key(f))
g = gray(l) ^ gray(l - len(s[0]))
for i in range(n - 1):
    b = ms(s[i], s[i + 1]) + 1
    g ^= l - b + 1
    t = len(s[i + 1]) - b
    g ^= gray(l - b) ^ gray(l - b - t)
if g == 0:
    print('Bob')
else:
    print('Alice')

Submission status: Wrong Answer

Solution code:
n,l = map(int,input().split())
ls = [input() for i in range(n)]
sm = sum([len(s) for s in ls])
ls.sort()
num = [0]*(sm+1)
for i in range(n):
  if i == 0:
    for j in range(len(ls[i])):
      num[j+1] = 1
  else:
    x = ls[i]
    p = ls[i-1]
    cnt = 0
    while cnt < min(len(x),len(p)):
      if x[cnt] == p[cnt]:
        cnt += 1
      else:
        break
    num[cnt+1] -= 1
    for j in range(cnt+2,len(x)+1):
      num[j] += 1
ans = 0
def d2(x):
  if x == 0:
    return 0
  cnt = 0
  while x%2 == 0:
    cnt += 1
    x //= 2
  return cnt
for i in range(sm+1):
  ans ^= d2(l+1-i)*(num[i]%2)
if ans:
  print("Alice")
else:
  print("Bob")

Submission status: Wrong Answer

Solution code:

N,L = map(int,input().split())

dic = {}

for loop in range(N):

    s = input()

    for i in range(len(s) + 1):

        if s[:i] not in dic:
            dic[s[:i]] = [1,1]

    for i in range(len(s)):
        if s[i] == "0":
            dic[s[:i]][0] = 0
        elif s[i] == "1":
            dic[s[:i]][1] = 0

rev = 0
#print (dic)

for i in dic:

    l,r = dic[i]

    rev += l * max(0 , L - len(i) - 1 ) % 2
    rev += r * max(0 , L - len(i) - 1 ) % 2

    #print ("ilr",i,l,r)
    #print ("revlr",l * max(0 , L - len(i) - 1 ) % 2 , r * max(0 , L - len(i) - 1 ) % 2)

#print (rev)

if rev == 0:
    print ("Bob")
else:
    print ("Alice")

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = 10**10+7
    mod2 = 10**10+9
    mod3 = 998244353
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    dic3 = defaultdict(int)
    h_list = []
    h2_list = []
    h3_list = []
    pair = {}
    pair2 = {}
    pair3 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        h3 = 0
        for i in range(len(s)):
            M += 1
            h = (h*1007 + int(s[i]) + 1) % mod
            pair[h] = (h + 1)%mod if s[i] == '0' else (h-1)%mod
            h2 = (h2 * 2009 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 + 1)%mod2 if s[i] == '0' else (h2-1)%mod2
            h3 = (h3 * 3001 + int(s[i]) + 1) % mod3
            pair3[h3] = (h3 + 1) % mod3 if s[i] == '0' else (h3 - 1) % mod3
            dic[h] = i+1
            dic2[h2] = i+1
            dic[h3] = i+1
            h_list.append(h)
            h2_list.append(h2)
            h3_list.append(h3)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    seen3 = defaultdict(int)
    for i in range(M):
        s, s2, s3 = h_list[i], h2_list[i], h3_list[i]
        if seen[s]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        t3 = pair3[s3]
        if dic[t] == 0:
            p = [dic[s]]
            p.sort()
            tmp = L - p[0] + 1
            '''
            if not seen[s]:
                tmp = L - dic[s] + 1
            elif not seen[s2]:
                tmp = L - dic2[s2] + 1
            else:
                tmp = L - dic3[s3] + 1
            '''
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1
        seen3[s3] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = 10**9+7
    mod2 = 10**9+9
    mod3 = 998244353
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    dic3 = defaultdict(int)
    h_list = []
    h2_list = []
    h3_list = []
    pair = {}
    pair2 = {}
    pair3 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        h3 = 0
        for i in range(len(s)):
            M += 1
            h = (h*1007 + int(s[i]) + 1) % mod
            pair[h] = (h + 1)%mod if s[i] == '0' else (h-1)%mod
            h2 = (h2 * 2009 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 + 1)%mod2 if s[i] == '0' else (h2-1)%mod2
            h3 = (h3 * 3001 + int(s[i]) + 1) % mod3
            pair3[h3] = (h3 + 1) % mod3 if s[i] == '0' else (h3 - 1) % mod3
            dic[h] = i+1
            dic2[h2] = i+1
            dic[h3] = i+1
            h_list.append(h)
            h2_list.append(h2)
            h3_list.append(h3)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    seen3 = defaultdict(int)
    for i in range(M):
        s, s2, s3 = h_list[i], h2_list[i], h3_list[i]
        if seen[s] and seen2[s2] and seen3[s3]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        t3 = pair3[s3]
        if dic[t] == 0 or dic2[t2] == 0 or dic3[t3] == 0:
            p = [dic[s], dic2[s2], dic3[s3]]
            p.sort()
            tmp = L - p[1] + 1
            '''
            if not seen[s]:
                tmp = L - dic[s] + 1
            elif not seen[s2]:
                tmp = L - dic2[s2] + 1
            else:
                tmp = L - dic3[s3] + 1
            '''
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1
        seen3[s3] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = 10**9+7
    mod2 = 10**9+9
    mod3 = 998244353
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    dic3 = defaultdict(int)
    h_list = []
    h2_list = []
    h3_list = []
    pair = {}
    pair2 = {}
    pair3 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        h3 = 0
        for i in range(len(s)):
            M += 1
            h = (h*1007 + int(s[i]) + 1) % mod
            pair[h] = (h + 1)%mod if s[i] == '0' else (h-1)%mod
            h2 = (h2 * 2009 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 + 1)%mod2 if s[i] == '0' else (h2-1)%mod2
            h3 = (h3 * 3001 + int(s[i]) + 1) % mod3
            pair3[h3] = (h3 + 1) % mod3 if s[i] == '0' else (h3 - 1) % mod3
            dic[h] = i+1
            dic2[h2] = i+1
            dic[h3] = i+1
            h_list.append(h)
            h2_list.append(h2)
            h3_list.append(h3)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    seen3 = defaultdict(int)
    for i in range(M):
        s, s2, s3 = h_list[i], h2_list[i], h3_list[i]
        if seen[s] and seen2[s2] and seen3[s3]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        t3 = pair3[s3]
        if dic[t] == 0 or dic2[t2] == 0 or dic3[t3] == 0:
            if not seen[s]:
                tmp = L - dic[s] + 1
            elif not seen[s2]:
                tmp = L - dic2[s2] + 1
            else:
                assert False
                tmp = L - dic3[s3] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1
        seen3[s3] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = 10**9+7
    mod2 = 10**9+9
    mod3 = 998244353
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    dic3 = defaultdict(int)
    h_list = []
    h2_list = []
    h3_list = []
    pair = {}
    pair2 = {}
    pair3 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        h3 = 0
        for i in range(len(s)):
            M += 1
            h = (h*1007 + int(s[i]) + 1) % mod
            pair[h] = (h + 1)%mod if s[i] == '0' else (h-1)%mod
            h2 = (h2 * 2009 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 + 1)%mod2 if s[i] == '0' else (h2-1)%mod2
            h3 = (h3 * 3001 + int(s[i]) + 1) % mod3
            pair3[h3] = (h3 + 1) % mod3 if s[i] == '0' else (h3 - 1) % mod3
            dic[h] = i+1
            dic2[h2] = i+1
            dic[h3] = i+1
            h_list.append(h)
            h2_list.append(h2)
            h3_list.append(h3)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    seen3 = defaultdict(int)
    for i in range(M):
        s, s2, s3 = h_list[i], h2_list[i], h3_list[i]
        if seen[s] and seen2[s2] and seen3[s3]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        t3 = pair3[s3]
        if dic[t] == 0 or dic2[t2] == 0 or dic3[t3] == 0:
            if not seen[s]:
                tmp = L - dic[s] + 1
            elif not seen[s2]:
                tmp = L - dic2[s2] + 1
            else:
                tmp = L - dic3[s3] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1
        seen3[s3] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = 10**9+7
    mod2 = 10**9+9
    mod3 = 998244353
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    dic3 = defaultdict(int)
    h_list = []
    h2_list = []
    h3_list = []
    pair = {}
    pair2 = {}
    pair3 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        h3 = 0
        for i in range(len(s)):
            M += 1
            h = (h*1007 + int(s[i]) + 1) % mod
            pair[h] = (h + 1)%mod if s[i] == '0' else (h-1)%mod
            h2 = (h2 * 2009 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 + 1)%mod2 if s[i] == '0' else (h2-1)%mod2
            h3 = (h3 * 3001 + int(s[i]) + 1) % mod3
            pair3[h3] = (h3 + 1) % mod3 if s[i] == '0' else (h3 - 1) % mod3
            dic[h] = i+1
            dic2[h2] = i+1
            dic[h3] = i+1
            h_list.append(h)
            h2_list.append(h2)
            h3_list.append(h3)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    seen3 = defaultdict(int)
    for i in range(M):
        s, s2, s3 = h_list[i], h2_list[i], h3_list[i]
        if seen[s] and seen2[s2] and seen3[s3]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        t3 = pair3[s3]
        if not (dic[t] and dic2[t2] and dic3[t3]):
            if not seen[s]:
                tmp = L - dic[s] + 1
            elif not seen[s2]:
                tmp = L - dic2[s2] + 1
            else:
                tmp = L - dic3[s3] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1
        seen3[s3] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = 10**9+7
    mod2 = 10**9+9
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    h_list = []
    h2_list = []
    pair = {}
    pair2 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        for i in range(len(s)):
            M += 1
            h = (h*1007 + int(s[i]) + 1) % mod
            pair[h] = (h + 1)%mod if s[i] == '0' else (h-1)%mod
            h2 = (h2 * 2009 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 + 1)%mod2 if s[i] == '0' else (h2-1)%mod2
            dic[h] = i+1
            dic2[h2] = i+1
            h_list.append(h)
            h2_list.append(h2)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    for i in range(M):
        s, s2 = h_list[i], h2_list[i]
        if seen[s] and seen2[s2]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        if not (dic[t] and dic2[t2]):
            tmp = L - dic[s] + 1 if not seen[s] else L - dic2[s2] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = 10**9+7
    mod2 = 10**9+9
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    h_list = []
    h2_list = []
    pair = {}
    pair2 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        for i in range(len(s)):
            M += 1
            h = (h*3 + int(s[i]) + 1) % mod
            pair[h] = (h + 1)%mod if s[i] == '0' else (h-1)%mod
            h2 = (h2 * 5 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 + 1)%mod2 if s[i] == '0' else (h2-1)%mod2
            dic[h] = i+1
            dic2[h2] = i+1
            h_list.append(h)
            h2_list.append(h2)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    for i in range(M):
        s, s2 = h_list[i], h2_list[i]
        if seen[s] and seen2[s2]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        if not (dic[t] and dic2[t2]):
            tmp = L - dic[s] + 1 if not seen[s] else L - dic2[s2] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = 10**9+7
    mod2 = 10**9+9
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    h_list = []
    h2_list = []
    pair = {}
    pair2 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        for i in range(len(s)):
            M += 1
            h = (h*3 + int(s[i]) + 1) % mod
            pair[h] = (h*3 + abs(int(s[i]) - 1) + 1) % mod
            h2 = (h2 * 5 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 * 5 + abs(int(s[i]) - 1) + 1) % mod2
            dic[h] = i+1
            dic2[h2] = i+1
            h_list.append(h)
            h2_list.append(h2)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    for i in range(M):
        s, s2 = h_list[i], h2_list[i]
        if seen[s] and seen2[s2]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        if not (dic[t] and dic2[t2]):
            tmp = L - dic[s] + 1 if not seen[s] else L - dic2[s2] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = (10**9+7) * 3
    mod2 = (10**9+9) * 5
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    h_list = []
    h2_list = []
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        for i in range(len(s)):
            M += 1
            h = (h*3 + int(s[i]) + 1) % mod
            h2 = (h2 * 5 + int(s[i]) + 1) % mod2
            dic[h] = i+1
            dic2[h2] = i+1
            h_list.append(h)
            h2_list.append(h2)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    for i in range(M):
        s, s2 = h_list[i], h2_list[i]
        if seen[s] and seen2[s2]:
            continue
        if s%3 == 1:
            t = (s + 1)%mod
        else:
            t = (s - 1)%mod
        if s2%5 == 1:
            t2 = (s2 + 1)%mod2
        else:
            assert s2 % 5 == 2
            t2 = (s2 - 1)%mod2
        if not (dic[t] and dic2[t2]):
            tmp = L - dic[s] + 1 if not seen[s] else L - dic2[s2] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = (10**9+7) * 3
    mod2 = (10**9+9) * 5
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    h_list = []
    h2_list = []
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        for i in range(len(s)):
            M += 1
            h = (h*3 + int(s[i]) + 1) % mod
            h2 = (h2 * 5 + int(s[i]) + 1) % mod2
            dic[h] = i+1
            dic2[h2] = i+1
            h_list.append(h)
            h2_list.append(h2)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    for i in range(M):
        s, s2 = h_list[i], h2_list[i]
        if seen[s] and seen2[s2]:
            continue
        if s%3 == 1:
            t = (s + 1)%mod
        else:
            t = (s - 1)%mod
        if s2%5 == 1:
            t2 = (s2 + 1)%mod2
        else:
            t2 = (s2 - 1)%mod2
        if not (dic[t] and dic2[t2]):
            tmp = L - dic[s] + 1 if not seen[s] else L - dic2[s2] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = (10**9+7) * 3
    mod2 = (10**9+9) * 5
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    h_list = []
    h2_list = []
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        for i in range(len(s)):
            M += 1
            h = (h*3 + int(s[i]) + 1) % mod
            h2 = (h2 * 5 + int(s[i]) + 1) % mod2
            dic[h] = i+1
            dic2[h2] = i+1
            h_list.append(h)
            h2_list.append(h2)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    for i in range(M):
        s, s2 = h_list[i], h2_list[i]
        if seen[s] or seen2[s2]:
            continue
        seen[s] = 1
        seen2[s2] = 1
        if s%3 == 1:
            t = (s + 1)%mod
        else:
            t = (s - 1)%mod
        if s2%5 == 1:
            t2 = (s2 + 1)%mod2
        else:
            t2 = (s2 - 1)%mod2
        if not (dic[t] and dic2[t2]):
            tmp = L - dic[s] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = (10**9+7) * 3
    mod2 = (10**9+9) * 3
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    h_list = []
    h2_list = []
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        for i in range(len(s)):
            M += 1
            h = (h*3 + int(s[i]) + 1) % mod
            h2 = (h2 * 3 + int(s[i]) + 1) % mod2
            dic[h] = i+1
            dic2[h2] = i+1
            h_list.append(h)
            h2_list.append(h2)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    for i in range(M):
        s, s2 = h_list[i], h2_list[i]
        if seen[s] or seen2[s2]:
            continue
        seen[s] = 1
        seen2[s2] = 1
        if s%3 == 1:
            t = (s + 1)%mod
            t2 = (s2 + 1)%mod2
        else:
            t = (s - 1)%mod
            t2 = (s2 - 1)%mod2
        if not (dic[t] and dic2[t2]):
            tmp = L - dic[s] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = (10**9+7) * 3
    mod2 = (10**9+9) * 3
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    h_list = []
    h2_list = []
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        for i in range(len(s)):
            M += 1
            h = (h*3 + int(s[i]) + 1) % mod
            h2 = (h2 * 3 + int(s[i]) + 1) % mod2
            dic[h] = i+1
            dic2[h2] = i+1
            h_list.append(h)
            h2_list.append(h2)

    g = 0
    for i in range(M):
        s, s2 = h_list[i], h2_list[i]
        if s%3 == 1:
            t = (s + 1)%mod
            t2 = (s2 + 1)%mod2
        else:
            t = (s - 1)%mod
            t2 = (s2 - 1)%mod2
        if not (dic[t] and dic2[t2]):
            tmp = L - dic[s] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = (10**9+7) * 3
    mod2 = (10**9+9) * 3
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    h_list = []
    h2_list = []
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        for i in range(len(s)):
            M += 1
            h = (h*3 + int(s[i]) + 1) % mod
            h2 = (h2 * 3 + int(s[i]) + 1) % mod2
            dic[h] = i+1
            dic2[h2] = i+1
            h_list.append(h)
            h2_list.append(h2)

    g = 0
    for i in range(M):
        s, s2 = h_list[i], h2_list[i]
        if s%3 == 1:
            t = (s + 1)%mod
            t2 = (s2 + 1)%mod2
        else:
            t = (s - 1)%mod
            t2 = (s2 + 1)%mod2
        if not (dic[t] and dic2[t2]):
            tmp = L - dic[s] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = (10**9+7) * 3
    mod2 = (10**9+9) * 3
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    h_list = []
    h2_list = []
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        for i in range(len(s)):
            M += 1
            h = (h*3 + int(s[i]) + 1) % mod
            h2 = (h2 * 3 + int(s[i]) + 1) % mod2
            dic[h] = i+1
            dic2[h2] = i+1
            h_list.append(h)
            h2_list.append(h2)

    g = 0
    for i in range(M):
        s, s2 = h_list[i], h2_list[i]
        if s%3 == 1:
            t = (s + 1)%mod
            t2 = (s2 + 1)%mod2
        else:
            t = (s - 1)%mod
            t2 = (s2 + 1)%mod2
        if not (dic[t] and dic[t2]):
            tmp = L - dic[s] + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)

    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()