Color the Picture (Codeforces 1710A)
Tags: Greedy, constructive algorithms

A picture can be represented as an $$$n\times m$$$ grid ($$$n$$$ rows and $$$m$$$ columns) so that each of the $$$n \cdot m$$$ cells is colored with one color. You have $$$k$$$ pigments of different colors. You have a limited amount of each pigment, more precisely you can color at most $$$a_i$$$ cells with the $$$i$$$-th pigment.A picture is considered beautiful if each cell has at least $$$3$$$ toroidal neighbors with the same color as itself.Two cells are considered toroidal neighbors if they toroidally share an edge. In other words, for some integers $$$1 \leq x_1,x_2 \leq n$$$ and $$$1 \leq y_1,y_2 \leq m$$$, the cell in the $$$x_1$$$-th row and $$$y_1$$$-th column is a toroidal neighbor of the cell in the $$$x_2$$$-th row and $$$y_2$$$-th column if one of following two conditions holds:  $$$x_1-x_2 \equiv \pm1 \pmod{n}$$$ and $$$y_1=y_2$$$, or  $$$y_1-y_2 \equiv \pm1 \pmod{m}$$$ and $$$x_1=x_2$$$. Notice that each cell has exactly $$$4$$$ toroidal neighbors. For example, if $$$n=3$$$ and $$$m=4$$$, the toroidal neighbors of the cell $$$(1, 2)$$$ (the cell on the first row and second column) are: $$$(3, 2)$$$, $$$(2, 2)$$$, $$$(1, 3)$$$, $$$(1, 1)$$$. They are shown in gray on the image below:  The gray cells show toroidal neighbors of $$$(1, 2)$$$. Is it possible to color all cells with the pigments provided and create a beautiful picture?

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). The description of the test cases follows.The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$3 \leq n,m \leq 10^9$$$, $$$1 \leq k \leq 10^5$$$) — the number of rows and columns of the picture and the number of pigments.The next line contains $$$k$$$ integers $$$a_1,a_2,\dots, a_k$$$ ($$$1 \leq a_i \leq 10^9$$$) — $$$a_i$$$ is the maximum number of cells that can be colored with the $$$i$$$-th pigment.It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case, print "Yes" (without quotes) if it is possible to color a beautiful picture. Otherwise, print "No" (without quotes).

Note: In the first test case, one possible solution is as follows:  In the third test case, we can color all cells with pigment $$$1$$$.

Sample Inputs:
6
4 6 3
12 9 8
3 3 2
8 8
3 3 2
9 5
4 5 2
10 11
5 4 2
9 11
10 10 3
11 45 14

Sample Outputs:
Yes
No
Yes
Yes
No
No

Solution (Python):
import sys

def solve1(n, m, a):
    s = 0
    ok = False
    for i in a:
        v = i // m
        if v >= 2:
            s += v
            if v > 2:
                ok = True
    if ok:
        return s >= n
    else:
        return s >= n and n % 2 == 0

def solve():
    inp = sys.stdin.readline
    (n, m, k) = map(int, inp().split())
    a = list(map(int, inp().split()))
    if solve1(n, m, a) or solve1(m, n, a):
        print('Yes')
    else:
        print('No')

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
R = lambda : map(int, input().split())
G = range
(t,) = R()

def f(n, m):
    b = [v // n for v in a if v >= 2 * n]
    return not (m & 1 and all((v == 2 for v in b))) and sum(b) >= m
for _ in G(t):
    (n, m, k) = R()
    a = [*R()]
    print(['No', 'Yes'][f(n, m) or f(m, n)])

Solution (Python):
import math
import sys
import heapq
from typing import List

def traverse(mat: List[List[int]], a: int, b: int, n: int, m: int):
    q = [[a, b]]
    index = 0
    moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while index < len(q):
        i = q[index][0]
        j = q[index][1]
        mat[i][j] = True
        for t in moves:
            if not (i + t[0] < 0 or j + t[1] < 0 or i + t[0] >= n or (j + t[1] >= m) or mat[i + t[0]][j + t[1]]):
                q.append([i + t[0], j + t[1]])
        index += 1

def aux(v: int, g: List[List[int]], diff: List[List[int]], res: List[int]) -> int:
    temp_diff = 0
    for u in g[v]:
        temp_diff += aux(u, g, diff, res)
    if diff[v][0] <= temp_diff:
        return min(temp_diff, diff[v][1])
    res[0] += 1
    return diff[v][1]

def dijk(graph: List[List[int]], v: int, d: List[int], g: List[dict], deg: List[int]):
    d[v] = 0
    s = [False] * len(d)
    arr = [[0, v]]
    heapq.heapify(arr)
    while len(arr) > 0:
        temp = arr.pop()
        u = temp[1]
        dist = -1 * temp[0]
        if s[u]:
            continue
        s[u] = True
        for t in graph[u]:
            deg[t] -= g[t][u]
            if s[t] is False and deg[t] + dist + 1 < d[t]:
                d[t] = deg[t] + dist + 1
                heapq.heappush(arr, [-d[t], t])

def total(arr: List[int]) -> int:
    res = 0
    last = 0
    for a in arr:
        temp = last // a + 1
        res += temp
        last = a * temp
    return res

def solve():
    (n, m, k) = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    if sum(a) < n * m:
        print('No')
        return
    r = 0
    c = 0
    num_rows = False
    num_cols = False
    for b in a:
        num_rows |= b // m > 2
        num_cols |= b // n > 2
        r += b // m * (b // m > 1)
        c += b // n * (b // n > 1)
    if r >= n and (n % 2 == 0 or num_rows) or (c >= m and (m % 2 == 0 or num_cols)):
        print('Yes')
    else:
        print('No')

def main():
    t = int(input())
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()