Color the Picture
Contest: Codeforces Round 810 (Div. 1)
Difficulty rating: 1500
Tags: constructive algorithms, greedy, math

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 format:
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 format:
For each test case, print "Yes" (without quotes) if it is possible to color a beautiful picture. Otherwise, print "No" (without quotes).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
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

Example output:
Yes
No
Yes
Yes
No
No

Editorial:
hint1.
The picture must consist of some stripes with at least $$$2$$$ rows or at least $$$2$$$ columns.
hint2.
When $$$n$$$ is odd and all $$$\lfloor \frac{a_i}{m} \rfloor=2$$$, we cannot draw a beautiful picture using row stripes.
Let's first prove hint1 first.
If there is a pair of toroidal neighbors with different colors. For example, $$$col_{x,y}=a$$$ and $$$col_{x+1,y}=b(a\neq b)$$$. Then we will find $$$col_{x-1,y}=col_{x,y+1}=col_{x,y-1}=a$$$,$$$col_{x+2,y}=col_{x+1,y+1}=col_{x+1,y-1}=b$$$ must hold. Then we find another two pairs of toroidal neighbors $$$col_{x,y+1},col_{x+1,y+1}$$$ and $$$col_{x,y-1},col_{x+1,y-1}$$$. Repeat such process, we will find the boundary should be like:
Similar, the boundaries can be vertical lines, but horizontal lines and vertical lines can not exist in one picture.
So the pattern should be row stripes both with at least $$$2$$$ rows or column stripes both with at least $$$2$$$ columns.
Check if one can draw a beautiful picture with row stripes only or with column stripes only. We consider only the case of row stripes, the reasoning is analogous for column stripes.
If it is possible, then $$$\sum_{i=1}^{n} \lfloor \frac{a_i}{m} \rfloor \geq n$$$ must hold.
If $$$n$$$ is even, then such a condition is enough.
If $$$n$$$ is odd, there must be some $$$\lfloor \frac{a_i}{m} \rfloor \geq 3$$$. In this case, you can draw a beautiful picture using such algorithm:
• Sort $$$a_i$$$ from large to small.
• Draw $$$2$$$ rows stripes of each color if possible.
• If the picture still has some rows empty, insert new rows into each stripe.
Total time complexity: $$$O(n)$$$.