Latin Square (Codeforces 1458C)
Tags: Math, matrices

You are given a square matrix of size $$$n$$$. Every row and every column of this matrix is a permutation of $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$n$$$. Let $$$a_{i, j}$$$ be the element at the intersection of $$$i$$$-th row and $$$j$$$-th column for every $$$1 \leq i, j \leq n$$$. Rows are numbered $$$1, \ldots, n$$$ top to bottom, and columns are numbered $$$1, \ldots, n$$$ left to right.There are six types of operations:   R: cyclically shift all columns to the right, formally, set the value of each $$$a_{i, j}$$$ to $$$a_{i, ((j - 2)\bmod n) + 1}$$$;  L: cyclically shift all columns to the left, formally, set the value of each $$$a_{i, j}$$$ to $$$a_{i, (j\bmod n) + 1}$$$;  D: cyclically shift all rows down, formally, set the value of each $$$a_{i, j}$$$ to $$$a_{((i - 2)\bmod n) + 1, j}$$$;  U: cyclically shift all rows up, formally, set the value of each $$$a_{i, j}$$$ to $$$a_{(i\bmod n) + 1, j}$$$;  I: replace the permutation read left to right in each row with its inverse.  C: replace the permutation read top to bottom in each column with its inverse.  Inverse of a permutation $$$p_1$$$, $$$p_2$$$, $$$\ldots$$$, $$$p_n$$$ is a permutation $$$q_1$$$, $$$q_2$$$, $$$\ldots$$$, $$$q_n$$$, such that $$$p_{q_i} = i$$$ for every $$$1 \leq i \leq n$$$.One can see that after any sequence of operations every row and every column of the matrix will still be a permutation of $$$1, 2, \ldots, n$$$.Given the initial matrix description, you should process $$$m$$$ operations and output the final matrix.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — number of test cases. $$$t$$$ test case descriptions follow.The first line of each test case description contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 1000, 1 \leq m \leq 10^5$$$) — size of the matrix and number of operations.Each of the next $$$n$$$ lines contains $$$n$$$ integers separated by single spaces — description of the matrix $$$a$$$ ($$$1 \leq a_{i, j} \leq n$$$).The last line of the description contains a string of $$$m$$$ characters describing the operations in order, according to the format above.The sum of $$$n$$$ does not exceed $$$1000$$$, and the sum of $$$m$$$ does not exceed $$$10^5$$$.

Output: For each test case, print $$$n$$$ lines with $$$n$$$ integers each — the final matrix after $$$m$$$ operations.

Note: Line breaks between sample test case answers are only for clarity, and don't have to be printed.

Sample Inputs:
5
3 2
1 2 3
2 3 1
3 1 2
DR
3 2
1 2 3
2 3 1
3 1 2
LU
3 1
1 2 3
2 3 1
3 1 2
I
3 1
1 2 3
2 3 1
3 1 2
C
3 16
1 2 3
2 3 1
3 1 2
LDICRUCILDICRUCI

Sample Outputs:
2 3 1 
3 1 2 
1 2 3 

3 1 2 
1 2 3 
2 3 1 

1 2 3 
3 1 2 
2 3 1 

1 3 2 
2 1 3 
3 2 1 

2 3 1 
3 1 2 
1 2 3

Solution (Python):
import sys, io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
out = []
for _ in range(t):
    (n, m) = map(int, input().split())
    MAT = [list(map(int, input().split())) for i in range(n)]
    dx = 0
    dy = 0
    order = [0, 1, 2]
    d = [0, 0, 0]
    s = input()
    for c in s:
        if c == ord('R'):
            d[1] += 1
        elif c == ord('L'):
            d[1] -= 1
        elif c == ord('D'):
            d[0] += 1
        elif c == ord('U'):
            d[0] -= 1
        elif c == ord('I'):
            (order[1], order[2]) = (order[2], order[1])
            (d[1], d[2]) = (d[2], d[1])
        elif c == ord('C'):
            (order[0], order[2]) = (order[2], order[0])
            (d[0], d[2]) = (d[2], d[0])
    om = [[0] * n for i in range(n)]
    for i in range(n):
        for j in range(n):
            (r, c, v) = (i, j, MAT[i][j] - 1)
            trip = [-1, -1, -1]
            for u in range(3):
                trip[u] = [r, c, v][order[u]]
                trip[u] += d[u]
                trip[u] %= n
            om[trip[0]][trip[1]] = trip[2] + 1
    for line in om:
        out.append(' '.join(map(str, line)))
