Gojou and Matrix Game (Codeforces 1658E)
Tags: Math, hashing

Marin feels exhausted after a long day of cosplay, so Gojou invites her to play a game!Marin and Gojou take turns to place one of their tokens on an $$$n \times n$$$ grid with Marin starting first. There are some restrictions and allowances on where to place tokens:   Apart from the first move, the token placed by a player must be more than Manhattan distance $$$k$$$ away from the previous token placed on the matrix. In other words, if a player places a token at $$$(x_1, y_1)$$$, then the token placed by the other player in the next move must be in a cell $$$(x_2, y_2)$$$ satisfying $$$|x_2 - x_1| + |y_2 - y_1| > k$$$.  Apart from the previous restriction, a token can be placed anywhere on the matrix, including cells where tokens were previously placed by any player. Whenever a player places a token on cell $$$(x, y)$$$, that player gets $$$v_{x,\ y}$$$ points. All values of $$$v$$$ on the grid are distinct. You still get points from a cell even if tokens were already placed onto the cell. The game finishes when each player makes $$$10^{100}$$$ moves.Marin and Gojou will play $$$n^2$$$ games. For each cell of the grid, there will be exactly one game where Marin places a token on that cell on her first move. Please answer for each game, if Marin and Gojou play optimally (after Marin's first move), who will have more points at the end? Or will the game end in a draw (both players have the same points at the end)?

Input: The first line contains two integers $$$n$$$, $$$k$$$ ($$$3 \le n \le 2000$$$, $$$1 \leq k \leq n - 2$$$). Note that under these constraints it is always possible to make a move.The following $$$n$$$ lines contains $$$n$$$ integers each. The $$$j$$$-th integer in the $$$i$$$-th line is $$$v_{i,j}$$$ ($$$1 \le v_{i,j} \le n^2$$$). All elements in $$$v$$$ are distinct.

Output: You should print $$$n$$$ lines. In the $$$i$$$-th line, print $$$n$$$ characters, where the $$$j$$$-th character is the result of the game in which Marin places her first token in the cell $$$(i, j)$$$. Print 'M' if Marin wins, 'G' if Gojou wins, and 'D' if the game ends in a draw. Do not print spaces between the characters in one line.


Sample Inputs:
3 1
1 2 4
6 8 3
9 5 7

Sample Outputs:
GGG
MGG
MGG

Solution (Python):
import heapq
import os
import sys
from io import BytesIO, IOBase
_str = str
str = lambda x=b'': x if type(x) is bytes else _str(x).encode()
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')

def f(x, y, x1, y1, x2, y2):
    return x1 + y1 <= x + y <= x2 + y2 and x1 - y1 <= x - y <= x2 - y2

def out(x, y, x1, y1, x2, y2):
    return not x1 + y1 <= x + y <= x2 + y2 and (not x1 - y1 <= x - y <= x2 - y2)

def merge(x1, y1, x2, y2, x3, y3, x4, y4):
    new = [0] * 4
    if f(x1, y1, x3, y3, x4, y4):
        (new[0], new[1]) = (x1, y1)
    elif out(x1, y1, x3, y3, x4, y4):
        (new[0], new[1]) = (x3, y4)
    elif x3 - y3 <= x1 - y1 <= x4 - y4:
        num = (x1 - y1 - (x3 - y3)) / 2
        (new[0], new[1]) = (x3 + num, y3 - num)
    else:
        num = (x1 + y1 - (x3 + y3)) / 2
        (new[0], new[1]) = (x3 + num, y3 + num)
    if f(x2, y2, x3, y3, x4, y4):
        (new[2], new[3]) = (x2, y2)
    elif out(x2, y2, x3, y3, x4, y4):
        (new[2], new[3]) = (x4, y4)
    elif x3 + y3 <= x2 + y2 <= x4 + y4:
        num = (x4 + y4 - (x2 + y2)) / 2
        (new[2], new[3]) = (x4 - num, y4 - num)
    else:
        num = (x4 - y4 - (x2 - y2)) / 2
        (new[2], new[3]) = (x4 - num, y4 + num)
    return new

def main():
    (n, k) = list(map(int, input().split(' ')))
    v = [list(map(int, input().split(' '))) for _ in range(n)]
    max_id = None
    d = [0] * (n * n + 1)
    for i in range(n):
        for j in range(n):
            d[v[i][j]] = i * (n + 1) + j
            if v[i][j] == n * n:
                max_id = [i, j]
    valid = [max_id[0] - k, max_id[1], max_id[0] + k, max_id[1]]
    for vnow in range(n * n, 0, -1):
        (x, y) = (d[vnow] // (n + 1), d[vnow] % (n + 1))
        if not f(x, y, valid[0], valid[1], valid[2], valid[3]):
            continue
        if f(valid[0], valid[1], x - k, y, x + k, y) and f(valid[2], valid[3], x - k, y, x + k, y):
            continue
        new = merge(valid[0], valid[1], valid[2], valid[3], x - k, y, x + k, y)
        valid.clear()
        valid = new
    for i in range(n):
        res = ['G'] * n
        for j in range(n):
            if f(i, j, valid[0], valid[1], valid[2], valid[3]):
                res[j] = 'M'
        print(''.join(res))
    return
main()

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k) = map(int, input().split())
v = [list(map(int, input().split())) for _ in range(n)]
m = n * n
(x, y) = ([0] * m, [0] * m)
for i in range(n):
    vi = v[i]
    for j in range(n):
        x[vi[j] - 1] = i
        y[vi[j] - 1] = j
ans0 = [['?'] * n for _ in range(n)]
m -= 1
(xm, ym) = (x[m], y[m])
ans0[xm][ym] = 'M'
(mi1, ma1) = (xm - ym, xm - ym)
(mi2, ma2) = (xm + ym, xm + ym)
for i in range(m - 1, -1, -1):
    (xi, yi) = (x[i], y[i])
    (d1, d2) = (xi - yi, xi + yi)
    ok = 1 if max(abs(mi1 - d1), abs(ma1 - d1), abs(mi2 - d2), abs(ma2 - d2)) <= k else 0
    ans0[xi][yi] = 'M' if ok else 'G'
    if ok:
        mi1 = min(mi1, d1)
        ma1 = max(ma1, d1)
        mi2 = min(mi2, d2)
        ma2 = max(ma2, d2)
ans = []
for i in ans0:
    ans.append(''.join(i))
sys.stdout.write('\n'.join(ans))

Solution (Python):
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('debug') not in [None, '0']
if DEBUG:
    from inspect import currentframe, getframeinfo
    from re import search

def debug(*args):
    if not DEBUG:
        return
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search('\\((.*)\\)', s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')

def main():
    (N, K) = list(map(int, input().split()))
    dp = [['G'] * N for _ in range(N)]
    idx = [None] * N * N
    for r in range(N):
        row = map(int, input().split())
        for (c, v) in enumerate(row):
            idx[v - 1] = (r, c)
    (mns, mxs, mnd, mxd) = (INF, -INF, INF, -INF)
    for (r, c) in idx[::-1]:
        (s, d) = (r + c, r - c)
        if mns is INF or max(abs(s - mxs), abs(s - mns), abs(d - mxd), abs(d - mnd)) <= K:
            dp[r][c] = 'M'
            (mns, mxs) = (min(mns, s), max(mxs, s))
            (mnd, mxd) = (min(mnd, d), max(mxd, d))
    for r in range(N):
        print(''.join(dp[r]))
if __name__ == '__main__':
    main()