Problem:
 Score : 500 points    Problem Statement We have a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i -th row from the top and the j -th column from the left.  The square (i, j) has two numbers A_{ij} and B_{ij} written on it.  First, for each square, Takahashi paints one of the written numbers red and the other blue.  Then, he travels from the square (1, 1) to the square (H, W) . In one move, he can move from a square (i, j) to the square (i+1, j) or the square (i, j+1) . He must not leave the grid.  Let the unbalancedness be the absolute difference of the sum of red numbers and the sum of blue numbers written on the squares along Takahashi's path, including the squares (1, 1) and (H, W) .  Takahashi wants to make the unbalancedness as small as possible by appropriately painting the grid and traveling on it.  Find the minimum unbalancedness possible.      Constraints  2 \leq H \leq 80  2 \leq W \leq 80  0 \leq A_{ij} \leq 80  0 \leq B_{ij} \leq 80  All values in input are integers.         Input Input is given from Standard Input in the following format:  H  W  A_{11}  A_{12}  \ldots  A_{1W}  :  A_{H1}  A_{H2}  \ldots  A_{HW}  B_{11}  B_{12}  \ldots  B_{1W}  :  B_{H1}  B_{H2}  \ldots  B_{HW}       Output Print the minimum unbalancedness possible.        Sample Input 1 2 2
1 2
3 4
3 4
2 1      Sample Output 1 0  By painting the grid and traveling on it as shown in the figure below, the sum of red numbers and the sum of blue numbers are 3+3+1=7 and 1+2+4=7 , respectively, for the unbalancedness of 0 .        Sample Input 2 2 3
1 10 80
80 10 1
1 2 3
4 5 6      Sample Output 2 2

Solution (Python):
H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in [0]*H]
B = [list(map(int,input().split())) for _ in [0]*H]


C = [[abs(b-a) for a,b in zip(a_row,b_row)] for a_row,b_row in zip(A,B)]

dm = [[0]*W for _ in [0]*H]
dm[-1][-1] = 80
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        c = C[i][j]
        if i-1>=0:
            dm[i-1][j] = max(dm[i-1][j],dm[i][j] + c)
        if j-1>=0:
            dm[i][j-1] = max(dm[i][j-1],dm[i][j] + c)

d = [[set() for _ in [0]*W] for _ in [0]*H]
d[0][0] = {C[0][0]}

for i in range(H):
    for j in range(W):
        for n in d[i][j]:
            if i+1<H:
                c = C[i+1][j]
                if n+c <= dm[i][j]:
                    d[i+1][j].add(n+c)
                if n-c <= dm[i][j]:
                    d[i+1][j].add(abs(n-c))
            if j+1<W:
                c = C[i][j+1]
                if n+c <= dm[i][j]:
                    d[i][j+1].add(n+c)
                if n-c <= dm[i][j]:
                    d[i][j+1].add(abs(n-c))
ans = min(abs(o) for o in d[-1][-1])
print(ans)

Solution (Python):
H, W = [int(x) for x in input().split()]

A = [[0]*W for i in range(H)]
for c in [1, -1]:
    for i in range(H):
        arr = [int(x) for x in input().split()]
        for j in range(W):
            A[i][j] += arr[j] * c

M = 160*80
dp = [[0]*W for i in range(H)]
dp[0][0] = 1 << M
for i in range(H):
    for j in range(W):
        if i > 0:
            dp[i][j] |= dp[i-1][j]
        if j > 0:
            dp[i][j] |= dp[i][j-1]
        a = abs(A[i][j])
        dp[i][j] = (dp[i][j] << a) | (dp[i][j] >> a)

ans = M
for i in range(2*M):
    if dp[H-1][W-1] & (1 << i) > 0:
        ans = min(ans, abs(M-i))
print(ans)

Solution (Python):
def ints():
  return list(map(int, input().split()))

H, W = ints()

A = [ints() for i in range(H)]
B = [ints() for i in range(H)]

C = 20000
dp = [[0 for j in range(W)] for i in range(H)]
dp[0][0] |= 1 << (C - A[0][0] + B[0][0]) 
dp[0][0] |= 1 << (C + A[0][0] - B[0][0])

