The Light Square (Codeforces 1218I)
Tags: Greedy, 2-sat

For her birthday Alice received an interesting gift from her friends – The Light Square. The Light Square game is played on an $$$N \times N$$$ lightbulbs square board with a magical lightbulb bar of size $$$N \times 1$$$ that has magical properties. At the start of the game some lights on the square board and magical bar are turned on. The goal of the game is to transform the starting light square board pattern into some other pattern using the magical bar without rotating the square board. The magical bar works as follows: It can be placed on any row or column The orientation of the magical lightbulb must be left to right or top to bottom for it to keep its magical properties The entire bar needs to be fully placed on a board The lights of the magical bar never change If the light on the magical bar is the same as the light of the square it is placed on it will switch the light on the square board off, otherwise it will switch the light on The magical bar can be used an infinite number of times Alice has a hard time transforming her square board into the pattern Bob gave her. Can you help her transform the board or let her know it is impossible? If there are multiple solutions print any. 

Input: The first line contains one positive integer number $$$N\ (1 \leq N \leq 2000)$$$ representing the size of the square board. The next $$$N$$$ lines are strings of length $$$N$$$ consisting of 1's and 0's representing the initial state of the square board starting from the top row. If the character in a string is 1 it means the light is turned on, otherwise it is off. The next $$$N$$$ lines are strings of length $$$N$$$ consisting of 1's and 0's representing the desired state of the square board starting from the top row that was given to Alice by Bob. The last line is one string of length $$$N$$$ consisting of 1's and 0's representing the pattern of the magical bar in a left to right order. 

Output: Transform the instructions for Alice in order to transform the square board into the pattern Bob gave her. The first line of the output contains an integer number $$$M\ (0 \leq M \leq 10^5$$$) representing the number of times Alice will need to apply the magical bar. The next $$$M$$$ lines are of the form "col $$$X$$$" or "row $$$X$$$", where $$$X$$$ is $$$0$$$-based index of the matrix, meaning the magical bar should be applied to either row $$$X$$$ or column $$$X$$$. If there is no solution, print only -1. In case of multiple solutions print any correct one. 

Note: Example 1: It is impossible to transform square board from one format to anotherExample 2: Magic bar can be applied on first row or column.

Sample Inputs:
2
11
11
00
01
11

2
10
00
00
00
10

3
110
011
100
100
011
100
100

Sample Outputs:
-1

1
row 0

3
row 0
col 0
col 1

Solution (Python):
""""""
N = int(input())
(initial, desired) = ([], [])
for n in range(N):
    initial.append(input())
for n in range(N):
    desired.append(input())
bar = input()
init_bar_index = -1 if bar.count('1') == 0 else bar.index('1')

def get_variable(ca, row, col):
    """"""
    v = int(initial[row][col]) ^ int(bar[row]) * ca[col]
    if v == v ^ int(bar[col]):
        if v == int(desired[row][col]):
            return None
        else:
            return False
    return v != int(desired[row][col])
if init_bar_index < 0:
    print(0 if initial == desired else -1)
else:
    (row_actions, col_actions) = ([], [])
    for n in range(N):
        if initial[init_bar_index][n] != desired[init_bar_index][n]:
            col_actions.append(1)
        else:
            col_actions.append(0)
    possible = True
    for n in range(N):
        inv = get_variable(col_actions, n, 0)
        for m in range(1, N):
            v = get_variable(col_actions, n, m)
            if v is not None and inv is None:
                inv = v
            if inv is not None and v is not None and (inv != v):
                possible = False
        row_actions.append(1 if inv else 0)
    if possible:
        print(sum(row_actions) + sum(col_actions))
        for r in range(len(row_actions)):
            if row_actions[r]:
                print('row', r)
        for c in range(len(col_actions)):
            if col_actions[c]:
                print('col', c)
    else:
        print(-1)

Solution (Python):
import random, sys, os, math, gc
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce, cmp_to_key
from itertools import accumulate, combinations, permutations, product
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
from bisect import bisect_left, bisect_right
from math import factorial, gcd
from operator import mul, xor
from types import GeneratorType
BUFSIZE = 8192
MOD = 10 ** 9 + 7
MODD = 998244353
INF = float('inf')
D4 = [(1, 0), (0, 1), (-1, 0), (0, -1)]
D8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

