Stars Drawing (Hard Edition) (Codeforces 1015E2)
Tags: Greedy, binary search

A star is a figure of the following type: an asterisk character '*' in the center of the figure and four rays (to the left, right, top, bottom) of the same positive length. The size of a star is the length of its rays. The size of a star must be a positive number (i.e. rays of length $$$0$$$ are not allowed).Let's consider empty cells are denoted by '.', then the following figures are stars:  The leftmost figure is a star of size $$$1$$$, the middle figure is a star of size $$$2$$$ and the rightmost figure is a star of size $$$3$$$. You are given a rectangular grid of size $$$n \times m$$$ consisting only of asterisks '*' and periods (dots) '.'. Rows are numbered from $$$1$$$ to $$$n$$$, columns are numbered from $$$1$$$ to $$$m$$$. Your task is to draw this grid using any number of stars or find out that it is impossible. Stars can intersect, overlap or even coincide with each other. The number of stars in the output can't exceed $$$n \cdot m$$$. Each star should be completely inside the grid. You can use stars of same and arbitrary sizes.In this problem, you do not need to minimize the number of stars. Just find any way to draw the given grid with at most $$$n \cdot m$$$ stars.

Input: The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n, m \le 1000$$$) — the sizes of the given grid.The next $$$n$$$ lines contains $$$m$$$ characters each, the $$$i$$$-th line describes the $$$i$$$-th row of the grid. It is guaranteed that grid consists of characters '*' and '.' only.

Output: If it is impossible to draw the given grid using stars only, print "-1".Otherwise in the first line print one integer $$$k$$$ ($$$0 \le k \le n \cdot m$$$) — the number of stars needed to draw the given grid. The next $$$k$$$ lines should contain three integers each — $$$x_j$$$, $$$y_j$$$ and $$$s_j$$$, where $$$x_j$$$ is the row index of the central star character, $$$y_j$$$ is the column index of the central star character and $$$s_j$$$ is the size of the star. Each star should be completely inside the grid.

Note: In the first example the output 23 4 13 5 2is also correct.

Sample Inputs:
6 8
....*...
...**...
..*****.
...**...
....*...
........

5 5
.*...
****.
.****
..**.
.....

5 5
.*...
***..
.*...
.*...
.....

3 3
*.*
.*.
*.*

Sample Outputs:
3
3 4 1
3 5 2
3 5 1

3
2 2 1
3 3 1
3 4 1

-1

-1

Solution (Python):
def main():
    (n, m) = map(int, input().split())
    w = [c == '*' for i in range(n) for c in input()]
    nm = n * m
    q = [*[range(i, i + m) for i in range(0, nm, m)], *[range(i, nm, m) for i in range(m)]]
    e = [1000] * nm
    for f in (True, False):
        for r in q:
            v = 0
            for i in r:
                if w[i]:
                    v += 1
                    if e[i] > v:
                        e[i] = v
                else:
                    v = e[i] = 0
        if f:
            w.reverse()
            e.reverse()
    e = [c if c != 1 else 0 for c in e]
    for f in (True, False):
        for r in q:
            v = 0
            for i in r:
                if v > e[i]:
                    v -= 1
                else:
                    v = e[i]
                if v:
                    w[i] = False
        if f:
            w.reverse()
            e.reverse()
    if any(w):
        print(-1)
    else:
        r = []
        for (i, c) in enumerate(e):
            if c:
                r.append(f'{i // m + 1} {i % m + 1} {c - 1}')
        print(len(r), '\n'.join(r), sep='\n')
main()

Solution (Python):
import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
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')

class SegmentTree:

    def __init__(self, data, default=0, func=lambda a, b: a + b):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size
        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)