for i in range(H):
  for j in range(W):
    if i + 1 < H:
      dp[i + 1][j] |= dp[i][j] << abs(A[i + 1][j] - B[i + 1][j])
      dp[i + 1][j] |= dp[i][j] >> abs(A[i + 1][j] - B[i + 1][j])
    if j + 1 < W:
      dp[i][j + 1] |= dp[i][j] << abs(A[i][j + 1] - B[i][j + 1])
      dp[i][j + 1] |= dp[i][j] >> abs(A[i][j + 1] - B[i][j + 1])

ans = 10**100
for k in range(2*C):
  if dp[H - 1][W - 1] >> k & 1:
    ans = min(ans, abs(k - C))
print(ans)

Solution (Python):
import numpy as np
 
h, w = list(map(int, input().split()))
 
aaa = [list(map(int, input().split())) for _ in range(h)]
bbb = [list(map(int, input().split())) for _ in range(h)]
aaa = np.array(aaa, dtype=np.int8)
bbb = np.array(bbb, dtype=np.int8)
diff = abs(aaa - bbb)
 
 
def merge_new_can(d, can, prev_can):
    if d == 0:
        can |= prev_can
    else:
        can[d:] |= prev_can[:-d]
        can[:-d] |= prev_can[d:]
 
 
prev_row = [None] * w
 
can = np.zeros(25601, dtype=np.int8)
can[diff[0][0] + 12800] = 1
prev_row[0] = can
 
for j in range(1, w):
    d = diff[0][j]
    can = np.zeros(25601, dtype=np.int8)
    prev_can = prev_row[j - 1]
    merge_new_can(d, can, prev_can)
    prev_row[j] = can
 
for i in range(1, h):
    curr_row = [None] * w
 
    d = diff[i][0]
    prev_can = prev_row[0]
    can = np.zeros(25601, dtype=np.int8)
    merge_new_can(d, can, prev_can)
    curr_row[0] = can
 
    for j in range(1, w):
        d = diff[i][j]
        can = np.zeros(25601, dtype=np.int8)
        prev_can1 = prev_row[j]
        prev_can2 = curr_row[j - 1]
        merge_new_can(d, can, prev_can1)
        merge_new_can(d, can, prev_can2)
        curr_row[j] = can
 
    prev_row = curr_row
 
goal = prev_row[-1]
goal[12801:] |= goal[:12800][::-1]
goal = goal[12800:]
print(np.argmax(goal))

Solution (Python):
import numpy as np

h, w = list(map(int, input().split()))

aaa = [list(map(int, input().split())) for _ in range(h)]
bbb = [list(map(int, input().split())) for _ in range(h)]
aaa = np.array(aaa, dtype=np.int8)
bbb = np.array(bbb, dtype=np.int8)
diff = abs(aaa - bbb)


def merge_new_can(d, can, prev_can):
    if d == 0:
        can |= prev_can
    else:
        can[d:] |= prev_can[:-d]
        can[:-d] |= prev_can[d:]


prev_row = [None] * w

can = np.zeros(25601, dtype=np.int8)
can[diff[0][0] + 12800] = 1
prev_row[0] = can

for j in range(1, w):
    d = diff[0][j]
    can = np.zeros(25601, dtype=np.int8)
    prev_can = prev_row[j - 1]
    merge_new_can(d, can, prev_can)
    prev_row[j] = can

for i in range(1, h):
    curr_row = [None] * w

    d = diff[i][0]
    prev_can = prev_row[0]
    can = np.zeros(25601, dtype=np.int8)
    merge_new_can(d, can, prev_can)
    curr_row[0] = can

    for j in range(1, w):
        d = diff[i][j]
        can = np.zeros(25601, dtype=np.int8)
        prev_can1 = prev_row[j]
        prev_can2 = curr_row[j - 1]
        merge_new_can(d, can, prev_can1)
        merge_new_can(d, can, prev_can2)
        curr_row[j] = can

    prev_row = curr_row

goal = prev_row[-1]
goal[12801:] |= goal[:12800][::-1]
goal = goal[12800:]
print(np.argmax(goal))

Solution (Python):
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

arr = [set() for _ in range(W)]
arr[0].add(0)
for y in range(H):
    nextarr = [set() for _ in range(W)]
    Ay = A[y]
    By = B[y]
    dh = H - y - 1
    for x in range(W):
        nextset = nextarr[x]
        d = Ay[x] - By[x]
        dw = W - x - 1
        lim = (dh + dw + 1) * 160
        if x >= 1:
            arr[x] |= nextarr[x-1]
        for n in arr[x]:
            if abs(n+d) <= lim:
                nextset.add(abs(n+d))
            if abs(n-d) <= lim:
                nextset.add(abs(n-d))
    arr = nextarr