print('\n'.join(out))

Solution (Python):
import sys, io, os
Z = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
Y = lambda : [*map(int, Z().split())]

def I(M):
    n = len(M)
    nM = [[0] * n for i in range(n)]
    for x in range(n):
        for y in range(n):
            nM[x][M[x][y] - 1] = y + 1
    return nM

def C(M):
    n = len(M)
    nM = [[0] * n for i in range(n)]
    for x in range(n):
        for y in range(n):
            nM[M[x][y] - 1][y] = x + 1
    return nM

def T(M):
    n = len(M)
    nM = [[0] * n for i in range(n)]
    for x in range(n):
        for y in range(n):
            nM[x][y] = M[y][x]
    return nM
o = []
for _ in range(int(Z())):
    (n, m) = Y()
    M = []
    for i in range(n):
        M.append(Y())
    s = Z().strip()
    s = s[::-1]
    dx = dy = dv = 0
    ui = t = 0
    for i in s:
        if ui == 67:
            if i == 68:
                i = 65
            elif i == 85:
                i = 83
            elif i == 73:
                i = 84
            elif i == 67:
                ui = i = 0
        elif ui == 73:
            if i == 82:
                i = 65
            elif i == 76:
                i = 83
            elif i == 67:
                i = 84
            elif i == 73:
                ui = i = 0
        if t:
            if i == 82:
                i = 68
            elif i == 76:
                i = 85
            elif i == 68:
                i = 82
            elif i == 85:
                i = 76
        if i == 82:
            dx += 1
        elif i == 76:
            dx -= 1
        elif i == 68:
            dy += 1
        elif i == 85:
            dy -= 1
        elif i == 73:
            ui = 73
        elif i == 67:
            ui = 67
        elif i == 84:
            t = 1 - t
        elif i == 83:
            dv -= 1
        elif i == 65:
            dv += 1
    if ui == 67:
        M = C(M)
    elif ui == 73:
        M = I(M)
    if t:
        M = T(M)
    nM = [[0] * n for i in range(n)]
    for x in range(n):
        for y in range(n):
            nM[x][y] = (M[(x - dy) % n][(y - dx) % n] - 1 + dv) % n + 1
    o.append('\n'.join((' '.join(map(str, r)) for r in nM)))
print('\n\n'.join(o))

Solution (Python):
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

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, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for _ in range(t):
    (n, m) = map(int, input().split())
    grid = []
    for i in range(n):
        grid.append(list(map(int, input().split())))
    s = input()
    a = 0
    b = 0
    c = 0
    for i in s:
        if i == 'R':
            b += 1
        elif i == 'L':
            b -= 1
        elif i == 'D':
            a += 1
        elif i == 'U':
            a -= 1
        elif i == 'I':
            tmp = b
            b = c
            c = tmp
        else:
            tmp = a
            a = c
            c = tmp
    pt = [a, b, c]
    dest0 = 0
    dest1 = 1
    dest2 = 2
    for i in s:
        if i == 'I':
            tmp = dest1
            dest1 = dest2
            dest2 = tmp
        elif i == 'C':
            tmp = dest0
            dest0 = dest2
            dest2 = tmp
    st = []
    for i in range(3):
        if dest0 == i:
            st.append(0)
        if dest1 == i:
            st.append(1)
        if dest2 == i:
            st.append(2)
    ans = []
    for i in range(n):
        ans.append([])
        for j in range(n):
            ans[-1].append(0)
    for i in range(n):
        for j in range(n):
            start = [i, j, grid[i][j] - 1]
            tmpans = [0, 0, 0]
            for k in range(3):
                tmpans[st[k]] = (pt[st[k]] + start[k]) % n
            ans[tmpans[0]][tmpans[1]] = str(tmpans[2] + 1)
    for a in ans:
        print(' '.join(a))