Chessboard (Codeforces 961C)
Tags: Implement, bitmasks

Magnus decided to play a classic chess game. Though what he saw in his locker shocked him! His favourite chessboard got broken into 4 pieces, each of size n by n, n is always odd. And what's even worse, some squares were of wrong color. j-th square of the i-th row of k-th piece of the board has color ak, i, j; 1 being black and 0 being white. Now Magnus wants to change color of some squares in such a way that he recolors minimum number of squares and obtained pieces form a valid chessboard. Every square has its color different to each of the neightbouring by side squares in a valid board. Its size should be 2n by 2n. You are allowed to move pieces but not allowed to rotate or flip them.

Input: The first line contains odd integer n (1 ≤ n ≤ 100) — the size of all pieces of the board. Then 4 segments follow, each describes one piece of the board. Each consists of n lines of n characters; j-th one of i-th line is equal to 1 if the square is black initially and 0 otherwise. Segments are separated by an empty line.

Output: Print one number — minimum number of squares Magnus should recolor to be able to obtain a valid chessboard.


Sample Inputs:
1
0
0
1
0

3
101
010
101
101
000
101
010
101
011
010
101
010

Sample Outputs:
1

2

Solution (Python):
new_n = int(input())
c = [0] * 4
for k in range(4):
    for i in range(new_n):
        s = input()
        for j in range(new_n):
            if (i + j) % 2 != int(s[j]):
                c[k] += 1
    if k < 3:
        input()
c.sort()
result = c[0] + c[1] + 2 * new_n * new_n - c[2] - c[3]
print(result)

Solution (Python):
def main():
    pieces_Dimension = int(input())
    piece1 = ''.join((input() for _ in range(pieces_Dimension)))
    input()
    piece2 = ''.join((input() for _ in range(pieces_Dimension)))
    input()
    piece3 = ''.join((input() for _ in range(pieces_Dimension)))
    input()
    piece4 = ''.join((input() for _ in range(pieces_Dimension)))
    brokenPieces = (piece1, piece2, piece3, piece4)
    nSquares = pieces_Dimension * pieces_Dimension
    squares = '01' * (nSquares // 2) + '0'
    return nSquaresToRecolorIn(brokenPieces, nSquares, squares)

def nSquaresToRecolorIn(brokenPieces, nSquares, squares):
    possible_nSquares = [sum((piece[i] != squares[i] for i in range(nSquares))) for piece in brokenPieces]
    possible_nSquares.sort()
    return 2 * nSquares + possible_nSquares[0] + possible_nSquares[1] - possible_nSquares[2] - possible_nSquares[3]
if __name__ == '__main__':
    print(main())

Solution (Python):
import sys
try:

    def check(n):
        count1 = 0
        s = ''
        while n != 0:
            if n % 2:
                count1 += 1
                s = '1' + s
            else:
                s = '0' + s
            n //= 2
        return s

    def solve(flag, n, l):
        temp_ans = 0
        for i in range(n):
            y = z[flag] ^ int(l[i], 2)
            b = bin(y)
            temp_ans += b.count('1')
            flag = not flag
        return temp_ans
    n = int(input())
    l1 = [input() for y in range(n)]
    temp = input()
    l2 = [input() for y in range(n)]
    temp = input()
    l3 = [input() for y in range(n)]
    temp = input()
    l4 = [input() for y in range(n)]
    z = []
    s = 0
    for i in range(n):
        if i % 2 == 1:
            s += 2 ** i
    z.append(s)
    z.append(z[0] ^ 2 ** n - 1)
    ans = m = sys.maxsize
    for i in range(2, 17):
        s = check(i)
        if s.count('1') == 2:
            s = (4 - len(s)) * '0' + s
            res = sys.maxsize
            for i in range(4):
                if i == 0:
                    x = l1
                elif i == 1:
                    x = l2
                elif i == 2:
                    x = l3
                else:
                    x = l4
                if s[i] == '1':
                    res += min(res, solve(1, n, x))
                else:
                    res += min(res, solve(0, n, x))
            ans = min(ans, res - m)
    print(ans)
except EOFError:
    pass