print(min([abs(d) for d in arr[-1]]))

Solution (Python):
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



H, W = list(map(int, sys.stdin.buffer.readline().split()))
A = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(H)]
B = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(H)]

grid = [[0] * W for _ in range(H)]
for h, w in itertools.product(range(H), range(W)):
    grid[h][w] = A[h][w] - B[h][w]


dp = [[set() for _ in range(W)] for _ in range(H)]
dp[0][0] = {grid[0][0] % 800, -(grid[0][0]) % 800}
for h, w in itertools.product(range(H), range(W)):
    g = grid[h][w]
    s = dp[h][w]
    if h - 1 >= 0:
        for c in dp[h - 1][w]:
            s.add((c + g) % 800)
            s.add((c - g) % 800)
    if w - 1 >= 0:
        for c in dp[h][w - 1]:
            s.add((c + g) % 800)
            s.add((c - g) % 800)


ans = INF
for s in dp[-1][-1]:
    ans = min(ans, s)
    ans = min(ans, (-s) % 800)
print(ans)

Solution (Python):
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

arr = [set() for _ in range(W)]
arr[0].add(A[0][0] - B[0][0])
for x in range(1, W):
    s = arr[x]
    d = A[0][x] - B[0][x]
    for n in arr[x-1]:
        s.add(abs(n+d))
        s.add(abs(n-d))

for y in range(1, H):
    nextarr = [set() for _ in range(W)]
    Ay = A[y]
    By = B[y]
    dh = H - y - 1
    for x in range(W):
        nextset = nextarr[x]
        d = Ay[x] - By[x]
        dw = W - x - 1
        lim = (dh + dw + 1) * 160
        
        if x >= 1:
            arr[x] |= nextarr[x-1]
        for n in arr[x]:
            if abs(n+d) <= lim:
                nextset.add(abs(n+d))
            if abs(n-d) <= lim:
                nextset.add(abs(n-d))
    arr = nextarr
print(min([abs(d) for d in arr[-1]]))

Solution (Python):
from collections import deque
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
C = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        C[i][j] = abs(A[i][j]-B[i][j])
M = 80*(H+W)
dp = [[0 for i in range(W)] for j in range(H)]
c = C[0][0]
dp[0][0]+=(1<<(c+M))|(1<<(M-c))
for s in range(1, H+W):
    for b in range(max(s-H+1, 0), min(s+1, W)):
        a = s-b
        c = C[a][b]
        if a>=1:
            d = dp[a-1][b]
            dp[a][b]|=(d<<c)|(d>>c)
        if b>=1:
            d = dp[a][b-1]
            dp[a][b]|=(d<<c)|(d>>c)
ans = 10**10
d = dp[-1][-1]
for i in range(0, M*2+1):
    if 1<<i&d:
        ans = min(ans, abs(i-M))
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
h,w=map(int,input().split())
A=[]
for i in range(h):
    a_list=list(map(int,input().split()))
    A.append(a_list)
B=[]
for i in range(h):
    b_list=list(map(int,input().split()))
    B.append(b_list)
dp=[]
for i in range(w):
    sub_list=[False]*12802
    dp.append(sub_list)
dp[0][0]=True
for i in range(h):
    for j in range(w):
        c=A[i][j]-B[i][j]
        l=[False]*12802
        for x in range(12802):
            if dp[j][x]:
                l[abs(x+c)]=True
                l[abs(x-c)]=True
                if j<w-1:
                    dp[j+1][abs(x+c)]=True
                    dp[j+1][abs(x-c)]=True
        dp[j]=l
ans=20000
for x in range(12802):
    if dp[w-1][x]:
        ans=min(ans,x)
print(ans)

Solution (Python):
h, w = map(int, input().split())
a = []
b = []
for _ in range(h):
    a.append(list(map(int, input().split())))
for _ in range(h):
    b.append(list(map(int, input().split())))

grid = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        grid[i][j] = abs(a[i][j] - b[i][j])

