If $$$a > b$$$, the answer is NO, as Alice always goes up and Bob always goes down. Otherwise, $$$a \leq b$$$, and the answer is YES if and only if the parity (oddness or evenness) of $$$a$$$ and $$$b$$$ is equal (equivalently, that $$$b - a$$$ is even). This is because the difference between them reduces by $$$2$$$ each step, and if the difference is odd, they'll end up on neighboring floors and then pass and miss each other on the next step.

Time complexity: $$$O(1)$$$

Assume that $$$A \leq B$$$ (otherwise, swap them). Now let's count the valid pairs $$$(a, b)$$$ where $$$a + b = c^2$$$ for some non-negative integer $$$c$$$.

Let's also define a useful function $$$\displaystyle P(n) = \sum_{i = 1}^{n} n^2 = \frac {n(n+1)(2n+1)} {6}$$$, representing the sum of the first $$$n$$$ positive integer squares, or the $$$n$$$-th square pyramidal number. Note that computing this might overflow a standard 64-bit integer type, so you either need to use modular inversion, or use a 128-bit type if your programming language supports it.

We could split the possibilities into three cases, and sum their results:

• $$$0 \leq c^2 \leq A$$$. Each such valid $$$c$$$ has $$$c^2 + 1$$$ possible pairs: $$$(0, c^2), (1, c^2 - 1), ..., (c^2, 0)$$$. Thus, the total number of pairs from this case is $$$\displaystyle \sum_{c = 0} ^ {\lfloor\sqrt{A}\rfloor} c^2 + 1 = P(\lfloor\sqrt{A}\rfloor) + \lfloor\sqrt{A}\rfloor + 1$$$.
• $$$A < c^2 \leq B$$$. Each such valid $$$c$$$ has $$$A + 1$$$ possible pairs: $$$(0, c^2), (1, c^2 - 1), ..., (A, c^2 - A)$$$. Thus, the total number of pairs from this case is $$$(\lfloor\sqrt{B}\rfloor - \lfloor\sqrt{A}\rfloor) \cdot (A + 1)$$$.
• $$$B < c^2 \leq A+B$$$. Each such valid $$$c$$$ has $$$A + B + 1 - c^2$$$ possible pairs: $$$(c^2 - B, B), (c^2 - B + 1, B - 1), ..., (A, c^2 - A)$$$. Thus, the total number of pairs from this case is $$$\displaystyle \sum_{c = \lfloor\sqrt{B}\rfloor + 1} ^ {\lfloor\sqrt{A + B}\rfloor} A + B + 1 - c^2 = (\lfloor\sqrt{A + B}\rfloor - \lfloor\sqrt{B}\rfloor) \cdot (A + B + 1) - (P(\lfloor\sqrt{A + B}\rfloor) - P(\lfloor\sqrt{B}\rfloor))$$$.

Time complexity: $$$O(T)$$$ or $$$O(T \log (A + B))$$$, depending on how you implement the floored square roots. [It can be done with either binary search, or by using floating points + small brute force to compensate for rounding error]

Let's define the balance of a court to be the sum of the numbers of the left half, minus the sum of the numbers of the right half. It is easy to see that the balance of a valid court should be $$$0$$$.

First, we fix the column the midline should be between (let's say it's between column $$$x$$$ and $$$x+1$$$). We slowly increase the half-width of the prospective court until at least one of the borders can't be extended further. Let's initialize an array $$$C_0, ... C_N$$$, at first with all zeros, where $$$C_i$$$ represents the balance of a court from the top of the grid to the $$$i$$$-th row. Now for each half-width $$$k$$$ (increasing from $$$1$$$ upward), we want to add $$$\displaystyle \sum_{i = 1}^{j} s_{i, x - (k - 1)} - s_{i, x + k}$$$ to each $$$C_j$$$. This can be done in $$$O(N)$$$ using a variable for the running sum.

Now, note that the balance of a court with top row $$$i$$$ and bottom row $$$j$$$ is $$$C_j - C_{i-1}$$$. Thus, this reduces to finding $$$x, y$$$ where $$$C_x = C_y$$$ and maximum $$$y - x$$$; this can be done using a hashmap in $$$O(N)$$$.

This procedure needs to be run for $$$O(M^2)$$$ possible combinations of midline and width, so the total running time is $$$O(NM^2)$$$.

If there are at least $$$K-1$$$ positions where $$$a_i = -1$$$, the answer is Infinity, as we can include those positions as well as up to one position with fixed $$$a_i$$$, and build an arithmetic sequence with any arbitrary gap. Otherwise, we must include at least two positions with fixed $$$a_i$$$, which would set the maximum possible gap (if it exists) below $$$\max_i a_i$$$. Let's try to binary search for the largest possible gap.

We fix a gap $$$G$$$ and implement a decision function on it, as to whether we could build an increasing subsequence of gap $$$G$$$ with length $$$K$$$. This can be done by a variant of the algorithm for the longest increasing subsequence problem.

As in that article, we will maintain the array $$$d[l]$$$ as the smallest element at which an increasing subsequence of length $$$l$$$ ends, except, when you binary search, you want to find the last element where $$$d[l] + G \leq a_i$$$, and then do $$$d[l+1] \leftarrow \min(d[l+1], a_i)$$$.

This works for $$$a_i \neq -1$$$, so what about the places where $$$a_i = -1$$$? It turns out:

• $$$d_{new}[1] = -\infty$$$, as a sequence of a single value can be made with an arbitrarily low number.
• $$$d_{new}[l+1] = d_{old}[l] + G$$$, as you can append this value to the end of any increasing subsequence, and make it the minimum possible with a gap of exactly $$$G$$$.

This change can be done naively to solve subtask 2, but for the full solution, we need to perform these operations "virtually". Note that if we have seen $$$c$$$ instances of $$$a_i = -1$$$ so far, we will "shifted $$$d$$$ to the right" $$$c$$$ times, and we would have added a total of $$$c \cdot G$$$ to each element of $$$d$$$; this can be saved as "offset"s of position and value. We add this offset every time we read out of $$$d$$$, and when we write into $$$d$$$, we subtract this offset.

Time complexity: $$$O(N \log K \log \max_i a_i)$$$

Assume that $$$K = 1$$$. We are trying to separate the roads of the kingdom into two parts, such that neither house can access all the vertices through their roads. Let's try to find a vertex $$$u$$$ such that there exists a $$$v$$$ where $$$u \neq v$$$ and $$$a_{u, v} = 0$$$.

If such a vertex exists, we could give house $$$1$$$ all the roads from $$$u$$$, and house $$$2$$$ the rest of the roads. House $$$2$$$ will not be able to access vertex $$$u$$$, and house $$$1$$$ will not be able to access vertex $$$v$$$, thus fulfilling the requirement.

If such a vertex does not exist, there is no solution, as the graph is complete, and there is no way of isolating house $$$2$$$ from any one vertex $$$u$$$ without allowing house $$$1$$$ access to all the vertices via the roads from vertex $$$u$$$.