Nice table (Codeforces 1098B)
Tags: Greedy, brute force

You are given an $$$n \times m$$$ table, consisting of characters «A», «G», «C», «T». Let's call a table nice, if every $$$2 \times 2$$$ square contains all four distinct characters. Your task is to find a nice table (also consisting of «A», «G», «C», «T»), that differs from the given table in the minimum number of characters.

Input: First line contains two positive integers $$$n$$$ and $$$m$$$ — number of rows and columns in the table you are given ($$$2 \leq n, m, n \times m \leq 300\,000$$$). Then, $$$n$$$ lines describing the table follow. Each line contains exactly $$$m$$$ characters «A», «G», «C», «T».

Output: Output $$$n$$$ lines, $$$m$$$ characters each. This table must be nice and differ from the input table in the minimum number of characters.

Note: In the first sample, the table is already nice. In the second sample, you can change 9 elements to make the table nice.

Sample Inputs:
2 2
AG
CT

3 5
AGCAG
AGCAG
AGCAG

Sample Outputs:
AG
CT

TGCAT
CATGC
TGCAT

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * m + v
(n, m) = map(int, input().split())
u = list('AGCT')
d = dict()
for i in range(4):
    d[u[i]] = i
s = [0] * (n * m)
for i in range(n):
    s0 = list(input().rstrip().decode())
    for j in range(m):
        s[f(i, j)] = d[s0[j]]
(ma1, m1, m2) = (-1, [], [])
for i in range(4):
    for j in range(i + 1, 4):
        (c1, c2) = ([i, j], [])
        for k in range(4):
            if i ^ k and j ^ k:
                c2.append(k)
        c = 0
        for k in range(n):
            (a, b) = (0, 0)
            if not k & 1:
                for l in range(m):
                    if s[f(k, l)] == c1[l & 1]:
                        a += 1
                    elif s[f(k, l)] == c1[l & 1 ^ 1]:
                        b += 1
            else:
                for l in range(m):
                    if s[f(k, l)] == c2[l & 1]:
                        a += 1
                    elif s[f(k, l)] == c2[l & 1 ^ 1]:
                        b += 1
            c += max(a, b)
        if ma1 < c:
            (ma1, m1, m2) = (c, c1, c2)
(ma2, m3, m4) = (-1, [], [])
for i in range(4):
    for j in range(i + 1, 4):
        (c1, c2) = ([i, j], [])
        for k in range(4):
            if i ^ k and j ^ k:
                c2.append(k)
        c = 0
        for l in range(m):
            (a, b) = (0, 0)
            if not l & 1:
                for k in range(n):
                    if s[f(k, l)] == c1[k & 1]:
                        a += 1
                    elif s[f(k, l)] == c1[k & 1 ^ 1]:
                        b += 1
            else:
                for k in range(n):
                    if s[f(k, l)] == c2[k & 1]:
                        a += 1
                    elif s[f(k, l)] == c2[k & 1 ^ 1]:
                        b += 1
            c += max(a, b)
        if ma2 < c:
            (ma2, m3, m4) = (c, c1, c2)
ans0 = [0] * (n * m)
if ma1 >= ma2:
    c = 0
    (c1, c2) = (m1, m2)
    for k in range(n):
        (a, b) = (0, 0)
        if not k & 1:
            for l in range(m):
                if s[f(k, l)] == c1[l & 1]:
                    a += 1
                elif s[f(k, l)] == c1[l & 1 ^ 1]:
                    b += 1
            i = 0 if a >= b else 1
            for l in range(m):
                ans0[f(k, l)] = c1[l & 1 ^ i]
        else:
            for l in range(m):
                if s[f(k, l)] == c2[l & 1]:
                    a += 1
                elif s[f(k, l)] == c2[l & 1 ^ 1]:
                    b += 1
            i = 0 if a >= b else 1
            for l in range(m):
                ans0[f(k, l)] = c2[l & 1 ^ i]
else:
    c = 0
    (c1, c2) = (m3, m4)
    for l in range(m):
        (a, b) = (0, 0)
        if not l & 1:
            for k in range(n):
                if s[f(k, l)] == c1[k & 1]:
                    a += 1
                elif s[f(k, l)] == c1[k & 1 ^ 1]:
                    b += 1
            i = 0 if a >= b else 1
            for k in range(n):
                ans0[f(k, l)] = c1[k & 1 ^ i]
        else:
            for k in range(n):
                if s[f(k, l)] == c2[k & 1]:
                    a += 1
                elif s[f(k, l)] == c2[k & 1 ^ 1]:
                    b += 1
            i = 0 if a >= b else 1
            for k in range(n):
                ans0[f(k, l)] = c2[k & 1 ^ i]