class Factorial:

    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]

    def calc(self, n):
        if n <= -1:
            print('Invalid argument to calculate n!')
            print('n must be non-negative value. But the argument was ' + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print('Invalid argument to calculate n^(-1)')
            print('n must be non-negative value. But the argument was ' + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print('Invalid argument to calculate (n^(-1))!')
            print('n must be non-negative value. But the argument was ' + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]

class Combination:

    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
    zipped_pairs = zip(list2, list1)
    z = [x for (_, x) in sorted(zipped_pairs)]
    return z

def product(l):
    por = 1
    for i in range(len(l)):
        por *= l[i]
    return por

def binarySearchCount(arr, n, key):
    left = 0
    right = n - 1
    count = 0
    while left <= right:
        mid = int((right + left) / 2)
        if arr[mid] < key:
            count = mid + 1
            left = mid + 1
        else:
            right = mid - 1
    return count

def countdig(n):
    c = 0
    while n > 0:
        n //= 10
        c += 1
    return c

def binary(x, length):
    y = bin(x)[2:]
    return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
    l = 0
    r = n - 1
    leftGreater = n
    while l <= r:
        m = int(l + (r - l) / 2)
        if arr[m] >= k:
            leftGreater = m
            r = m - 1
        else:
            l = m + 1
    return n - leftGreater
(n, m) = map(int, input().split())
l = []
tot = []
done = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
    l.append(input())
colsum = [[0 for i in range(m)] for j in range(n)]
rowsum = [[0 for i in range(m)] for j in range(n)]
col = [[0 for i in range(m)] for j in range(n)]
row = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
    for j in range(m):
        if l[i][j] == '*':
            rowsum[i][j] = 1
            colsum[i][j] = 1
            row[i][j] = 1
            col[i][j] = 1
for i in range(n):
    for j in range(1, m):
        if l[i][j] == '.':
            continue
        rowsum[i][j] += rowsum[i][j - 1]
for i in range(n):
    for j in range(m - 2, -1, -1):
        if l[i][j] == '.':
            continue
        row[i][j] += row[i][j + 1]
for i in range(m):
    for j in range(n - 2, -1, -1):
        if l[j][i] == '.':
            continue
        col[j][i] += col[j + 1][i]
for i in range(m):
    for j in range(1, n):
        if l[j][i] == '.':
            continue
        colsum[j][i] += colsum[j - 1][i]

def check(x, y):
    i = x
    j = y
    ans = min(row[i][j], rowsum[i][j], colsum[i][j], col[i][j]) - 1
    if ans == 0:
        return []
    return [ans]
h = [[0 for i in range(m + 1)] for j in range(n)]
v = [[0 for i in range(m)] for j in range(n + 1)]
for i in range(n):
    for j in range(m):
        if l[i][j] == '*':
            ans = check(i, j)
            for j1 in ans:
                tot.append([i + 1, j + 1, j1])
                h[i][j - j1] += 1
                h[i][j + j1 + 1] -= 1
                v[i - j1][j] += 1
                v[i + j1 + 1][j] -= 1
for i in range(n):
    for j in range(1, m):
        h[i][j] += h[i][j - 1]
for i in range(m):
    for j in range(1, n):
        v[j][i] += v[j - 1][i]
for i in range(n):
    for j in range(m):
        if l[i][j] == '*' and h[i][j] == 0 and (v[i][j] == 0):
            print(-1)
            sys.exit(0)
print(len(tot))
for i in tot:
    print(*i)

Solution (Python):
import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
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')

class SegmentTree:

    def __init__(self, data, default=0, func=lambda a, b: a + b):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size
        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

    def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
        """"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        if start == stop:
            return self.__getitem__(start)
        stop += 1
        start += self._size
        stop += self._size
        res = self._default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]
        self.invModulos = [0, 1]
        self.invFactorial_ = [1, 1]

    def calc(self, n):
        if n <= -1:
            print('Invalid argument to calculate n!')
            print('n must be non-negative value. But the argument was ' + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print('Invalid argument to calculate n^(-1)')
            print('n must be non-negative value. But the argument was ' + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        nextArr = [0] * (n + 1 - len(self.invModulos))
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print('Invalid argument to calculate (n^(-1))!')
            print('n must be non-negative value. But the argument was ' + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]

class Combination:

    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def ncr(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
    p = 2
    c = 0
    while p * p <= n:
        if prime[p] == True:
            c += 1
            for i in range(p, n + 1, p):
                pp[i] += 1
                prime[i] = False
        p += 1

def binarySearch(arr, n, key):
    left = 0
    right = n - 1
    mid = 0
    res = arr[n - 1]
    while left <= right:
        mid = (right + left) // 2
        if arr[mid] >= key:
            res = arr[mid]
            right = mid - 1
        else:
            left = mid + 1
    return res

def binarySearch1(arr, n, key):
    left = 0
    right = n - 1
    mid = 0
    res = arr[0]
    while left <= right:
        mid = (right + left) // 2
        if arr[mid] > key:
            right = mid - 1
        else:
            res = arr[mid]
            left = mid + 1
    return res
(n, m) = map(int, input().split())
l = []
tot = []
done = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
    l.append(input())
colsum = [[0 for i in range(m)] for j in range(n)]
rowsum = [[0 for i in range(m)] for j in range(n)]
col = [[0 for i in range(m)] for j in range(n)]
row = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
    for j in range(m):
        if l[i][j] == '*':
            rowsum[i][j] = 1
            colsum[i][j] = 1
            row[i][j] = 1
            col[i][j] = 1
for i in range(n):
    for j in range(1, m):
        if l[i][j] == '.':
            continue
        rowsum[i][j] += rowsum[i][j - 1]
for i in range(n):
    for j in range(m - 2, -1, -1):
        if l[i][j] == '.':
            continue
        row[i][j] += row[i][j + 1]
for i in range(m):
    for j in range(n - 2, -1, -1):
        if l[j][i] == '.':
            continue
        col[j][i] += col[j + 1][i]
for i in range(m):
    for j in range(1, n):
        if l[j][i] == '.':
            continue
        colsum[j][i] += colsum[j - 1][i]

def check(x, y):
    i = x
    j = y
    ans = min(row[i][j], rowsum[i][j], colsum[i][j], col[i][j]) - 1
    if ans == 0:
        return []
    return [ans]
h = [[0 for i in range(m + 1)] for j in range(n)]
v = [[0 for i in range(m)] for j in range(n + 1)]
for i in range(n):
    for j in range(m):
        if l[i][j] == '*':
            ans = check(i, j)
            for j1 in ans:
                tot.append([i + 1, j + 1, j1])
                h[i][j - j1] += 1
                h[i][j + j1 + 1] -= 1
                v[i - j1][j] += 1
                v[i + j1 + 1][j] -= 1
for i in range(n):
    for j in range(1, m):
        h[i][j] += h[i][j - 1]
for i in range(m):
    for j in range(1, n):
        v[j][i] += v[j - 1][i]
for i in range(n):
    for j in range(m):
        if l[i][j] == '*' and h[i][j] == 0 and (v[i][j] == 0):
            print(-1)
            sys.exit(0)
print(len(tot))
for i in tot:
    print(*i)