This problem is a harder version of the CSMO 2017 Grade 10 Problem 8.

CQYIMO42 wrote: Given the positive integer $m \geq 2$, $n \geq 3$. Define the following set $$S = \left\{(a, b) | a \in \{1, 2, \cdots, m\}, b \in \{1, 2, \cdots, n\} \right\}.$$Let $A$ be a subset of $S$. If there does not exist positive integers $x_1, x_2, x_3, y_1, y_2, y_3$ such that $x_1 < x_2 < x_3, y_1 < y_2 < y_3$ and $$(x_1, y_2), (x_2, y_1), (x_2, y_2), (x_2, y_3), (x_3, y_2) \in A.$$Determine the largest possible number of elements in $A$. Bump_ after a long time.

Take an obvious table interpretation, marking all cells in $A$. We claim that the answer is $\boxed{2m+2n-4}$. The construction is easy, just mark the cells which is on the perimeter. Now we prove the bound. The key idea is we assign arrows to each of the marked cell in the following way. For each row having at least one marked cell, assign $\leftarrow$ to the leftmost cell and assign $\rightarrow$ to the rightmost cell. If the two cells are coincide, let that cells have both left and right arrow. For each column having at least one marked cell, assign $\uparrow$ to the topmost cell and assign $\downarrow$ to the bottomost cell. If the two cells are coincide, let that cells have both left and right arrow. If the row have no marked cell, then put both $\leftarrow$ and $\rightarrow$ in the trash of that row. Repeat similar logic to each column. Observe that we have assigned exactly $2m+2n$ arrows (Including the arrows in trash). We claim that Claim 1 : Each marked cell is assigned at least one arrow. Proof : Suppose that there is a marked cell having no arrows. Then it's easy to see that there exists four cells in top, left, right and bottom of it, which broke the problem's condition so we are done. Claim 2: If the first row has $a$ marked cells, then it has at least $a+2$ arrows. (Including the arrows in trash.) Proof : If $a=0$ then the claim is obviously true. If $a=1$ then it's easy to see that we have $\leftarrow, \rightarrow, \uparrow$ in that cell, so the claim is true. If $a\geqslant 2$ then the leftmost cell must contain $\leftarrow$ and $\uparrow$. Similarly, the rightmost cell must contain $\rightarrow$ and $\uparrow$. Moreover by Claim 1, other cells have at least one arrow hence there are at least $a+2$ arrows as desired. Back to the main problem, by Claim 1 and 2, it's easy to see that $$\text{number of arrows} - \text{number of marked cells}\geqslant 4$$but we have exactly $2m+2n$ arrows hence we have at most $2m+2n-4$ marked cells as desired.