ans = ['?'] * n
for i in range(n):
    ans1 = ''.join([u[ans0[j]] for j in range(i * m, (i + 1) * m)])
    ans[i] = ans1
sys.stdout.write('\n'.join(ans))

Solution (Python):
from itertools import permutations
from sys import stdin, stdout
(ly, lx) = map(int, input().split())
grid = [[c for c in inp] for inp in stdin.read().splitlines()]
first = set()
bl = []
bpattern = []
bcost = 1000000.0
flip_row = False
for l in permutations('AGCT'):
    if bcost == 0:
        break
    if ''.join(l[:2]) in first:
        continue
    first |= set([''.join(l[:2]), ''.join(l[1::-1])])
    cost = 0
    pattern = [0] * ly
    for i in range(ly):
        (diff1, diff2) = (0, 0)
        for j in range(lx):
            if grid[i][j] != l[((i & 1) << 1) + (j & 1)]:
                diff1 += 1
            if grid[i][j] != l[((i & 1) << 1) + ((j ^ 1) & 1)]:
                diff2 += 1
        cost += min(diff1, diff2)
        if diff1 >= diff2:
            pattern[i] = 1
    if cost < bcost:
        bcost = cost
        bpattern = pattern.copy()
        flip_row = True
        bl = l
    cost = 0
    pattern = [0] * lx
    for j in range(lx):
        diff1 = diff2 = 0
        for i in range(ly):
            if grid[i][j] != l[((j & 1) << 1) + (i & 1)]:
                diff1 += 1
            if grid[i][j] != l[((j & 1) << 1) + ((i ^ 1) & 1)]:
                diff2 += 1
        cost += min(diff1, diff2)
        if diff1 >= diff2:
            pattern[j] = 1
    if cost < bcost:
        bcost = cost
        bpattern = pattern.copy()
        flip_row = False
        bl = l
if flip_row:
    for i in range(ly):
        grid[i] = ''.join([bl[((i & 1) << 1) + ((j ^ bpattern[i]) & 1)] for j in range(lx)])
else:
    for i in range(ly):
        grid[i] = ''.join([bl[((j & 1) << 1) + ((i ^ bpattern[j]) & 1)] for j in range(lx)])
print('\n'.join((''.join((k for k in grid[i])) for i in range(ly))))

Solution (Python):
from itertools import permutations
from sys import stdin, stdout
(ly, lx) = map(int, input().split())
grid = [[c for c in inp] for inp in stdin.read().splitlines()]
first = set()
bl = []
bpattern = []
bcost = 1000000.0
flip_row = False
for l in permutations('AGCT'):
    if bcost == 0:
        break
    if ''.join(l[:2]) in first:
        continue
    first |= set([''.join(l[:2]), ''.join(l[1::-1])])
    cost = 0
    pattern = [0] * ly
    for i in range(ly):
        (diff1, diff2) = (0, 0)
        for j in range(lx):
            if grid[i][j] != l[((i & 1) << 1) + (j & 1)]:
                diff1 += 1
            if grid[i][j] != l[((i & 1) << 1) + ((j ^ 1) & 1)]:
                diff2 += 1
        cost += min(diff1, diff2)
        if diff1 >= diff2:
            pattern[i] = 1
    if cost < bcost:
        bcost = cost
        bpattern = pattern.copy()
        flip_row = True
        bl = l
    cost = 0
    pattern = [0] * lx
    for j in range(lx):
        diff1 = diff2 = 0
        for i in range(ly):
            if grid[i][j] != l[((j & 1) << 1) + (i & 1)]:
                diff1 += 1
            if grid[i][j] != l[((j & 1) << 1) + ((i ^ 1) & 1)]:
                diff2 += 1
        cost += min(diff1, diff2)
        if diff1 >= diff2:
            pattern[j] = 1
    if cost < bcost:
        bcost = cost
        bpattern = pattern.copy()
        flip_row = False
        bl = l
if flip_row:
    for i in range(ly):
        grid[i] = ''.join([bl[((i & 1) << 1) + ((j ^ bpattern[i]) & 1)] for j in range(lx)])
else:
    for i in range(ly):
        grid[i] = ''.join([bl[((j & 1) << 1) + ((i ^ bpattern[j]) & 1)] for j in range(lx)])
stdout.write('\n'.join((''.join((k for k in grid[i])) for i in range(ly))))