dp = [[0 for _ in range(80*(h+w) + 1)] for _ in range(h+w)]
dp[0][0] = 1
for ij in range(h+w-1):
    for i in range(h):
        j = ij - i
        if j < 0 or j >= w:
            continue
        c = grid[i][j]
        for k in range(80*(h+w-1) + 1):
            if dp[ij][k] == 1:
                dp[ij+1][k+c] = 1
                dp[ij+1][abs(k-c)] = 1

for i in range(100):
    if dp[-1][i] == 1:
        print(i)
        exit()

Solution (Python):
def chk(a):
    L = []
    for i in range(13000):
        if a >> i & 1:
            L.append(i)
    return L
H, W = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(H)]
B = [[int(a) for a in input().split()] for _ in range(H)]
C = [[A[i][j] - B[i][j] for j in range(W)] for i in range(H)]
m = (1 << 12800) - 1
X = [[0] * (W) for _ in range(H)]
X[0][0] = (1 << 80 + C[0][0]) | (1 << 80 - C[0][0])
for i in range(H):
    for j in range(W):
        if i:
            X[i][j] |= (X[i-1][j] << 80 + C[i][j]) | (X[i-1][j] << 80 - C[i][j])
        if j:
            X[i][j] |= (X[i][j-1] << 80 + C[i][j]) | (X[i][j-1] << 80 - C[i][j])
        X[i][j] &= m
s = bin(X[-1][-1] + (1<<13000))
mi = 1<<100
for i in range(len(s)):
    if s[-i-1] == "1":
        mi = min(mi, abs(i-(H+W-1)*80))
print(mi)

Solution (Python):
def main():
    h,w=map(int,input().split())
    a=[list(map(int,input().split())) for _ in [0]*h]
    b=[list(map(int,input().split())) for _ in [0]*h]
    c=[[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]
    t=7160
    dp1=[[False]*(t+1) for _ in [0]*w]
    dp1[0][c[0][0]]=True
    for j in range(1,w):
        v=c[0][j]
        for k in range(t+1):
            if dp1[j-1][k]==True:
                if v+k<=t:
                    dp1[j][v+k]=True
                if abs(v-k)<=0:
                    dp1[j][abs(v-k)]=True
    for i in range(1,h):
        dp2=[[False]*(t+1) for _ in [0]*w]
        for j in range(w):
            v=c[i][j]
            for k in range(t+1):
                if dp1[j][k]==True:
                    if v+k<=t:
                        dp2[j][v+k]=True
                    if abs(v-k)<=t:
                        dp2[j][abs(v-k)]=True
        for j in range(1,w):
            v=c[i][j]
            for k in range(t+1):
                if dp2[j-1][k]==True:
                    if v+k<=t:
                        dp2[j][v+k]=True
                    if abs(v-k)<=t:
                        dp2[j][abs(v-k)]=True  
        dp1=dp2
    for i,j in enumerate(dp1[w-1]):
        if j==True:
            print(i)
            break
main()

Solution (Python):
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
b = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(m)] for _ in range(n)]
dp[0][0] = (1 << (a[0][0] - b[0][0] + 12880)) | 1 << (b[0][0] - a[0][0] + 12880)
mxs = (1 << (12880 * 2 + 1)) - 1
for i in range(n):
	for j in range(m):
		if not i and not j:
			continue
		d = abs(a[i][j] - b[i][j])
		if i:
			u = (dp[i - 1][j] << d) & mxs
			v = (dp[i - 1][j] >> d)
			dp[i][j] |= u
			dp[i][j] |= v
		if j:
			u = (dp[i][j - 1] << d) & mxs
			v = (dp[i][j - 1] >> d) & mxs
			dp[i][j] |= u
			dp[i][j] |= v

c = dp[n - 1][m - 1] >> 12880
for i in range(12880):
	if c & 1:
		print(i)
		break
	c >>= 1

Solution (Python):
import numpy as np

h, w = list(map(int, input().split()))

aaa = [list(map(int, input().split())) for _ in range(h)]
bbb = [list(map(int, input().split())) for _ in range(h)]
aaa = np.array(aaa, dtype=np.int8)
bbb = np.array(bbb, dtype=np.int8)
diff = abs(aaa - bbb)


def merge_new_can(d, can, prev_can):
    if d == 0:
        can |= prev_can
    else:
        can[d:] |= prev_can[:-d]
        can[:-d] |= prev_can[d:]


