Problem:


Score : 700 points

Problem Statement

Given is a sequence of N digits a_1a_2\ldots a_N, where each element is 1, 2, or 3.
Let x_{i,j} defined as follows:

x_{1,j} := a_j \quad (1 \leq j \leq N)

x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} | \quad (2 \leq i \leq N and 1 \leq j \leq N+1-i)

Find x_{N,1}.

Constraints

2 \leq N \leq 10^6

a_i = 1,2,3 (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N
a_1a_2\ldotsa_N

Output

Print x_{N,1}.

Sample Input 1

4
1231

Sample Output 1

1

x_{1,1},x_{1,2},x_{1,3},x_{1,4} are respectively 1,2,3,1.

x_{2,1},x_{2,2},x_{2,3} are respectively |1-2| = 1,|2-3| = 1,|3-1| = 2.

x_{3,1},x_{3,2} are respectively |1-1| = 0,|1-2| = 1.

Finally, x_{4,1} = |0-1| = 1, so the answer is 1.

Sample Input 2

10
2311312312

Sample Output 2

0



Sample input:
4
1231


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = input()
while len(a)!=1:
    k = a
    a = ""
    left = 0
    right = len(k)-1
    leftlist = rightlist = ""
    while right - left != 1 and right!=left:
        leftlist = leftlist + str(abs(int(k[left])-int(k[left+1])))
        left+=1
        rightlist = str(abs(int(k[right])-int(k[right-1]))) + rightlist
        right-=1
    if right == left:
        a = leftlist + rightlist
    if right-left == 1:
        a = leftlist + str(abs(int(k[right])-int(k[left]))) +rightlist
print(a)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = input()
l = []
k = []
for i in range(N):
    l.append(a[i])

for j in range(1,N):
    for i in range(N-j):
        min = abs(int(l[i]) - int(l[i+1]))
        k.append(min)
    l = k
    k = []
    
ans = l[0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())

L = [int(s) for s in input()]

a = np.array(L)
for i in range(N-1):
  a = np.abs(a[1:]-a[:-1])
print(a[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input()))
import copy
for _ in range(n-1):
  b=[0]*(len(a)-1)
  for i in range(len(a)-1):
    b[i]=abs(a[i]-a[i+1])
    #print(b)
  a = copy.deepcopy(b)
  #print(a)

print(b[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = [int(i) for i in input()]
for i in range(1, n):
    y = []
    for j in range(len(x) - 1):
        y.append(abs(x[j] - x[j + 1]))
    x = y
print(x[0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

x = str(input())
kari_x = ""
p = 0
while len(x) > 2:
    for i in range(len(x)-2):
        if int(x[i+1]) >= int(x[i]) and int(x[i+1]) >= int(x[i+2]):
            kari_x += str(abs(int(x[i])-int(x[i+2])))
        elif int(x[i+1]) != 0:
            kari_x += str(abs(int(x[i+1])*2 - int(x[i]) -int(x[i+2])))
        else:
            kari_x += str(abs(int(x[i]) -int(x[i+2])))
    x = kari_x
    kari_x = ""

if len(x) == 2:
    print(abs(int(x[0])-int(x[1])))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,list(input())))
l1=A.copy()

for i in range(2,n+1):
    l2 = [0]*n
    for j in range(n+1-i):
        l2[j] = abs(l1[j] - l1[j+1])
    l1 = l2.copy()

print(l1[0])