Red-Blue Matrix (Codeforces 1606D)
Tags: Others, sortings

You are given a matrix, consisting of $$$n$$$ rows and $$$m$$$ columns. The $$$j$$$-th cell of the $$$i$$$-th row contains an integer $$$a_{ij}$$$.First, you have to color each row of the matrix either red or blue in such a way that at least one row is colored red and at least one row is colored blue.Then, you have to choose an integer $$$k$$$ ($$$1 \le k < m$$$) and cut the colored matrix in such a way that the first $$$k$$$ columns become a separate matrix (the left matrix) and the last $$$m-k$$$ columns become a separate matrix (the right matrix).The coloring and the cut are called perfect if two properties hold:   every red cell in the left matrix contains an integer greater than every blue cell in the left matrix;  every blue cell in the right matrix contains an integer greater than every red cell in the right matrix. Find any perfect coloring and cut, or report that there are none.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.Then the descriptions of $$$t$$$ testcases follow.The first line of each testcase contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 5 \cdot 10^5$$$; $$$n \cdot m \le 10^6$$$) — the number of rows and the number of columns in the matrix, respectively.The $$$i$$$-th of the next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i1}, a_{i2}, \dots, a_{im}$$$ ($$$1 \le a_{ij} \le 10^6$$$).The sum of $$$n \cdot m$$$ over all testcases doesn't exceed $$$10^6$$$.

Output: For each testcase print an answer. If there are no perfect colorings and cuts in the matrix, then print "NO".Otherwise, first, print "YES". Then a string, consisting of $$$n$$$ characters: the $$$i$$$-th character should be 'R' if the $$$i$$$-th row is colored red and 'B' if it's colored blue. The string should contain at least one 'R' and at least one 'B'. Finally, print an integer $$$k$$$ ($$$1 \le k < m$$$) — the number of columns from the left that are cut.

Note: The coloring and the cut for the first testcase:  

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

Sample Outputs:
YES
BRBRB 1
NO
YES
RB 3

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

def main(t):
    inf = 2147483647
    (m, n) = map(int, input().split())
    matrix = []
    for _ in range(m):
        matrix.append(tuple(map(int, input().split())))
    maxleft = [[0 for j in range(n + 1)] for i in range(m)]
    maxright = [[0 for j in range(n + 1)] for i in range(m)]
    minleft = [[inf for j in range(n + 1)] for i in range(m)]
    minright = [[inf for j in range(n + 1)] for i in range(m)]
    for i in range(m):
        for j in range(n):
            maxleft[i][j] = max(maxleft[i][j - 1], matrix[i][j])
            minleft[i][j] = min(minleft[i][j - 1], matrix[i][j])
        for j in range(n - 1, -1, -1):
            maxright[i][j] = max(maxright[i][j + 1], matrix[i][j])
            minright[i][j] = min(minright[i][j + 1], matrix[i][j])
    ans = ['B'] * m
    for j in range(n - 1):
        minleft_index = [i for i in range(m)]
        minleft_index.sort(key=lambda i: -minleft[i][j])
        currright = [maxright[i][j + 1] for i in minleft_index]
        for i in range(1, m):
            currright[i] = max(currright[i - 1], currright[i])
        leftmaximum = -inf
        rightminimum = inf
        for i in range(m - 1, 0, -1):
            (front, rear) = (minleft_index[i - 1], minleft_index[i])
            leftmaximum = max(leftmaximum, maxleft[rear][j])
            rightminimum = min(rightminimum, minright[rear][j + 1])
            if minleft[front][j] > leftmaximum and currright[i - 1] < rightminimum:
                print('YES')
                for k in range(i):
                    ans[minleft_index[k]] = 'R'
                print(''.join(ans), j + 1)
                return
    print('NO')
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

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