prev_row = [None] * w

can = np.zeros(25601, dtype=np.int8)
can[diff[0][0] + 12800] = 1
prev_row[0] = can

for j in range(1, w):
    d = diff[0][j]
    can = np.zeros(25601, dtype=np.int8)
    prev_can = prev_row[j - 1]
    merge_new_can(d, can, prev_can)
    prev_row[j] = can

for i in range(1, h):
    curr_row = [None] * w

    d = diff[i][0]
    prev_can = prev_row[0]
    can = np.zeros(25601, dtype=np.int8)
    merge_new_can(d, can, prev_can)
    curr_row[0] = can

    for j in range(1, w):
        d = diff[i][j]
        can = np.zeros(25601, dtype=np.int8)
        prev_can1 = prev_row[j]
        prev_can2 = curr_row[j - 1]
        merge_new_can(d, can, prev_can1)
        merge_new_can(d, can, prev_can2)
        curr_row[j] = can

    prev_row = curr_row

goal = prev_row[-1]
goal[12801:] |= goal[:12800][::-1]
goal = goal[12800:]
print(np.argmax(goal))

Solution (Python):
def main():
    h, w = map(int, raw_input().split())
    aa = [map(int, raw_input().split()) for _ in xrange(h)]
    bb = [map(int, raw_input().split()) for _ in xrange(h)]
    dp = [{aa[0][0] - bb[0][0]}]
    for x in xrange(1, w):
        a = aa[0][x] - bb[0][x]
        ab = set()
        for c in dp[-1]:
            ab.add(abs(c + a))
            ab.add(abs(c - a))
        dp.append(ab)
    dp = [dp]
    for y in xrange(1, h):
        a = aa[y][0] - bb[y][0]
        ab = set()
        for c in dp[y - 1][0]:
            ab.add(abs(c + a))
            ab.add(abs(c - a))
        dp.append([ab])
        for x in xrange(1, w):
            a = aa[y][x] - bb[y][x]
            ab = set()
            for c in dp[y - 1][x]:
                ab.add(abs(c + a))
                ab.add(abs(c - a))
            for c in dp[y][x - 1]:
                ab.add(abs(c + a))
                ab.add(abs(c - a))
            dp[-1].append(ab)
    print min(abs(c) for c in dp[-1][-1])


main()

Solution (Python):



import sys
read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines


h,w = [int(i) for i in readline().split()]

a = [[int(i) for i in readline().split()] for _ in range(h)]
b = [[int(i) for i in readline().split()] for _ in range(h)]


dp = [[0] for _ in range(w)]
dp[0][0] = 1


N = 6401
for i in range(h):
    ndp = [[0]*N for _ in range(w)]
    for j in range(w):
        v = abs(a[i][j] - b[i][j])
        
        for ii,c in enumerate(dp[j]):
            if ii+v < N:
                ndp[j][abs(ii+v)] |= c
            ndp[j][abs(ii-v)] |= c
        if j:
            for ii,c in enumerate(ndp[j-1]):
                if ii+v < N:
                    ndp[j][abs(ii+v)] |= c
                ndp[j][abs(ii-v)] |= c

    dp = ndp
    
    
c = [i for i,c in enumerate(dp[j]) if c]


print(min(c))

Solution (Python):
import sys
readline = sys.stdin.readline


def reverse(d, x):
    res = 0
    for i in range(x+1):
        res <<= 1
        if (1<<i) & d:
            res |= 1
    return res

H, W = map(int, readline().split())

A = [list(map(int, readline().split())) for _ in range(H)]
B = [list(map(int, readline().split())) for _ in range(H)]
G = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        G[i][j] = abs(A[i][j] - B[i][j])

dp = [[0]*W for _ in range(H)]
dp[0][0] = 1<<G[0][0]
for s in range(H+W-1):
    for h in range(max(0, s-(W-1)), 1+min(s, H-1)):
        w = s - h
        d = dp[h][w]
        if w != W-1:
            g = G[h][w+1]
            dp[h][w+1] |= d<<g | d>>g | reverse(d, g)
        if h != H-1:
            g = G[h+1][w]
            dp[h+1][w] |= d<<g | d>>g | reverse(d, g)
ans = dp[H-1][W-1]
ans = (-ans&ans).bit_length() - 1
print(ans)