def solve():
    n = II()
    a = [[int(i) for i in I()] for _ in range(n)]
    b = [[int(i) for i in I()] for _ in range(n)]
    s = [int(i) for i in I()]
    for i in range(n):
        for j in range(n):
            a[i][j] ^= b[i][j]
    ans = []
    for x in range(n):
        if s[x]:
            for i in range(n):
                if a[i][x]:
                    ans.append(('row', i))
                    for j in range(n):
                        a[i][j] ^= s[j]
            for j in range(n):
                if a[x][j]:
                    ans.append(('col', j))
                    for i in range(n):
                        a[i][j] ^= s[i]
            break
    else:
        return print(-1)
    if sum((sum(i) for i in a)):
        return print(-1)
    print(len(ans))
    for i in ans:
        print(*i)

def main():
    t = 1
    for _ in range(t):
        solve()

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def bitcnt(n):
    c = (n & 6148914691236517205) + (n >> 1 & 6148914691236517205)
    c = (c & 3689348814741910323) + (c >> 2 & 3689348814741910323)
    c = (c & 1085102592571150095) + (c >> 4 & 1085102592571150095)
    c = (c & 71777214294589695) + (c >> 8 & 71777214294589695)
    c = (c & 281470681808895) + (c >> 16 & 281470681808895)
    c = (c & 4294967295) + (c >> 32 & 4294967295)
    return c

def lcm(x, y):
    return x * y // gcd(x, y)

def lowbit(x):
    return x & -x

def perm(n, r):
    return factorial(n) // factorial(n - r) if n >= r else 0