def sortlist(temp, flag=False):
    output = []
    vals = []
    dic = {}
    for [val, index] in temp:
        vals.append(val)
        if val not in dic:
            dic[val] = []
        dic[val].append(index)
    vals = sorted(vals, reverse=flag)
    for key in dic:
        dic[key] = dic[key][::-1]
    for val in vals:
        output.append((val, dic[val].pop()))
    return output
M = 10 ** 9 + 7

def main(t):
    inf = 2147483647
    (m, n) = map(int, input().split())
    matrix = []
    for _ in range(m):
        matrix.append(tuple(map(int, input().split())))
    maxleft = [[0 for j in range(n + 1)] for i in range(m)]
    maxright = [[0 for j in range(n + 1)] for i in range(m)]
    minleft = [[inf for j in range(n + 1)] for i in range(m)]
    minright = [[inf for j in range(n + 1)] for i in range(m)]
    for i in range(m):
        for j in range(n):
            maxleft[i][j] = max(maxleft[i][j - 1], matrix[i][j])
            minleft[i][j] = min(minleft[i][j - 1], matrix[i][j])
        for j in range(n - 1, -1, -1):
            maxright[i][j] = max(maxright[i][j + 1], matrix[i][j])
            minright[i][j] = min(minright[i][j + 1], matrix[i][j])
    ans = ['B'] * m
    for j in range(n - 1):
        minleft_index = [i for i in range(m)]
        minleft_index.sort(key=lambda i: -minleft[i][j])
        currright = [maxright[i][j + 1] for i in minleft_index]
        for i in range(1, m):
            currright[i] = max(currright[i - 1], currright[i])
        leftmaximum = -inf
        rightminimum = inf
        for i in range(m - 1, 0, -1):
            (front, rear) = (minleft_index[i - 1], minleft_index[i])
            leftmaximum = max(leftmaximum, maxleft[rear][j])
            rightminimum = min(rightminimum, minright[rear][j + 1])
            if minleft[front][j] > leftmaximum and currright[i - 1] < rightminimum:
                print('YES')
                for k in range(i):
                    ans[minleft_index[k]] = 'R'
                print(''.join(ans), j + 1)
                return
    print('NO')
T = int(input())
t = 1
while t <= T:
    main(t)
    t += 1

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')
print = sys.stdout.write
inf = float('inf')

def solve():
    (n, m) = map(int, input().split())
    M = [list(map(int, input().split())) for _ in range(n)]
    pmn = [[0] * m for _ in range(n)]
    pmx = [[0] * m for _ in range(n)]
    smn = [[0] * m for _ in range(n)]
    smx = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if j >= 1:
                pmn[i][j] = min(pmn[i][j - 1], M[i][j])
                pmx[i][j] = max(pmx[i][j - 1], M[i][j])
            else:
                pmn[i][j] = M[i][j]
                pmx[i][j] = M[i][j]
    for i in range(n):
        for j in range(m - 1, -1, -1):
            if j + 1 < m:
                smn[i][j] = min(smn[i][j + 1], M[i][j])
                smx[i][j] = max(smx[i][j + 1], M[i][j])
            else:
                smn[i][j] = M[i][j]
                smx[i][j] = M[i][j]
    I = list(range(0, n))
    for j in range(0, m - 1):
        I.sort(key=lambda i: -pmn[i][j])
        cmx = -inf
        cmn = inf
        D = [smx[i][j + 1] for i in I]
        for i in range(1, n):
            D[i] = max(D[i], D[i - 1])
        for _ in range(n - 1, 0, -1):
            i0 = I[_]
            i1 = I[_ - 1]
            cmx = max(cmx, pmx[i0][j])
            cmn = min(cmn, smn[i0][j + 1])
            if pmn[i1][j] > cmx and D[_ - 1] < cmn:
                ans = ['B'] * n
                idx = 0
                while I[idx] != i1:
                    ans[I[idx]] = 'R'
                    idx += 1
                ans[i1] = 'R'
                print('YES\n')
                print(''.join(ans) + ' ' + str(j + 1) + '\n')
                return
    print('NO\n')
for nt in range(int(input())):
    solve()