def comb(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def probabilityMod(x, y, mod):
    return x * pow(y, mod - 2, mod) % mod

class SortedList:

    def __init__(self, iterable=[], _load=200):
        """"""
        values = sorted(iterable)
        self._len = _len = len(values)
        self._load = _load
        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
        self._list_lens = [len(_list) for _list in _lists]
        self._mins = [_list[0] for _list in _lists]
        self._fen_tree = []
        self._rebuild = True

    def _fen_build(self):
        """"""
        self._fen_tree[:] = self._list_lens
        _fen_tree = self._fen_tree
        for i in range(len(_fen_tree)):
            if i | i + 1 < len(_fen_tree):
                _fen_tree[i | i + 1] += _fen_tree[i]
        self._rebuild = False

    def _fen_update(self, index, value):
        """"""
        if not self._rebuild:
            _fen_tree = self._fen_tree
            while index < len(_fen_tree):
                _fen_tree[index] += value
                index |= index + 1

    def _fen_query(self, end):
        """"""
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        x = 0
        while end:
            x += _fen_tree[end - 1]
            end &= end - 1
        return x

    def _fen_findkth(self, k):
        """"""
        _list_lens = self._list_lens
        if k < _list_lens[0]:
            return (0, k)
        if k >= self._len - _list_lens[-1]:
            return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
        if self._rebuild:
            self._fen_build()
        _fen_tree = self._fen_tree
        idx = -1
        for d in reversed(range(len(_fen_tree).bit_length())):
            right_idx = idx + (1 << d)
            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
                idx = right_idx
                k -= _fen_tree[idx]
        return (idx + 1, k)

    def _delete(self, pos, idx):
        """"""
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len -= 1
        self._fen_update(pos, -1)
        del _lists[pos][idx]
        _list_lens[pos] -= 1
        if _list_lens[pos]:
            _mins[pos] = _lists[pos][0]
        else:
            del _lists[pos]
            del _list_lens[pos]
            del _mins[pos]
            self._rebuild = True

    def _loc_left(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (lo, pos) = (-1, len(_lists) - 1)
        while lo + 1 < pos:
            mi = lo + pos >> 1
            if value <= _mins[mi]:
                pos = mi
            else:
                lo = mi
        if pos and value <= _lists[pos - 1][-1]:
            pos -= 1
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value <= _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def _loc_right(self, value):
        """"""
        if not self._len:
            return (0, 0)
        _lists = self._lists
        _mins = self._mins
        (pos, hi) = (0, len(_lists))
        while pos + 1 < hi:
            mi = pos + hi >> 1
            if value < _mins[mi]:
                hi = mi
            else:
                pos = mi
        _list = _lists[pos]
        (lo, idx) = (-1, len(_list))
        while lo + 1 < idx:
            mi = lo + idx >> 1
            if value < _list[mi]:
                idx = mi
            else:
                lo = mi
        return (pos, idx)

    def add(self, value):
        """"""
        _load = self._load
        _lists = self._lists
        _mins = self._mins
        _list_lens = self._list_lens
        self._len += 1
        if _lists:
            (pos, idx) = self._loc_right(value)
            self._fen_update(pos, 1)
            _list = _lists[pos]
            _list.insert(idx, value)
            _list_lens[pos] += 1
            _mins[pos] = _list[0]
            if _load + _load < len(_list):
                _lists.insert(pos + 1, _list[_load:])
                _list_lens.insert(pos + 1, len(_list) - _load)
                _mins.insert(pos + 1, _list[_load])
                _list_lens[pos] = _load
                del _list[_load:]
                self._rebuild = True
        else:
            _lists.append([value])
            _mins.append(value)
            _list_lens.append(1)
            self._rebuild = True

    def discard(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_right(value)
            if idx and _lists[pos][idx - 1] == value:
                self._delete(pos, idx - 1)

    def remove(self, value):
        """"""
        _len = self._len
        self.discard(value)
        if _len == self._len:
            raise ValueError('{0!r} not in list'.format(value))

    def pop(self, index=-1):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        value = self._lists[pos][idx]
        self._delete(pos, idx)
        return value

    def bisect_left(self, value):
        """"""
        (pos, idx) = self._loc_left(value)
        return self._fen_query(pos) + idx

    def bisect_right(self, value):
        """"""
        (pos, idx) = self._loc_right(value)
        return self._fen_query(pos) + idx

    def count(self, value):
        """"""
        return self.bisect_right(value) - self.bisect_left(value)

    def __len__(self):
        """"""
        return self._len

    def __getitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        return self._lists[pos][idx]

    def __delitem__(self, index):
        """"""
        (pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
        self._delete(pos, idx)

    def __contains__(self, value):
        """"""
        _lists = self._lists
        if _lists:
            (pos, idx) = self._loc_left(value)
            return idx < len(_lists[pos]) and _lists[pos][idx] == value
        return False

    def __iter__(self):
        """"""
        return (value for _list in self._lists for value in _list)

    def __reversed__(self):
        """"""
        return (value for _list in reversed(self._lists) for value in reversed(_list))

    def __repr__(self):
        """"""
        return 'SortedList({0})'.format(list(self))

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))

def getGraph(n, m, directed=False):
    d = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = LGMI()
        d[u].append(v)
        if not directed:
            d[v].append(u)
    return d

def getWeightedGraph(n, m, directed=False):
    d = [[] for _ in range(n)]
    for _ in range(m):
        (u, v, w) = LII()
        u -= 1
        v -= 1
        d[u].append((v, w))
        if not directed:
            d[v].append((u, w))
    return d
if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
(inicial, desejado) = ([], [])
for n in range(N):
    inicial.append(input())
for n in range(N):
    desejado.append(input())
barra = input()
initB = -1 if barra.count('1') == 0 else barra.index('1')

def getVar(ca, row, col):
    v = int(inicial[row][col]) ^ int(barra[row]) * ca[col]
    if v == v ^ int(barra[col]):
        if v == int(desejado[row][col]):
            return None
        else:
            return False
    return v != int(desejado[row][col])
if initB < 0:
    print(0 if inicial == desejado else -1)
else:
    (rowActions, colActions) = ([], [])
    for n in range(N):
        if inicial[initB][n] != desejado[initB][n]:
            colActions.append(1)
        else:
            colActions.append(0)
    possible = True
    for n in range(N):
        inv = getVar(colActions, n, 0)
        for m in range(1, N):
            v = getVar(colActions, n, m)
            if v is not None and inv is None:
                inv = v
            if inv is not None and v is not None and (inv != v):
                possible = False
        rowActions.append(1 if inv else 0)
    if possible:
        print(sum(rowActions) + sum(colActions))
        for r in range(len(rowActions)):
            if rowActions[r]:
                print('row', r)
        for c in range(len(colActions)):
            if colActions[c]:
                print('col', c)
    else:
        print(-1)